Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/centrality/subgraph_alg.py: 27%
63 statements
« prev ^ index » next coverage.py v7.3.2, created at 2023-10-20 07:00 +0000
1"""
2Subraph centrality and communicability betweenness.
3"""
4import networkx as nx
5from networkx.utils import not_implemented_for
7__all__ = [
8 "subgraph_centrality_exp",
9 "subgraph_centrality",
10 "communicability_betweenness_centrality",
11 "estrada_index",
12]
15@not_implemented_for("directed")
16@not_implemented_for("multigraph")
17@nx._dispatch
18def subgraph_centrality_exp(G):
19 r"""Returns the subgraph centrality for each node of G.
21 Subgraph centrality of a node `n` is the sum of weighted closed
22 walks of all lengths starting and ending at node `n`. The weights
23 decrease with path length. Each closed walk is associated with a
24 connected subgraph ([1]_).
26 Parameters
27 ----------
28 G: graph
30 Returns
31 -------
32 nodes:dictionary
33 Dictionary of nodes with subgraph centrality as the value.
35 Raises
36 ------
37 NetworkXError
38 If the graph is not undirected and simple.
40 See Also
41 --------
42 subgraph_centrality:
43 Alternative algorithm of the subgraph centrality for each node of G.
45 Notes
46 -----
47 This version of the algorithm exponentiates the adjacency matrix.
49 The subgraph centrality of a node `u` in G can be found using
50 the matrix exponential of the adjacency matrix of G [1]_,
52 .. math::
54 SC(u)=(e^A)_{uu} .
56 References
57 ----------
58 .. [1] Ernesto Estrada, Juan A. Rodriguez-Velazquez,
59 "Subgraph centrality in complex networks",
60 Physical Review E 71, 056103 (2005).
61 https://arxiv.org/abs/cond-mat/0504730
63 Examples
64 --------
65 (Example from [1]_)
66 >>> G = nx.Graph(
67 ... [
68 ... (1, 2),
69 ... (1, 5),
70 ... (1, 8),
71 ... (2, 3),
72 ... (2, 8),
73 ... (3, 4),
74 ... (3, 6),
75 ... (4, 5),
76 ... (4, 7),
77 ... (5, 6),
78 ... (6, 7),
79 ... (7, 8),
80 ... ]
81 ... )
82 >>> sc = nx.subgraph_centrality_exp(G)
83 >>> print([f"{node} {sc[node]:0.2f}" for node in sorted(sc)])
84 ['1 3.90', '2 3.90', '3 3.64', '4 3.71', '5 3.64', '6 3.71', '7 3.64', '8 3.90']
85 """
86 # alternative implementation that calculates the matrix exponential
87 import scipy as sp
89 nodelist = list(G) # ordering of nodes in matrix
90 A = nx.to_numpy_array(G, nodelist)
91 # convert to 0-1 matrix
92 A[A != 0.0] = 1
93 expA = sp.linalg.expm(A)
94 # convert diagonal to dictionary keyed by node
95 sc = dict(zip(nodelist, map(float, expA.diagonal())))
96 return sc
99@not_implemented_for("directed")
100@not_implemented_for("multigraph")
101@nx._dispatch
102def subgraph_centrality(G):
103 r"""Returns subgraph centrality for each node in G.
105 Subgraph centrality of a node `n` is the sum of weighted closed
106 walks of all lengths starting and ending at node `n`. The weights
107 decrease with path length. Each closed walk is associated with a
108 connected subgraph ([1]_).
110 Parameters
111 ----------
112 G: graph
114 Returns
115 -------
116 nodes : dictionary
117 Dictionary of nodes with subgraph centrality as the value.
119 Raises
120 ------
121 NetworkXError
122 If the graph is not undirected and simple.
124 See Also
125 --------
126 subgraph_centrality_exp:
127 Alternative algorithm of the subgraph centrality for each node of G.
129 Notes
130 -----
131 This version of the algorithm computes eigenvalues and eigenvectors
132 of the adjacency matrix.
134 Subgraph centrality of a node `u` in G can be found using
135 a spectral decomposition of the adjacency matrix [1]_,
137 .. math::
139 SC(u)=\sum_{j=1}^{N}(v_{j}^{u})^2 e^{\lambda_{j}},
141 where `v_j` is an eigenvector of the adjacency matrix `A` of G
142 corresponding to the eigenvalue `\lambda_j`.
144 Examples
145 --------
146 (Example from [1]_)
147 >>> G = nx.Graph(
148 ... [
149 ... (1, 2),
150 ... (1, 5),
151 ... (1, 8),
152 ... (2, 3),
153 ... (2, 8),
154 ... (3, 4),
155 ... (3, 6),
156 ... (4, 5),
157 ... (4, 7),
158 ... (5, 6),
159 ... (6, 7),
160 ... (7, 8),
161 ... ]
162 ... )
163 >>> sc = nx.subgraph_centrality(G)
164 >>> print([f"{node} {sc[node]:0.2f}" for node in sorted(sc)])
165 ['1 3.90', '2 3.90', '3 3.64', '4 3.71', '5 3.64', '6 3.71', '7 3.64', '8 3.90']
167 References
168 ----------
169 .. [1] Ernesto Estrada, Juan A. Rodriguez-Velazquez,
170 "Subgraph centrality in complex networks",
171 Physical Review E 71, 056103 (2005).
172 https://arxiv.org/abs/cond-mat/0504730
174 """
175 import numpy as np
177 nodelist = list(G) # ordering of nodes in matrix
178 A = nx.to_numpy_array(G, nodelist)
179 # convert to 0-1 matrix
180 A[np.nonzero(A)] = 1
181 w, v = np.linalg.eigh(A)
182 vsquare = np.array(v) ** 2
183 expw = np.exp(w)
184 xg = vsquare @ expw
185 # convert vector dictionary keyed by node
186 sc = dict(zip(nodelist, map(float, xg)))
187 return sc
190@not_implemented_for("directed")
191@not_implemented_for("multigraph")
192@nx._dispatch
193def communicability_betweenness_centrality(G):
194 r"""Returns subgraph communicability for all pairs of nodes in G.
196 Communicability betweenness measure makes use of the number of walks
197 connecting every pair of nodes as the basis of a betweenness centrality
198 measure.
200 Parameters
201 ----------
202 G: graph
204 Returns
205 -------
206 nodes : dictionary
207 Dictionary of nodes with communicability betweenness as the value.
209 Raises
210 ------
211 NetworkXError
212 If the graph is not undirected and simple.
214 Notes
215 -----
216 Let `G=(V,E)` be a simple undirected graph with `n` nodes and `m` edges,
217 and `A` denote the adjacency matrix of `G`.
219 Let `G(r)=(V,E(r))` be the graph resulting from
220 removing all edges connected to node `r` but not the node itself.
222 The adjacency matrix for `G(r)` is `A+E(r)`, where `E(r)` has nonzeros
223 only in row and column `r`.
225 The subraph betweenness of a node `r` is [1]_
227 .. math::
229 \omega_{r} = \frac{1}{C}\sum_{p}\sum_{q}\frac{G_{prq}}{G_{pq}},
230 p\neq q, q\neq r,
232 where
233 `G_{prq}=(e^{A}_{pq} - (e^{A+E(r)})_{pq}` is the number of walks
234 involving node r,
235 `G_{pq}=(e^{A})_{pq}` is the number of closed walks starting
236 at node `p` and ending at node `q`,
237 and `C=(n-1)^{2}-(n-1)` is a normalization factor equal to the
238 number of terms in the sum.
240 The resulting `\omega_{r}` takes values between zero and one.
241 The lower bound cannot be attained for a connected
242 graph, and the upper bound is attained in the star graph.
244 References
245 ----------
246 .. [1] Ernesto Estrada, Desmond J. Higham, Naomichi Hatano,
247 "Communicability Betweenness in Complex Networks"
248 Physica A 388 (2009) 764-774.
249 https://arxiv.org/abs/0905.4102
251 Examples
252 --------
253 >>> G = nx.Graph([(0, 1), (1, 2), (1, 5), (5, 4), (2, 4), (2, 3), (4, 3), (3, 6)])
254 >>> cbc = nx.communicability_betweenness_centrality(G)
255 >>> print([f"{node} {cbc[node]:0.2f}" for node in sorted(cbc)])
256 ['0 0.03', '1 0.45', '2 0.51', '3 0.45', '4 0.40', '5 0.19', '6 0.03']
257 """
258 import numpy as np
259 import scipy as sp
261 nodelist = list(G) # ordering of nodes in matrix
262 n = len(nodelist)
263 A = nx.to_numpy_array(G, nodelist)
264 # convert to 0-1 matrix
265 A[np.nonzero(A)] = 1
266 expA = sp.linalg.expm(A)
267 mapping = dict(zip(nodelist, range(n)))
268 cbc = {}
269 for v in G:
270 # remove row and col of node v
271 i = mapping[v]
272 row = A[i, :].copy()
273 col = A[:, i].copy()
274 A[i, :] = 0
275 A[:, i] = 0
276 B = (expA - sp.linalg.expm(A)) / expA
277 # sum with row/col of node v and diag set to zero
278 B[i, :] = 0
279 B[:, i] = 0
280 B -= np.diag(np.diag(B))
281 cbc[v] = B.sum()
282 # put row and col back
283 A[i, :] = row
284 A[:, i] = col
285 # rescale when more than two nodes
286 order = len(cbc)
287 if order > 2:
288 scale = 1.0 / ((order - 1.0) ** 2 - (order - 1.0))
289 for v in cbc:
290 cbc[v] *= scale
291 return cbc
294@nx._dispatch
295def estrada_index(G):
296 r"""Returns the Estrada index of a the graph G.
298 The Estrada Index is a topological index of folding or 3D "compactness" ([1]_).
300 Parameters
301 ----------
302 G: graph
304 Returns
305 -------
306 estrada index: float
308 Raises
309 ------
310 NetworkXError
311 If the graph is not undirected and simple.
313 Notes
314 -----
315 Let `G=(V,E)` be a simple undirected graph with `n` nodes and let
316 `\lambda_{1}\leq\lambda_{2}\leq\cdots\lambda_{n}`
317 be a non-increasing ordering of the eigenvalues of its adjacency
318 matrix `A`. The Estrada index is ([1]_, [2]_)
320 .. math::
321 EE(G)=\sum_{j=1}^n e^{\lambda _j}.
323 References
324 ----------
325 .. [1] E. Estrada, "Characterization of 3D molecular structure",
326 Chem. Phys. Lett. 319, 713 (2000).
327 https://doi.org/10.1016/S0009-2614(00)00158-5
328 .. [2] José Antonio de la Peñaa, Ivan Gutman, Juan Rada,
329 "Estimating the Estrada index",
330 Linear Algebra and its Applications. 427, 1 (2007).
331 https://doi.org/10.1016/j.laa.2007.06.020
333 Examples
334 --------
335 >>> G = nx.Graph([(0, 1), (1, 2), (1, 5), (5, 4), (2, 4), (2, 3), (4, 3), (3, 6)])
336 >>> ei = nx.estrada_index(G)
337 >>> print(f"{ei:0.5}")
338 20.55
339 """
340 return sum(subgraph_centrality(G).values())