Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / algorithms / centrality / subgraph_alg.py @ 5cef0f13

History | View | Annotate | Download (9.38 KB)

1
# -*- coding: utf-8 -*-
2
"""
3
Subraph centrality and communicability betweenness.
4
"""
5
#    Copyright (C) 2011 by
6
#    Aric Hagberg <hagberg@lanl.gov>
7
#    Dan Schult <dschult@colgate.edu>
8
#    Pieter Swart <swart@lanl.gov>
9
#    All rights reserved.
10
#    BSD license.
11
import networkx as nx
12
from networkx.utils import *
13
__author__ = "\n".join(['Aric Hagberg (hagberg@lanl.gov)',
14
                        'Franck Kalala (franckkalala@yahoo.fr'])
15
__all__ = ['subgraph_centrality_exp',
16
           'subgraph_centrality',
17
           'communicability_betweenness_centrality',
18
           'estrada_index'
19
           ]
20

    
21

    
22
@not_implemented_for('directed')
23
@not_implemented_for('multigraph')
24
def subgraph_centrality_exp(G):
25
    r"""Returns the subgraph centrality for each node of G.
26

27
    Subgraph centrality  of a node `n` is the sum of weighted closed
28
    walks of all lengths starting and ending at node `n`. The weights
29
    decrease with path length. Each closed walk is associated with a
30
    connected subgraph ([1]_).
31

32
    Parameters
33
    ----------
34
    G: graph
35

36
    Returns
37
    -------
38
    nodes:dictionary
39
        Dictionary of nodes with subgraph centrality as the value.
40

41
    Raises
42
    ------
43
    NetworkXError
44
        If the graph is not undirected and simple.
45

46
    See Also
47
    --------
48
    subgraph_centrality:
49
        Alternative algorithm of the subgraph centrality for each node of G.
50

51
    Notes
52
    -----
53
    This version of the algorithm exponentiates the adjacency matrix.
54

55
    The subgraph centrality of a node `u` in G can be found using
56
    the matrix exponential of the adjacency matrix of G [1]_,
57

58
    .. math::
59

60
        SC(u)=(e^A)_{uu} .
61

62
    References
63
    ----------
64
    .. [1] Ernesto Estrada, Juan A. Rodriguez-Velazquez,
65
       "Subgraph centrality in complex networks",
66
       Physical Review E 71, 056103 (2005).
67
       https://arxiv.org/abs/cond-mat/0504730
68

69
    Examples
70
    --------
71
    (Example from [1]_)
72
    >>> 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)])
73
    >>> sc = nx.subgraph_centrality_exp(G)
74
    >>> print(['%s %0.2f'%(node,sc[node]) for node in sorted(sc)])
75
    ['1 3.90', '2 3.90', '3 3.64', '4 3.71', '5 3.64', '6 3.71', '7 3.64', '8 3.90']
76
    """
77
    # alternative implementation that calculates the matrix exponential
78
    import scipy.linalg
79
    nodelist = list(G)  # ordering of nodes in matrix
80
    A = nx.to_numpy_matrix(G, nodelist)
81
    # convert to 0-1 matrix
82
    A[A != 0.0] = 1
83
    expA = scipy.linalg.expm(A.A)
84
    # convert diagonal to dictionary keyed by node
85
    sc = dict(zip(nodelist, map(float, expA.diagonal())))
86
    return sc
87

    
88

    
89
@not_implemented_for('directed')
90
@not_implemented_for('multigraph')
91
def subgraph_centrality(G):
92
    r"""Returns subgraph centrality for each node in G.
93

94
    Subgraph centrality  of a node `n` is the sum of weighted closed
95
    walks of all lengths starting and ending at node `n`. The weights
96
    decrease with path length. Each closed walk is associated with a
97
    connected subgraph ([1]_).
98

99
    Parameters
100
    ----------
101
    G: graph
102

103
    Returns
104
    -------
105
    nodes : dictionary
106
       Dictionary of nodes with subgraph centrality as the value.
107

108
    Raises
109
    ------
110
    NetworkXError
111
       If the graph is not undirected and simple.
112

113
    See Also
114
    --------
115
    subgraph_centrality_exp:
116
        Alternative algorithm of the subgraph centrality for each node of G.
117

118
    Notes
119
    -----
120
    This version of the algorithm computes eigenvalues and eigenvectors
121
    of the adjacency matrix.
122

123
    Subgraph centrality of a node `u` in G can be found using
124
    a spectral decomposition of the adjacency matrix [1]_,
125

126
    .. math::
127

128
       SC(u)=\sum_{j=1}^{N}(v_{j}^{u})^2 e^{\lambda_{j}},
129

130
    where `v_j` is an eigenvector of the adjacency matrix `A` of G
131
    corresponding corresponding to the eigenvalue `\lambda_j`.
132

133
    Examples
134
    --------
135
    (Example from [1]_)
136
    >>> 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)])
137
    >>> sc = nx.subgraph_centrality(G)
138
    >>> print(['%s %0.2f'%(node,sc[node]) for node in sorted(sc)])
139
    ['1 3.90', '2 3.90', '3 3.64', '4 3.71', '5 3.64', '6 3.71', '7 3.64', '8 3.90']
140

141
    References
142
    ----------
143
    .. [1] Ernesto Estrada, Juan A. Rodriguez-Velazquez,
144
       "Subgraph centrality in complex networks",
145
       Physical Review E 71, 056103 (2005).
146
       https://arxiv.org/abs/cond-mat/0504730
147

148
    """
149
    import numpy
150
    import numpy.linalg
151
    nodelist = list(G)  # ordering of nodes in matrix
152
    A = nx.to_numpy_matrix(G, nodelist)
153
    # convert to 0-1 matrix
154
    A[A != 0.0] = 1
155
    w, v = numpy.linalg.eigh(A.A)
156
    vsquare = numpy.array(v)**2
157
    expw = numpy.exp(w)
158
    xg = numpy.dot(vsquare, expw)
159
    # convert vector dictionary keyed by node
160
    sc = dict(zip(nodelist, map(float, xg)))
161
    return sc
162

    
163

    
164
@not_implemented_for('directed')
165
@not_implemented_for('multigraph')
166
def communicability_betweenness_centrality(G, normalized=True):
167
    r"""Returns subgraph communicability for all pairs of nodes in G.
168

169
    Communicability betweenness measure makes use of the number of walks
170
    connecting every pair of nodes as the basis of a betweenness centrality
171
    measure.
172

173
    Parameters
174
    ----------
175
    G: graph
176

177
    Returns
178
    -------
179
    nodes : dictionary
180
        Dictionary of nodes with communicability betweenness as the value.
181

182
    Raises
183
    ------
184
    NetworkXError
185
        If the graph is not undirected and simple.
186

187
    Notes
188
    -----
189
    Let `G=(V,E)` be a simple undirected graph with `n` nodes and `m` edges,
190
    and `A` denote the adjacency matrix of `G`.
191

192
    Let `G(r)=(V,E(r))` be the graph resulting from
193
    removing all edges connected to node `r` but not the node itself.
194

195
    The adjacency matrix for `G(r)` is `A+E(r)`,  where `E(r)` has nonzeros
196
    only in row and column `r`.
197

198
    The subraph betweenness of a node `r`  is [1]_
199

200
    .. math::
201

202
         \omega_{r} = \frac{1}{C}\sum_{p}\sum_{q}\frac{G_{prq}}{G_{pq}},
203
         p\neq q, q\neq r,
204

205
    where
206
    `G_{prq}=(e^{A}_{pq} - (e^{A+E(r)})_{pq}`  is the number of walks
207
    involving node r,
208
    `G_{pq}=(e^{A})_{pq}` is the number of closed walks starting
209
    at node `p` and ending at node `q`,
210
    and `C=(n-1)^{2}-(n-1)` is a normalization factor equal to the
211
    number of terms in the sum.
212

213
    The resulting `\omega_{r}` takes values between zero and one.
214
    The lower bound cannot be attained for a connected
215
    graph, and the upper bound is attained in the star graph.
216

217
    References
218
    ----------
219
    .. [1] Ernesto Estrada, Desmond J. Higham, Naomichi Hatano,
220
       "Communicability Betweenness in Complex Networks"
221
       Physica A 388 (2009) 764-774.
222
       https://arxiv.org/abs/0905.4102
223

224
    Examples
225
    --------
226
    >>> G = nx.Graph([(0,1),(1,2),(1,5),(5,4),(2,4),(2,3),(4,3),(3,6)])
227
    >>> cbc = nx.communicability_betweenness_centrality(G)
228
    """
229
    import scipy
230
    import scipy.linalg
231
    nodelist = list(G)  # ordering of nodes in matrix
232
    n = len(nodelist)
233
    A = nx.to_numpy_matrix(G, nodelist)
234
    # convert to 0-1 matrix
235
    A[A != 0.0] = 1
236
    expA = scipy.linalg.expm(A.A)
237
    mapping = dict(zip(nodelist, range(n)))
238
    cbc = {}
239
    for v in G:
240
        # remove row and col of node v
241
        i = mapping[v]
242
        row = A[i, :].copy()
243
        col = A[:, i].copy()
244
        A[i, :] = 0
245
        A[:, i] = 0
246
        B = (expA - scipy.linalg.expm(A.A)) / expA
247
        # sum with row/col of node v and diag set to zero
248
        B[i, :] = 0
249
        B[:, i] = 0
250
        B -= scipy.diag(scipy.diag(B))
251
        cbc[v] = float(B.sum())
252
        # put row and col back
253
        A[i, :] = row
254
        A[:, i] = col
255
    # rescaling
256
    cbc = _rescale(cbc, normalized=normalized)
257
    return cbc
258

    
259

    
260
def _rescale(cbc, normalized):
261
    # helper to rescale betweenness centrality
262
    if normalized is True:
263
        order = len(cbc)
264
        if order <= 2:
265
            scale = None
266
        else:
267
            scale = 1.0 / ((order - 1.0)**2 - (order - 1.0))
268
    if scale is not None:
269
        for v in cbc:
270
            cbc[v] *= scale
271
    return cbc
272

    
273

    
274
def estrada_index(G):
275
    r"""Returns the Estrada index of a the graph G.
276

277
    The Estrada Index is a topological index of folding or 3D "compactness" ([1]_).
278

279
    Parameters
280
    ----------
281
    G: graph
282

283
    Returns
284
    -------
285
    estrada index: float
286

287
    Raises
288
    ------
289
    NetworkXError
290
        If the graph is not undirected and simple.
291

292
    Notes
293
    -----
294
    Let `G=(V,E)` be a simple undirected graph with `n` nodes  and let
295
    `\lambda_{1}\leq\lambda_{2}\leq\cdots\lambda_{n}`
296
    be a non-increasing ordering of the eigenvalues of its adjacency
297
    matrix `A`. The Estrada index is ([1]_, [2]_)
298

299
    .. math::
300
        EE(G)=\sum_{j=1}^n e^{\lambda _j}.
301

302
    References
303
    ----------
304
    .. [1] E. Estrada, "Characterization of 3D molecular structure",
305
       Chem. Phys. Lett. 319, 713 (2000).
306
       https://doi.org/10.1016/S0009-2614(00)00158-5
307
    .. [2] José Antonio de la Peñaa, Ivan Gutman, Juan Rada,
308
       "Estimating the Estrada index",
309
       Linear Algebra and its Applications. 427, 1 (2007).
310
       https://doi.org/10.1016/j.laa.2007.06.020
311

312
    Examples
313
    --------
314
    >>> G=nx.Graph([(0,1),(1,2),(1,5),(5,4),(2,4),(2,3),(4,3),(3,6)])
315
    >>> ei=nx.estrada_index(G)
316
    """
317
    return sum(subgraph_centrality(G).values())
318

    
319
# fixture for nose tests
320

    
321

    
322
def setup_module(module):
323
    from nose import SkipTest
324
    try:
325
        import numpy
326
    except:
327
        raise SkipTest("NumPy not available")
328
    try:
329
        import scipy
330
    except:
331
        raise SkipTest("SciPy not available")