Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
1"""
2Subraph centrality and communicability betweenness.
3"""
5import networkx as nx
6from networkx.utils import not_implemented_for
8__all__ = [
9 "subgraph_centrality_exp",
10 "subgraph_centrality",
11 "communicability_betweenness_centrality",
12 "estrada_index",
13]
16@not_implemented_for("directed")
17@not_implemented_for("multigraph")
18@nx._dispatchable
19def subgraph_centrality_exp(G, *, normalized=False):
20 r"""Returns the subgraph centrality for each node of G.
22 Subgraph centrality of a node `n` is the sum of weighted closed
23 walks of all lengths starting and ending at node `n`. The weights
24 decrease with path length. Each closed walk is associated with a
25 connected subgraph ([1]_).
27 Parameters
28 ----------
29 G: graph
30 normalized : bool
31 If True, normalize the centrality values using the largest eigenvalue of the
32 adjacency matrix so that the centrality values are generally between 0 and 1.
34 Returns
35 -------
36 nodes:dictionary
37 Dictionary of nodes with subgraph centrality as the value.
39 Raises
40 ------
41 NetworkXError
42 If the graph is not undirected and simple.
44 See Also
45 --------
46 subgraph_centrality:
47 Alternative algorithm of the subgraph centrality for each node of G.
49 Notes
50 -----
51 This version of the algorithm exponentiates the adjacency matrix.
53 The subgraph centrality of a node `u` in G can be found using
54 the matrix exponential of the adjacency matrix of G [1]_,
56 .. math::
58 SC(u)=(e^A)_{uu} .
60 Examples
61 --------
62 (Example from [1]_)
64 >>> G = nx.Graph(
65 ... [
66 ... (1, 2),
67 ... (1, 5),
68 ... (1, 8),
69 ... (2, 3),
70 ... (2, 8),
71 ... (3, 4),
72 ... (3, 6),
73 ... (4, 5),
74 ... (4, 7),
75 ... (5, 6),
76 ... (6, 7),
77 ... (7, 8),
78 ... ]
79 ... )
80 >>> sc = nx.subgraph_centrality_exp(G)
81 >>> print([f"{node} {sc[node]:0.2f}" for node in sorted(sc)])
82 ['1 3.90', '2 3.90', '3 3.64', '4 3.71', '5 3.64', '6 3.71', '7 3.64', '8 3.90']
83 >>> sc = nx.subgraph_centrality(G, normalized=True)
84 >>> print([f"{node} {sc[node]:0.3f}" for node in sorted(sc)])
85 ['1 0.194', '2 0.194', '3 0.181', '4 0.184', '5 0.181', '6 0.184', '7 0.181', '8 0.194']
87 References
88 ----------
89 .. [1] Ernesto Estrada, Juan A. Rodriguez-Velazquez,
90 "Subgraph centrality in complex networks",
91 Physical Review E 71, 056103 (2005).
92 https://arxiv.org/abs/cond-mat/0504730
94 """
95 # alternative implementation that calculates the matrix exponential
96 import scipy as sp
98 nodelist = list(G) # ordering of nodes in matrix
99 A = nx.to_numpy_array(G, nodelist)
100 # convert to 0-1 matrix
101 A[A != 0.0] = 1
102 expA = sp.linalg.expm(A)
103 values = map(float, expA.diagonal())
104 if normalized:
105 values = values / values.max()
106 # convert diagonal to dictionary keyed by node
107 sc = dict(zip(nodelist, values))
108 return sc
111@not_implemented_for("directed")
112@not_implemented_for("multigraph")
113@nx._dispatchable
114def subgraph_centrality(G, *, normalized=False):
115 r"""Returns subgraph centrality for each node in G.
117 Subgraph centrality of a node `n` is the sum of weighted closed
118 walks of all lengths starting and ending at node `n`. The weights
119 decrease with path length. Each closed walk is associated with a
120 connected subgraph ([1]_).
122 Parameters
123 ----------
124 G: Graph
125 normalized : bool
126 If True, normalize the centrality values using the largest eigenvalue of the
127 adjacency matrix so that the centrality values are generally between 0 and 1.
129 Returns
130 -------
131 nodes : dictionary
132 Dictionary of nodes with subgraph centrality as the value.
134 Raises
135 ------
136 NetworkXError
137 If the graph is not undirected and simple.
139 See Also
140 --------
141 subgraph_centrality_exp:
142 Alternative algorithm of the subgraph centrality for each node of G.
144 Notes
145 -----
146 This version of the algorithm computes eigenvalues and eigenvectors
147 of the adjacency matrix.
149 Subgraph centrality of a node `u` in G can be found using
150 a spectral decomposition of the adjacency matrix [1]_,
152 .. math::
154 SC(u)=\sum_{j=1}^{N}(v_{j}^{u})^2 e^{\lambda_{j}},
156 where `v_j` is an eigenvector of the adjacency matrix `A` of G
157 corresponding to the eigenvalue `\lambda_j`.
159 Examples
160 --------
161 (Example from [1]_)
163 >>> G = nx.Graph(
164 ... [
165 ... (1, 2),
166 ... (1, 5),
167 ... (1, 8),
168 ... (2, 3),
169 ... (2, 8),
170 ... (3, 4),
171 ... (3, 6),
172 ... (4, 5),
173 ... (4, 7),
174 ... (5, 6),
175 ... (6, 7),
176 ... (7, 8),
177 ... ]
178 ... )
179 >>> sc = nx.subgraph_centrality(G)
180 >>> print([f"{node} {sc[node]:0.2f}" for node in sorted(sc)])
181 ['1 3.90', '2 3.90', '3 3.64', '4 3.71', '5 3.64', '6 3.71', '7 3.64', '8 3.90']
182 >>> sc = nx.subgraph_centrality(G, normalized=True)
183 >>> print([f"{node} {sc[node]:0.3f}" for node in sorted(sc)])
184 ['1 0.194', '2 0.194', '3 0.181', '4 0.184', '5 0.181', '6 0.184', '7 0.181', '8 0.194']
186 References
187 ----------
188 .. [1] Ernesto Estrada, Juan A. Rodriguez-Velazquez,
189 "Subgraph centrality in complex networks",
190 Physical Review E 71, 056103 (2005).
191 https://arxiv.org/abs/cond-mat/0504730
193 """
194 import numpy as np
196 nodelist = list(G) # ordering of nodes in matrix
197 A = nx.to_numpy_array(G, nodelist)
198 # convert to 0-1 matrix
199 A[np.nonzero(A)] = 1
200 w, v = np.linalg.eigh(A)
201 vsquare = np.array(v) ** 2
202 if normalized:
203 expw = np.exp(w - w.max())
204 else:
205 expw = np.exp(w)
206 xg = vsquare @ expw
207 # convert vector dictionary keyed by node
208 sc = dict(zip(nodelist, map(float, xg)))
209 return sc
212@not_implemented_for("directed")
213@not_implemented_for("multigraph")
214@nx._dispatchable
215def communicability_betweenness_centrality(G):
216 r"""Returns subgraph communicability for all pairs of nodes in G.
218 Communicability betweenness measure makes use of the number of walks
219 connecting every pair of nodes as the basis of a betweenness centrality
220 measure.
222 Parameters
223 ----------
224 G: graph
226 Returns
227 -------
228 nodes : dictionary
229 Dictionary of nodes with communicability betweenness as the value.
231 Raises
232 ------
233 NetworkXError
234 If the graph is not undirected and simple.
236 Notes
237 -----
238 Let `G=(V,E)` be a simple undirected graph with `n` nodes and `m` edges,
239 and `A` denote the adjacency matrix of `G`.
241 Let `G(r)=(V,E(r))` be the graph resulting from
242 removing all edges connected to node `r` but not the node itself.
244 The adjacency matrix for `G(r)` is `A+E(r)`, where `E(r)` has nonzeros
245 only in row and column `r`.
247 The subraph betweenness of a node `r` is [1]_
249 .. math::
251 \omega_{r} = \frac{1}{C}\sum_{p}\sum_{q}\frac{G_{prq}}{G_{pq}},
252 p\neq q, q\neq r,
254 where
255 `G_{prq}=(e^{A}_{pq} - (e^{A+E(r)})_{pq}` is the number of walks
256 involving node r,
257 `G_{pq}=(e^{A})_{pq}` is the number of closed walks starting
258 at node `p` and ending at node `q`,
259 and `C=(n-1)^{2}-(n-1)` is a normalization factor equal to the
260 number of terms in the sum.
262 The resulting `\omega_{r}` takes values between zero and one.
263 The lower bound cannot be attained for a connected
264 graph, and the upper bound is attained in the star graph.
266 References
267 ----------
268 .. [1] Ernesto Estrada, Desmond J. Higham, Naomichi Hatano,
269 "Communicability Betweenness in Complex Networks"
270 Physica A 388 (2009) 764-774.
271 https://arxiv.org/abs/0905.4102
273 Examples
274 --------
275 >>> G = nx.Graph([(0, 1), (1, 2), (1, 5), (5, 4), (2, 4), (2, 3), (4, 3), (3, 6)])
276 >>> cbc = nx.communicability_betweenness_centrality(G)
277 >>> print([f"{node} {cbc[node]:0.2f}" for node in sorted(cbc)])
278 ['0 0.03', '1 0.45', '2 0.51', '3 0.45', '4 0.40', '5 0.19', '6 0.03']
279 """
280 import numpy as np
281 import scipy as sp
283 nodelist = list(G) # ordering of nodes in matrix
284 n = len(nodelist)
285 A = nx.to_numpy_array(G, nodelist)
286 # convert to 0-1 matrix
287 A[np.nonzero(A)] = 1
288 expA = sp.linalg.expm(A)
289 mapping = dict(zip(nodelist, range(n)))
290 cbc = {}
291 for v in G:
292 # remove row and col of node v
293 i = mapping[v]
294 row = A[i, :].copy()
295 col = A[:, i].copy()
296 A[i, :] = 0
297 A[:, i] = 0
298 B = (expA - sp.linalg.expm(A)) / expA
299 # sum with row/col of node v and diag set to zero
300 B[i, :] = 0
301 B[:, i] = 0
302 B -= np.diag(np.diag(B))
303 cbc[v] = float(B.sum())
304 # put row and col back
305 A[i, :] = row
306 A[:, i] = col
307 # rescale when more than two nodes
308 order = len(cbc)
309 if order > 2:
310 scale = 1.0 / ((order - 1.0) ** 2 - (order - 1.0))
311 cbc = {node: value * scale for node, value in cbc.items()}
312 return cbc
315@nx._dispatchable
316def estrada_index(G):
317 r"""Returns the Estrada index of a the graph G.
319 The Estrada Index is a topological index of folding or 3D "compactness" ([1]_).
321 Parameters
322 ----------
323 G: graph
325 Returns
326 -------
327 estrada index: float
329 Raises
330 ------
331 NetworkXError
332 If the graph is not undirected and simple.
334 Notes
335 -----
336 Let `G=(V,E)` be a simple undirected graph with `n` nodes and let
337 `\lambda_{1}\leq\lambda_{2}\leq\cdots\lambda_{n}`
338 be a non-increasing ordering of the eigenvalues of its adjacency
339 matrix `A`. The Estrada index is ([1]_, [2]_)
341 .. math::
342 EE(G)=\sum_{j=1}^n e^{\lambda _j}.
344 References
345 ----------
346 .. [1] E. Estrada, "Characterization of 3D molecular structure",
347 Chem. Phys. Lett. 319, 713 (2000).
348 https://doi.org/10.1016/S0009-2614(00)00158-5
349 .. [2] José Antonio de la Peñaa, Ivan Gutman, Juan Rada,
350 "Estimating the Estrada index",
351 Linear Algebra and its Applications. 427, 1 (2007).
352 https://doi.org/10.1016/j.laa.2007.06.020
354 Examples
355 --------
356 >>> G = nx.Graph([(0, 1), (1, 2), (1, 5), (5, 4), (2, 4), (2, 3), (4, 3), (3, 6)])
357 >>> ei = nx.estrada_index(G)
358 >>> print(f"{ei:0.5}")
359 20.55
360 """
361 return sum(subgraph_centrality(G).values())