networkx.algorithms.centrality.subgraph_centrality¶
-
subgraph_centrality
(G)[source]¶ Return subgraph centrality for each node in G.
Subgraph centrality of a node
n
is the sum of weighted closed walks of all lengths starting and ending at noden
. The weights decrease with path length. Each closed walk is associated with a connected subgraph ([1]).Parameters: G (graph) Returns: nodes – Dictionary of nodes with subgraph centrality as the value. Return type: dictionary Raises: NetworkXError
– If the graph is not undirected and simple.See also
subgraph_centrality_exp()
- Alternative algorithm of the subgraph centrality for each node of G.
Notes
This version of the algorithm computes eigenvalues and eigenvectors of the adjacency matrix.
Subgraph centrality of a node
u
in G can be found using a spectral decomposition of the adjacency matrix [1],\[SC(u)=\sum_{j=1}^{N}(v_{j}^{u})^2 e^{\lambda_{j}},\]where
v_j
is an eigenvector of the adjacency matrixA
of G corresponding corresponding to the eigenvaluelambda_j
.Examples
(Example from [1]) >>> G = nx.Graph([(1,2),(1,5),(1,8),(2,3),(2,8),(3,4),(3,6),(4,5),(4,7),(5,6),(6,7),(7,8)]) >>> sc = nx.subgraph_centrality(G) >>> print([‘%s %0.2f’%(node,sc[node]) for node in sorted(sc)]) [‘1 3.90’, ‘2 3.90’, ‘3 3.64’, ‘4 3.71’, ‘5 3.64’, ‘6 3.71’, ‘7 3.64’, ‘8 3.90’]
References
[1] (1, 2, 3) Ernesto Estrada, Juan A. Rodriguez-Velazquez, “Subgraph centrality in complex networks”, Physical Review E 71, 056103 (2005). https://arxiv.org/abs/cond-mat/0504730