Warning

This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.

# communicability_betweenness_centrality¶

communicability_betweenness_centrality(G, normalized=True)

Return communicability betweenness for all pairs of nodes in G.

Communicability betweenness measure makes use of the number of walks connecting every pair of nodes as the basis of a betweenness centrality measure.

Parameters : G: graph nodes:dictionary Dictionary of nodes with communicability betweenness as the value. NetworkXError If the graph is not undirected and simple.

communicability
Communicability between all pairs of nodes in G.
communicability_centrality
Communicability centrality for each node of G using matrix exponential.
communicability_centrality_exp
Communicability centrality for each node in G using spectral decomposition.

Notes

Let $$G=(V,E)$$ be a simple undirected graph with $$n$$ nodes and $$m$$ edges, and $$A$$ denote the adjacency matrix of $$G$$.

Let $$G(r)=(V,E(r))$$ be the graph resulting from removing all edges connected to node $$r$$ but not the node itself.

The adjacency matrix for $$G(r)$$ is $$A+E(r)$$, where $$E(r)$$ has nonzeros only in row and column $$r$$.

The communicability betweenness of a node $$r$$ is [R174]

$\omega_{r} = \frac{1}{C}\sum_{p}\sum_{q}\frac{G_{prq}}{G_{pq}}, p\neq q, q\neq r,$

where $$G_{prq}=(e^{A}_{pq} - (e^{A+E(r)})_{pq}$$ is the number of walks involving node r, $$G_{pq}=(e^{A})_{pq}$$ is the number of closed walks starting at node $$p$$ and ending at node $$q$$, and $$C=(n-1)^{2}-(n-1)$$ is a normalization factor equal to the number of terms in the sum.

The resulting $$\omega_{r}$$ takes values between zero and one. The lower bound cannot be attained for a connected graph, and the upper bound is attained in the star graph.

References

 [R174] (1, 2) Ernesto Estrada, Desmond J. Higham, Naomichi Hatano, “Communicability Betweenness in Complex Networks” Physica A 388 (2009) 764-774. http://arxiv.org/abs/0905.4102

Examples

>>> G = nx.Graph([(0,1),(1,2),(1,5),(5,4),(2,4),(2,3),(4,3),(3,6)])
>>> cbc = nx.communicability_betweenness_centrality(G)