13
12
__all__ = ['current_flow_betweenness_centrality_subset',
14
13
'edge_current_flow_betweenness_centrality_subset']
16
16
import networkx as nx
17
from networkx.algorithms.centrality.flow_matrix import *
18
20
def current_flow_betweenness_centrality_subset(G,sources,targets,
20
"""Compute current-flow betweenness centrality for subsets nodes.
23
dtype=float, solver='lu'):
24
r"""Compute current-flow betweenness centrality for subsets of nodes.
22
26
Current-flow betweenness centrality uses an electrical current
23
27
model for information spreading in contrast to betweenness
37
41
targets: list of nodes
38
42
Nodes to use as sinks for current
40
normalized : bool, optional
44
normalized : bool, optional (default=True)
41
45
If True the betweenness values are normalized by b=b/(n-1)(n-2) where
42
46
n is the number of nodes in G.
48
weight : string or None, optional (default='weight')
49
Key for edge data used as the edge weight.
50
If None, then use 1 as each edge weight.
52
dtype: data type (float)
53
Default data type for internal matrices.
54
Set to np.float32 for lower memory consumption.
56
solver: string (default='lu')
57
Type of linear solver to use for computing the flow matrix.
58
Options are "full" (uses most memory), "lu" (recommended), and
59
"cg" (uses least memory).
68
approximate_current_flow_betweenness_centrality
51
69
betweenness_centrality
52
70
edge_betweenness_centrality
53
71
edge_current_flow_betweenness_centrality
57
The algorithm is from Brandes [1]_.
75
Current-flow betweenness can be computed in `O(I(n-1)+mn \log n)`
76
time [1]_, where `I(n-1)` is the time needed to compute the
77
inverse Laplacian. For a full matrix this is `O(n^3)` but using
78
sparse methods you can achieve `O(nm{\sqrt k})` where `k` is the
79
Laplacian matrix condition number.
81
The space required is `O(nw) where `w` is the width of the sparse
82
Laplacian matrix. Worse case is `w=n` for `O(n^2)`.
59
84
If the edges have a 'weight' attribute they will be used as
60
85
weights in this algorithm. Unspecified weights are set to 1.
70
95
.. [2] A measure of betweenness centrality based on random walks,
71
96
M. E. J. Newman, Social Networks 27, 39-54 (2005).
98
from networkx.utils import reverse_cuthill_mckee_ordering
74
100
import numpy as np
75
101
except ImportError:
77
"""current_flow_betweenness_centrality_subset() requires NumPy
102
raise ImportError('current_flow_betweenness_centrality requires NumPy ',
107
raise ImportError('current_flow_betweenness_centrality requires SciPy ',
80
109
if G.is_directed():
81
raise nx.NetworkXError(\
82
"current_flow_betweenness_centrality_subset() not defined for digraphs.")
110
raise nx.NetworkXError('current_flow_betweenness_centrality() ',
111
'not defined for digraphs.')
83
112
if not nx.is_connected(G):
84
113
raise nx.NetworkXError("Graph not connected.")
85
betweenness=dict.fromkeys(G,0.0) # b[v]=0 for v in G
86
F=_compute_F(G) # Current-flow matrix
87
m,n=F.shape # m edges and n nodes
88
mapping=dict(zip(G,range(n))) # map nodes to integers
89
for (ei,e) in enumerate(G.edges_iter()):
92
Fe=F[ei,:] # ei row of F
97
betweenness[u]+=0.5*np.abs(Fe[i]-Fe[j])
98
betweenness[v]+=0.5*np.abs(Fe[i]-Fe[j])
114
n = G.number_of_nodes()
115
ordering = list(reverse_cuthill_mckee_ordering(G))
116
# make a copy with integer labels according to rcm ordering
117
# this could be done without a copy if we really wanted to
118
mapping=dict(zip(ordering,range(n)))
119
H = nx.relabel_nodes(G,mapping)
120
betweenness = dict.fromkeys(H,0.0) # b[v]=0 for v in H
121
for row,(s,t) in flow_matrix_row(H, weight=weight, dtype=dtype,
127
betweenness[s]+=0.5*np.abs(row[i]-row[j])
128
betweenness[t]+=0.5*np.abs(row[i]-row[j])
100
130
nb=(n-1.0)*(n-2.0) # normalization factor
104
134
betweenness[v]=betweenness[v]/nb+1.0/(2-n)
108
def edge_current_flow_betweenness_centrality_subset(G,sources,targets,
110
"""Compute edge current-flow betweenness centrality for subsets
135
return dict((ordering[k],v) for k,v in betweenness.items())
138
def edge_current_flow_betweenness_centrality_subset(G, sources, targets,
141
dtype=float, solver='lu'):
142
"""Compute current-flow betweenness centrality for edges using subsets
113
145
Current-flow betweenness centrality uses an electrical current
128
160
targets: list of nodes
129
161
Nodes to use as sinks for current
131
normalized : bool, optional
163
normalized : bool, optional (default=True)
132
164
If True the betweenness values are normalized by b=b/(n-1)(n-2) where
133
165
n is the number of nodes in G.
167
weight : string or None, optional (default='weight')
168
Key for edge data used as the edge weight.
169
If None, then use 1 as each edge weight.
171
dtype: data type (float)
172
Default data type for internal matrices.
173
Set to np.float32 for lower memory consumption.
175
solver: string (default='lu')
176
Type of linear solver to use for computing the flow matrix.
177
Options are "full" (uses most memory), "lu" (recommended), and
178
"cg" (uses least memory).
137
182
nodes : dictionary
148
The algorithm is from Brandes [1]_.
193
Current-flow betweenness can be computed in `O(I(n-1)+mn \log n)`
194
time [1]_, where `I(n-1)` is the time needed to compute the
195
inverse Laplacian. For a full matrix this is `O(n^3)` but using
196
sparse methods you can achieve `O(nm{\sqrt k})` where `k` is the
197
Laplacian matrix condition number.
199
The space required is `O(nw) where `w` is the width of the sparse
200
Laplacian matrix. Worse case is `w=n` for `O(n^2)`.
150
202
If the edges have a 'weight' attribute they will be used as
151
203
weights in this algorithm. Unspecified weights are set to 1.
161
213
.. [2] A measure of betweenness centrality based on random walks,
162
214
M. E. J. Newman, Social Networks 27, 39-54 (2005).
216
from networkx.utils import reverse_cuthill_mckee_ordering
165
218
import numpy as np
166
219
except ImportError:
168
"""current_flow_betweenness_centrality_subset() requires NumPy
169
http://scipy.org/""")
220
raise ImportError('current_flow_betweenness_centrality requires NumPy ',
225
raise ImportError('current_flow_betweenness_centrality requires SciPy ',
171
227
if G.is_directed():
172
raise nx.NetworkXError(\
173
"edge_current_flow_closeness_centrality_subset() not defined for digraphs.")
228
raise nx.NetworkXError('edge_current_flow_betweenness_centrality ',
229
'not defined for digraphs.')
174
230
if not nx.is_connected(G):
175
231
raise nx.NetworkXError("Graph not connected.")
176
betweenness=(dict.fromkeys(G.edges(),0.0))
177
F=_compute_F(G) # Current-flow matrix
178
m,n=F.shape # m edges and n nodes
232
n = G.number_of_nodes()
233
ordering = list(reverse_cuthill_mckee_ordering(G))
234
# make a copy with integer labels according to rcm ordering
235
# this could be done without a copy if we really wanted to
236
mapping=dict(zip(ordering,range(n)))
237
H = nx.relabel_nodes(G,mapping)
238
betweenness=(dict.fromkeys(H.edges(),0.0))
180
240
nb=(n-1.0)*(n-2.0) # normalization factor
183
mapping=dict(zip(G,range(n))) # map nodes to integers
184
for (ei,e) in enumerate(G.edges_iter()):
185
# ei is index of edge
186
Fe=F[ei,:] # ei row of F
191
betweenness[e]+=0.5*np.abs(Fe[i]-Fe[j])
243
for row,(e) in flow_matrix_row(H, weight=weight, dtype=dtype,
249
betweenness[e]+=0.5*np.abs(row[i]-row[j])
192
250
betweenness[e]/=nb
198
"""Inverse of Laplacian."""
203
"""current_flow_betweenness_centrality_subset() requires NumPy
204
http://scipy.org/""")
206
L=nx.laplacian(G) # use ordering of G.nodes()
207
# remove first row and column
209
LRinv=np.linalg.inv(LR)
215
"""Current flow matrix."""
220
"""current_flow_betweenness_centrality_subset() requires NumPy
221
http://scipy.org/""")
222
C=np.asmatrix(_compute_C(G))
223
n=G.number_of_nodes()
224
m=G.number_of_edges()
226
# use G.nodes() and G.edges() ordering of edges for B
227
mapping=dict(zip(G,range(n))) # map nodes to integers
228
for (ei,(v,w,d)) in enumerate(G.edges_iter(data=True)):
229
c=d.get('weight',1.0)
234
return np.asarray(B.T*C)
251
return dict(((ordering[s],ordering[t]),v)
252
for (s,t),v in betweenness.items())
237
255
# fixture for nose tests
added
removed
networkx/algorithms/centrality/current_flow_betweenness_subset.py
