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