Does communicability count only shortest paths?

No. The standard definition includes walks of all lengths with factorial weighting.

Can a walk revisit the same node?

Yes. Repeated visits are allowed, which distinguishes a walk from a simple path.

Is communicability a probability between zero and one?

No. The raw matrix-exponential score is not a normalized probability and can exceed one.

AI Glossary / Graphs and symbolic AI / Intermediate

Communicability

Definition

Communicability is a network measure describing the connection between two nodes using walks of many lengths, rather than only their shortest path. In the standard matrix-exponential definition, every walk of length k receives weight 1 divided by k factorial. The resulting score summarizes structural opportunities for connection under that mathematical weighting.

What it means

Two nodes can share the same shortest-path distance while having very different numbers of alternative routes between them. Communicability captures some of that additional structure by counting walks beyond the shortest ones.

A walk can revisit a node or edge. It is therefore different from a simple path, which does not repeat vertices. This distinction matters because a network containing cycles or even a single undirected edge permits indefinitely many walks through repeated traversal.

The factorial weighting makes the total well defined for a finite adjacency matrix. A communicability value is not automatically a probability, an observed communication volume, or a measured delivery rate. Its interpretation depends on whether the modeled relationships and walk-based assumptions suit the application.

How it works

For a simple unweighted undirected graph, create an adjacency matrix A. An entry is 1 when the corresponding nodes are linked and 0 otherwise. The entry at row u and column v of A raised to power k counts walks of length k from u to v.

Communicability adds those counts after dividing each by k factorial, starting with k = 0. In matrix notation, the result is exp(A), the matrix exponential. This is not the same as exponentiating each matrix entry separately.

Shorter individual walks receive more weight than longer individual walks. Nevertheless, many long walks can contribute collectively, so the measure should not be described as counting only a few nearby connections.

For distinct nodes in separate components, no connecting walk exists and their score is zero. Diagonal entries include closed walks returning to the starting node, including the length-zero contribution. Those diagonal values answer a different question from connection between two distinct nodes.

Three practical examples

1. A researcher compares pairs of nodes with equal shortest-path distance to investigate how alternative walks change their structural relationship.

2. An analyst studies an undirected collaboration network and uses communicability alongside other measures to explore patterns beyond direct contacts.

3. A graph-learning experiment uses communicability-derived features, then checks whether those features improve the particular prediction task on held-out data.

Think of it this way

Think of comparing two places by considering many possible journeys between them, giving each longer journey a progressively smaller contribution.

The analogy includes journeys that revisit places. It does not model a real traveler choosing a route, traffic capacity, travel time, or the probability that a message arrives. Those require additional assumptions and evidence.

Worked example

Consider the three-node chain A-B-C, with no other edges. There is no one-step walk from A to C, one two-step walk, no three-step walk, and two four-step walks.

The two four-step walks are A-B-A-B-C and A-B-C-B-C. There are four six-step walks, and the pattern continues for longer even lengths. Odd-length contributions are zero because the chain is bipartite and A and C lie in the same part.

The first contributions to communicability from A to C are therefore 1/2! + 2/4! + 4/6!, approximately 0.588889. Including all remaining terms gives approximately 0.589092.

The shortest-path distance remains 2, but the communicability score also reflects repeated walks. The score is not a 58.9 percent chance of communication: no probability model or observed transmission process was specified. The truncated sum illustrates the definition, while the reported full value was checked by matrix computation.

Illustrative case study

Fictional case: Fieldstone Research studies connections among project teams. Two pairs of teams are both two links apart, but one pair belongs to a more richly connected part of the network.

An analyst uses communicability to examine the difference and presents it as a structural feature. The project manager asks whether the higher score means the teams exchange more useful information. The analyst explains that the graph alone cannot establish that outcome.

The group compares the structural finding with separate evidence about actual collaboration. This fictional case shows how communicability can generate an investigative question without turning a mathematical walk count into a claim about business performance.

Common misconceptions and mistakes

Do not confuse matrix exponentiation with applying the ordinary exponential function independently to every adjacency entry. The matrix operation incorporates products that represent walks.

Do not call every walk a simple path. Repeated nodes and edges are essential to this definition.

A larger score is not universally better. Dense connectivity can increase walk counts without establishing that the underlying process is effective or desirable.

Finally, comparisons across graphs need care. Network size, density, edge meaning, and weighting conventions affect the result. A score from one representation should not be treated as directly comparable with a score from a substantially different representation without justification.

Business use

For business use, communicability can complement direct-link and shortest-path summaries when indirect relationships matter. Start by documenting what the nodes and links represent and why counting repeated walks is meaningful for the question.

Check the implementation's graph restrictions and weight handling. The cited NetworkX function is documented for simple undirected graphs. If the application involves directed dependencies or meaningful edge weights, select and validate an appropriate formulation rather than silently interpreting an unsuitable calculation as equivalent.

Check your understanding

Two nodes are in different connected components of a simple undirected graph. What is their pairwise communicability under this definition?

Answer: Zero. No walk connects the two distinct nodes, so every term contributing to their off-diagonal score is zero.

Related terms

Shortest Paths
Communicability Betweenness
graph walk
adjacency matrix
matrix exponential
shortest path
connected component
graph spectrum
centrality

Learn next

Enumerate walks of lengths two and four in a small chain. Compare their weighted contributions with the shortest-path distance, then examine how adding an edge changes the matrix exponential without interpreting the result as a measured communication rate.

Sources

Primary sources consulted: NetworkX communicability documentation, https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.communicability_alg.communicability.html ; Ernesto Estrada and Naomichi Hatano, Communicability in complex networks, https://arxiv.org/pdf/0707.0756 . The chain calculation and fictional case are original teaching examples.

Previous: Commonsense reasoning Next: Communicability Betweenness