Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (9.14 KB)

1
#    Copyright (C) 2010-2019 by
2
#    Aric Hagberg <hagberg@lanl.gov>
3
#    Dan Schult <dschult@colgate.edu>
4
#    Pieter Swart <swart@lanl.gov>
5
#    All rights reserved.
6
#    BSD license.
7
#
8
# Author: Aric Hagberg (hagberg@lanl.gov)
9
"""Current-flow betweenness centrality measures for subsets of nodes."""
10
import itertools
11

    
12
import networkx as nx
13
from networkx.algorithms.centrality.flow_matrix import *
14
from networkx.utils import not_implemented_for, reverse_cuthill_mckee_ordering
15

    
16
__all__ = ['current_flow_betweenness_centrality_subset',
17
           'edge_current_flow_betweenness_centrality_subset']
18

    
19

    
20
@not_implemented_for('directed')
21
def current_flow_betweenness_centrality_subset(G, sources, targets,
22
                                               normalized=True,
23
                                               weight=None,
24
                                               dtype=float, solver='lu'):
25
    r"""Compute current-flow betweenness centrality for subsets of nodes.
26

27
    Current-flow betweenness centrality uses an electrical current
28
    model for information spreading in contrast to betweenness
29
    centrality which uses shortest paths.
30

31
    Current-flow betweenness centrality is also known as
32
    random-walk betweenness centrality [2]_.
33

34
    Parameters
35
    ----------
36
    G : graph
37
      A NetworkX graph
38

39
    sources: list of nodes
40
      Nodes to use as sources for current
41

42
    targets: list of nodes
43
      Nodes to use as sinks for current
44

45
    normalized : bool, optional (default=True)
46
      If True the betweenness values are normalized by b=b/(n-1)(n-2) where
47
      n is the number of nodes in G.
48

49
    weight : string or None, optional (default=None)
50
      Key for edge data used as the edge weight.
51
      If None, then use 1 as each edge weight.
52

53
    dtype: data type (float)
54
      Default data type for internal matrices.
55
      Set to np.float32 for lower memory consumption.
56

57
    solver: string (default='lu')
58
       Type of linear solver to use for computing the flow matrix.
59
       Options are "full" (uses most memory), "lu" (recommended), and
60
       "cg" (uses least memory).
61

62
    Returns
63
    -------
64
    nodes : dictionary
65
       Dictionary of nodes with betweenness centrality as the value.
66

67
    See Also
68
    --------
69
    approximate_current_flow_betweenness_centrality
70
    betweenness_centrality
71
    edge_betweenness_centrality
72
    edge_current_flow_betweenness_centrality
73

74
    Notes
75
    -----
76
    Current-flow betweenness can be computed in $O(I(n-1)+mn \log n)$
77
    time [1]_, where $I(n-1)$ is the time needed to compute the
78
    inverse Laplacian.  For a full matrix this is $O(n^3)$ but using
79
    sparse methods you can achieve $O(nm{\sqrt k})$ where $k$ is the
80
    Laplacian matrix condition number.
81

82
    The space required is $O(nw)$ where $w$ is the width of the sparse
83
    Laplacian matrix.  Worse case is $w=n$ for $O(n^2)$.
84

85
    If the edges have a 'weight' attribute they will be used as
86
    weights in this algorithm.  Unspecified weights are set to 1.
87

88
    References
89
    ----------
90
    .. [1] Centrality Measures Based on Current Flow.
91
       Ulrik Brandes and Daniel Fleischer,
92
       Proc. 22nd Symp. Theoretical Aspects of Computer Science (STACS '05).
93
       LNCS 3404, pp. 533-544. Springer-Verlag, 2005.
94
       http://algo.uni-konstanz.de/publications/bf-cmbcf-05.pdf
95

96
    .. [2] A measure of betweenness centrality based on random walks,
97
       M. E. J. Newman, Social Networks 27, 39-54 (2005).
98
    """
99
    from networkx.utils import reverse_cuthill_mckee_ordering
100
    try:
101
        import numpy as np
102
    except ImportError:
103
        raise ImportError('current_flow_betweenness_centrality requires NumPy ',
104
                          'http://scipy.org/')
105
    try:
106
        import scipy
107
    except ImportError:
108
        raise ImportError('current_flow_betweenness_centrality requires SciPy ',
109
                          'http://scipy.org/')
110
    if not nx.is_connected(G):
111
        raise nx.NetworkXError("Graph not connected.")
112
    n = G.number_of_nodes()
113
    ordering = list(reverse_cuthill_mckee_ordering(G))
114
    # make a copy with integer labels according to rcm ordering
115
    # this could be done without a copy if we really wanted to
116
    mapping = dict(zip(ordering, range(n)))
117
    H = nx.relabel_nodes(G, mapping)
118
    betweenness = dict.fromkeys(H, 0.0)  # b[v]=0 for v in H
119
    for row, (s, t) in flow_matrix_row(H, weight=weight, dtype=dtype,
120
                                       solver=solver):
121
        for ss in sources:
122
            i = mapping[ss]
123
            for tt in targets:
124
                j = mapping[tt]
125
                betweenness[s] += 0.5 * np.abs(row[i] - row[j])
126
                betweenness[t] += 0.5 * np.abs(row[i] - row[j])
127
    if normalized:
128
        nb = (n - 1.0) * (n - 2.0)  # normalization factor
129
    else:
130
        nb = 2.0
131
    for v in H:
132
        betweenness[v] = betweenness[v] / nb + 1.0 / (2 - n)
133
    return dict((ordering[k], v) for k, v in betweenness.items())
134

    
135

    
136
@not_implemented_for('directed')
137
def edge_current_flow_betweenness_centrality_subset(G, sources, targets,
138
                                                    normalized=True,
139
                                                    weight=None,
140
                                                    dtype=float, solver='lu'):
141
    r"""Compute current-flow betweenness centrality for edges using subsets
142
    of nodes.
143

144
    Current-flow betweenness centrality uses an electrical current
145
    model for information spreading in contrast to betweenness
146
    centrality which uses shortest paths.
147

148
    Current-flow betweenness centrality is also known as
149
    random-walk betweenness centrality [2]_.
150

151
    Parameters
152
    ----------
153
    G : graph
154
      A NetworkX graph
155

156
    sources: list of nodes
157
      Nodes to use as sources for current
158

159
    targets: list of nodes
160
      Nodes to use as sinks for current
161

162
    normalized : bool, optional (default=True)
163
      If True the betweenness values are normalized by b=b/(n-1)(n-2) where
164
      n is the number of nodes in G.
165

166
    weight : string or None, optional (default=None)
167
      Key for edge data used as the edge weight.
168
      If None, then use 1 as each edge weight.
169

170
    dtype: data type (float)
171
      Default data type for internal matrices.
172
      Set to np.float32 for lower memory consumption.
173

174
    solver: string (default='lu')
175
       Type of linear solver to use for computing the flow matrix.
176
       Options are "full" (uses most memory), "lu" (recommended), and
177
       "cg" (uses least memory).
178

179
    Returns
180
    -------
181
    nodes : dict
182
       Dictionary of edge tuples with betweenness centrality as the value.
183

184
    See Also
185
    --------
186
    betweenness_centrality
187
    edge_betweenness_centrality
188
    current_flow_betweenness_centrality
189

190
    Notes
191
    -----
192
    Current-flow betweenness can be computed in $O(I(n-1)+mn \log n)$
193
    time [1]_, where $I(n-1)$ is the time needed to compute the
194
    inverse Laplacian.  For a full matrix this is $O(n^3)$ but using
195
    sparse methods you can achieve $O(nm{\sqrt k})$ where $k$ is the
196
    Laplacian matrix condition number.
197

198
    The space required is $O(nw)$ where $w$ is the width of the sparse
199
    Laplacian matrix.  Worse case is $w=n$ for $O(n^2)$.
200

201
    If the edges have a 'weight' attribute they will be used as
202
    weights in this algorithm.  Unspecified weights are set to 1.
203

204
    References
205
    ----------
206
    .. [1] Centrality Measures Based on Current Flow.
207
       Ulrik Brandes and Daniel Fleischer,
208
       Proc. 22nd Symp. Theoretical Aspects of Computer Science (STACS '05).
209
       LNCS 3404, pp. 533-544. Springer-Verlag, 2005.
210
       http://algo.uni-konstanz.de/publications/bf-cmbcf-05.pdf
211

212
    .. [2] A measure of betweenness centrality based on random walks,
213
       M. E. J. Newman, Social Networks 27, 39-54 (2005).
214
    """
215
    try:
216
        import numpy as np
217
    except ImportError:
218
        raise ImportError('current_flow_betweenness_centrality requires NumPy ',
219
                          'http://scipy.org/')
220
    try:
221
        import scipy
222
    except ImportError:
223
        raise ImportError('current_flow_betweenness_centrality requires SciPy ',
224
                          'http://scipy.org/')
225
    if not nx.is_connected(G):
226
        raise nx.NetworkXError("Graph not connected.")
227
    n = G.number_of_nodes()
228
    ordering = list(reverse_cuthill_mckee_ordering(G))
229
    # make a copy with integer labels according to rcm ordering
230
    # this could be done without a copy if we really wanted to
231
    mapping = dict(zip(ordering, range(n)))
232
    H = nx.relabel_nodes(G, mapping)
233
    edges = (tuple(sorted((u, v))) for u, v in H.edges())
234
    betweenness = dict.fromkeys(edges, 0.0)
235
    if normalized:
236
        nb = (n - 1.0) * (n - 2.0)  # normalization factor
237
    else:
238
        nb = 2.0
239
    for row, (e) in flow_matrix_row(H, weight=weight, dtype=dtype,
240
                                    solver=solver):
241
        for ss in sources:
242
            i = mapping[ss]
243
            for tt in targets:
244
                j = mapping[tt]
245
                betweenness[e] += 0.5 * np.abs(row[i] - row[j])
246
        betweenness[e] /= nb
247
    return dict(((ordering[s], ordering[t]), v)
248
                for (s, t), v in betweenness.items())
249

    
250

    
251
# fixture for nose tests
252
def setup_module(module):
253
    from nose import SkipTest
254
    try:
255
        import numpy
256
        import scipy
257
    except:
258
        raise SkipTest("NumPy not available")