Can an endpoint have a nonzero score?

Yes. Longer walks between other nodes can visit the endpoint and return, as in the worked chain.

Why isolate the node instead of counting only shortest routes through it?

Isolation reveals its contribution to all factorial-weighted walks represented by communicability.

Can the connected-graph formula be applied blindly to disconnected graphs?

No. Zero pairwise communicabilities require an explicit convention or separate component treatment.

AI Glossary / Graphs and symbolic AI / Advanced

Communicability Betweenness

Definition

Communicability betweenness is a node-centrality measure based on how much that node contributes to the weighted walks connecting other nodes. It compares pairwise communicability before and after isolating the selected node, then averages the relative reductions. Unlike shortest-path betweenness, it includes contributions from longer walks that may revisit nodes and edges.

What it means

A node can participate in network connections even when it does not lie on another pair's shortest path. Communicability betweenness captures this broader structural role using matrix-exponential communicability.

The idea is to isolate a node by removing all its incident edges while keeping the node itself in the graph. For every eligible pair of other distinct nodes, compare their original communicability with the value after that isolation.

A large relative reduction indicates that many of the pair's weighted walks involved the selected node. Averaging these reductions gives the node's score. This is a mathematical sensitivity measure under a walk-based model, not an automatic estimate of lost revenue, traffic, or operational capacity after a real outage.

How it works

For the standard simple undirected graph formulation, pairwise communicability is an entry of exp(A), where A is the adjacency matrix. Walks of length k contribute with weight 1/k factorial.

To evaluate node r, set its adjacency row and column to zero and recompute the matrix exponential. For each pair p and q distinct from one another and from r, subtract the modified communicability from the original value and divide by the original value.

In a connected graph with at least three nodes, these denominators are positive. Average over the (n-1)(n-2) ordered eligible pairs. The resulting normalized score lies between zero and one.

The original paper defines the comparison for connected graphs. Disconnected inputs require explicit treatment because some pairwise denominators are zero. Very small graphs also need care because the usual normalization can vanish. Check the implementation rather than assigning an arbitrary meaning to undefined cases.

Three practical examples

1. A network researcher compares communicability betweenness with shortest-path betweenness to identify nodes whose roles differ when longer walks are included.

2. An analyst examines a simplified interaction graph and uses the score to investigate which nodes contribute broadly to indirect structural connections.

3. A graph-method evaluation tests how node rankings change when the network boundary or a set of uncertain edges changes, checking the stability of the interpretation.

Think of it this way

Think of temporarily closing all entrances to one place and asking how much the collection of possible journeys between other places changes, with long journeys discounted.

The analogy includes detours and repeated visits. It does not imply that travelers actually take every journey, or that closing the place produces the same practical consequences as changing a static graph model.

Worked example

Use the chain A-B-C. First evaluate the middle node B. The only eligible ordered pairs are (A, C) and (C, A). Their original communicability is approximately 0.589092 each.

Isolating B removes both edges, leaving no walk between A and C. The modified pairwise values are zero. Each relative reduction is therefore 1, so the average score for B is 1.

Now evaluate endpoint A. The eligible pair is B and C, counted in both directions. Their original communicability is approximately 1.368299. After A is isolated, B-C remains a single edge, with communicability approximately 1.175201.

The relative reduction is (1.368299 - 1.175201)/1.368299, approximately 0.141122. Thus A has positive communicability betweenness even though it lies on no shortest path between B and C. Walks that detour from B to A and back explain the contribution. The numerical values were checked using matrix exponentials computed through eigendecomposition.

Illustrative case study

Fictional case: Shoreline Analytics examines a small organizational interaction graph. A peripheral team has zero shortest-path betweenness but a positive communicability-betweenness score. A reviewer initially assumes the results conflict.

The analyst shows that the measures count different structures. The peripheral team participates in longer returning walks, even though the shortest routes between other teams do not need it.

Shoreline retains both measures with clear descriptions and avoids calling either score a direct estimate of team importance. The fictional lesson is that different centrality definitions can answer different questions without either calculation being erroneous.

Common misconceptions and mistakes

Communicability betweenness is not simply the number of neighbors a node has. It depends on the surrounding graph and weighted walks between other nodes.

It is also not ordinary shortest-path betweenness under another name. A leaf can have a positive value because walks can visit it and return.

The subtraction counts the weighted walks affected by isolation; it does not count each repeated visit as a separate independent unit of observed traffic.

Finally, distinguish a normalized structural score from a real failure-impact model. Actual systems may reroute, change behavior, or have capacities and timing constraints absent from the graph.

Business use

For business analysis, use this measure when a walk-based view of indirect connections is relevant and its assumptions can be explained. State the graph definition, normalization, component handling, and implementation alongside the ranking.

Compare the findings with operational evidence before using them to allocate resources or label entities as critical. Examine sensitivity to omitted edges and network boundaries. A stable mathematical ranking can still answer the wrong business question if the links do not represent the process of interest.

Check your understanding

In A-B-C, isolating B removes every walk between the other two nodes. What normalized communicability-betweenness score does B receive?

Answer: One. Both eligible ordered pairs lose all their original communicability, so each relative reduction and their average equal one.

Related terms

Communicability
centrality
betweenness centrality
adjacency matrix
matrix exponential
graph walk
node isolation
network robustness

Learn next

Compute both centrality measures for a small chain and triangle. Explain why the endpoint result differs, then investigate how adding a bypass edge changes the isolation comparison. Keep the mathematical experiment separate from claims about actual network traffic.

Sources

Primary sources consulted: NetworkX communicability betweenness documentation, https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.centrality.communicability_betweenness_centrality.html ; Ernesto Estrada, Desmond Higham, and Naomichi Hatano, Communicability Betweenness in Complex Networks, https://arxiv.org/pdf/0905.4102 . Connected-graph scope is explicit. The chain calculation and fictional case are original.

Previous: Communicability Next: Communication-avoiding algorithm