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