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):
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
31 Returns
32 -------
33 nodes:dictionary
34 Dictionary of nodes with subgraph centrality as the value.
36 Raises
37 ------
38 NetworkXError
39 If the graph is not undirected and simple.
41 See Also
42 --------
43 subgraph_centrality:
44 Alternative algorithm of the subgraph centrality for each node of G.
46 Notes
47 -----
48 This version of the algorithm exponentiates the adjacency matrix.
50 The subgraph centrality of a node `u` in G can be found using
51 the matrix exponential of the adjacency matrix of G [1]_,
53 .. math::
55 SC(u)=(e^A)_{uu} .
57 References
58 ----------
59 .. [1] Ernesto Estrada, Juan A. Rodriguez-Velazquez,
60 "Subgraph centrality in complex networks",
61 Physical Review E 71, 056103 (2005).
62 https://arxiv.org/abs/cond-mat/0504730
64 Examples
65 --------
66 (Example from [1]_)
68 >>> G = nx.Graph(
69 ... [
70 ... (1, 2),
71 ... (1, 5),
72 ... (1, 8),
73 ... (2, 3),
74 ... (2, 8),
75 ... (3, 4),
76 ... (3, 6),
77 ... (4, 5),
78 ... (4, 7),
79 ... (5, 6),
80 ... (6, 7),
81 ... (7, 8),
82 ... ]
83 ... )
84 >>> sc = nx.subgraph_centrality_exp(G)
85 >>> print([f"{node} {sc[node]:0.2f}" for node in sorted(sc)])
86 ['1 3.90', '2 3.90', '3 3.64', '4 3.71', '5 3.64', '6 3.71', '7 3.64', '8 3.90']
87 """
88 # alternative implementation that calculates the matrix exponential
89 import scipy as sp
91 nodelist = list(G) # ordering of nodes in matrix
92 A = nx.to_numpy_array(G, nodelist)
93 # convert to 0-1 matrix
94 A[A != 0.0] = 1
95 expA = sp.linalg.expm(A)
96 # convert diagonal to dictionary keyed by node
97 sc = dict(zip(nodelist, map(float, expA.diagonal())))
98 return sc
101@not_implemented_for("directed")
102@not_implemented_for("multigraph")
103@nx._dispatchable
104def subgraph_centrality(G):
105 r"""Returns subgraph centrality for each node in G.
107 Subgraph centrality of a node `n` is the sum of weighted closed
108 walks of all lengths starting and ending at node `n`. The weights
109 decrease with path length. Each closed walk is associated with a
110 connected subgraph ([1]_).
112 Parameters
113 ----------
114 G: graph
116 Returns
117 -------
118 nodes : dictionary
119 Dictionary of nodes with subgraph centrality as the value.
121 Raises
122 ------
123 NetworkXError
124 If the graph is not undirected and simple.
126 See Also
127 --------
128 subgraph_centrality_exp:
129 Alternative algorithm of the subgraph centrality for each node of G.
131 Notes
132 -----
133 This version of the algorithm computes eigenvalues and eigenvectors
134 of the adjacency matrix.
136 Subgraph centrality of a node `u` in G can be found using
137 a spectral decomposition of the adjacency matrix [1]_,
139 .. math::
141 SC(u)=\sum_{j=1}^{N}(v_{j}^{u})^2 e^{\lambda_{j}},
143 where `v_j` is an eigenvector of the adjacency matrix `A` of G
144 corresponding to the eigenvalue `\lambda_j`.
146 Examples
147 --------
148 (Example from [1]_)
150 >>> G = nx.Graph(
151 ... [
152 ... (1, 2),
153 ... (1, 5),
154 ... (1, 8),
155 ... (2, 3),
156 ... (2, 8),
157 ... (3, 4),
158 ... (3, 6),
159 ... (4, 5),
160 ... (4, 7),
161 ... (5, 6),
162 ... (6, 7),
163 ... (7, 8),
164 ... ]
165 ... )
166 >>> sc = nx.subgraph_centrality(G)
167 >>> print([f"{node} {sc[node]:0.2f}" for node in sorted(sc)])
168 ['1 3.90', '2 3.90', '3 3.64', '4 3.71', '5 3.64', '6 3.71', '7 3.64', '8 3.90']
170 References
171 ----------
172 .. [1] Ernesto Estrada, Juan A. Rodriguez-Velazquez,
173 "Subgraph centrality in complex networks",
174 Physical Review E 71, 056103 (2005).
175 https://arxiv.org/abs/cond-mat/0504730
177 """
178 import numpy as np
180 nodelist = list(G) # ordering of nodes in matrix
181 A = nx.to_numpy_array(G, nodelist)
182 # convert to 0-1 matrix
183 A[np.nonzero(A)] = 1
184 w, v = np.linalg.eigh(A)
185 vsquare = np.array(v) ** 2
186 expw = np.exp(w)
187 xg = vsquare @ expw
188 # convert vector dictionary keyed by node
189 sc = dict(zip(nodelist, map(float, xg)))
190 return sc
193@not_implemented_for("directed")
194@not_implemented_for("multigraph")
195@nx._dispatchable
196def communicability_betweenness_centrality(G):
197 r"""Returns subgraph communicability for all pairs of nodes in G.
199 Communicability betweenness measure makes use of the number of walks
200 connecting every pair of nodes as the basis of a betweenness centrality
201 measure.
203 Parameters
204 ----------
205 G: graph
207 Returns
208 -------
209 nodes : dictionary
210 Dictionary of nodes with communicability betweenness as the value.
212 Raises
213 ------
214 NetworkXError
215 If the graph is not undirected and simple.
217 Notes
218 -----
219 Let `G=(V,E)` be a simple undirected graph with `n` nodes and `m` edges,
220 and `A` denote the adjacency matrix of `G`.
222 Let `G(r)=(V,E(r))` be the graph resulting from
223 removing all edges connected to node `r` but not the node itself.
225 The adjacency matrix for `G(r)` is `A+E(r)`, where `E(r)` has nonzeros
226 only in row and column `r`.
228 The subraph betweenness of a node `r` is [1]_
230 .. math::
232 \omega_{r} = \frac{1}{C}\sum_{p}\sum_{q}\frac{G_{prq}}{G_{pq}},
233 p\neq q, q\neq r,
235 where
236 `G_{prq}=(e^{A}_{pq} - (e^{A+E(r)})_{pq}` is the number of walks
237 involving node r,
238 `G_{pq}=(e^{A})_{pq}` is the number of closed walks starting
239 at node `p` and ending at node `q`,
240 and `C=(n-1)^{2}-(n-1)` is a normalization factor equal to the
241 number of terms in the sum.
243 The resulting `\omega_{r}` takes values between zero and one.
244 The lower bound cannot be attained for a connected
245 graph, and the upper bound is attained in the star graph.
247 References
248 ----------
249 .. [1] Ernesto Estrada, Desmond J. Higham, Naomichi Hatano,
250 "Communicability Betweenness in Complex Networks"
251 Physica A 388 (2009) 764-774.
252 https://arxiv.org/abs/0905.4102
254 Examples
255 --------
256 >>> G = nx.Graph([(0, 1), (1, 2), (1, 5), (5, 4), (2, 4), (2, 3), (4, 3), (3, 6)])
257 >>> cbc = nx.communicability_betweenness_centrality(G)
258 >>> print([f"{node} {cbc[node]:0.2f}" for node in sorted(cbc)])
259 ['0 0.03', '1 0.45', '2 0.51', '3 0.45', '4 0.40', '5 0.19', '6 0.03']
260 """
261 import numpy as np
262 import scipy as sp
264 nodelist = list(G) # ordering of nodes in matrix
265 n = len(nodelist)
266 A = nx.to_numpy_array(G, nodelist)
267 # convert to 0-1 matrix
268 A[np.nonzero(A)] = 1
269 expA = sp.linalg.expm(A)
270 mapping = dict(zip(nodelist, range(n)))
271 cbc = {}
272 for v in G:
273 # remove row and col of node v
274 i = mapping[v]
275 row = A[i, :].copy()
276 col = A[:, i].copy()
277 A[i, :] = 0
278 A[:, i] = 0
279 B = (expA - sp.linalg.expm(A)) / expA
280 # sum with row/col of node v and diag set to zero
281 B[i, :] = 0
282 B[:, i] = 0
283 B -= np.diag(np.diag(B))
284 cbc[v] = float(B.sum())
285 # put row and col back
286 A[i, :] = row
287 A[:, i] = col
288 # rescale when more than two nodes
289 order = len(cbc)
290 if order > 2:
291 scale = 1.0 / ((order - 1.0) ** 2 - (order - 1.0))
292 cbc = {node: value * scale for node, value in cbc.items()}
293 return cbc
296@nx._dispatchable
297def estrada_index(G):
298 r"""Returns the Estrada index of a the graph G.
300 The Estrada Index is a topological index of folding or 3D "compactness" ([1]_).
302 Parameters
303 ----------
304 G: graph
306 Returns
307 -------
308 estrada index: float
310 Raises
311 ------
312 NetworkXError
313 If the graph is not undirected and simple.
315 Notes
316 -----
317 Let `G=(V,E)` be a simple undirected graph with `n` nodes and let
318 `\lambda_{1}\leq\lambda_{2}\leq\cdots\lambda_{n}`
319 be a non-increasing ordering of the eigenvalues of its adjacency
320 matrix `A`. The Estrada index is ([1]_, [2]_)
322 .. math::
323 EE(G)=\sum_{j=1}^n e^{\lambda _j}.
325 References
326 ----------
327 .. [1] E. Estrada, "Characterization of 3D molecular structure",
328 Chem. Phys. Lett. 319, 713 (2000).
329 https://doi.org/10.1016/S0009-2614(00)00158-5
330 .. [2] José Antonio de la Peñaa, Ivan Gutman, Juan Rada,
331 "Estimating the Estrada index",
332 Linear Algebra and its Applications. 427, 1 (2007).
333 https://doi.org/10.1016/j.laa.2007.06.020
335 Examples
336 --------
337 >>> G = nx.Graph([(0, 1), (1, 2), (1, 5), (5, 4), (2, 4), (2, 3), (4, 3), (3, 6)])
338 >>> ei = nx.estrada_index(G)
339 >>> print(f"{ei:0.5}")
340 20.55
341 """
342 return sum(subgraph_centrality(G).values())