ioftools / networkxMiCe / networkxmaster / networkx / algorithms / centrality / current_flow_betweenness_subset.py @ 5cef0f13
History  View  Annotate  Download (9.14 KB)
1 
# Copyright (C) 20102019 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 
"""Currentflow 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 currentflow betweenness centrality for subsets of nodes.

26 

27 
Currentflow betweenness centrality uses an electrical current

28 
model for information spreading in contrast to betweenness

29 
centrality which uses shortest paths.

30 

31 
Currentflow betweenness centrality is also known as

32 
randomwalk 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/(n1)(n2) 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 
Currentflow betweenness can be computed in $O(I(n1)+mn \log n)$

77 
time [1]_, where $I(n1)$ 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. 533544. SpringerVerlag, 2005.

94 
http://algo.unikonstanz.de/publications/bfcmbcf05.pdf

95 

96 
.. [2] A measure of betweenness centrality based on random walks,

97 
M. E. J. Newman, Social Networks 27, 3954 (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 currentflow betweenness centrality for edges using subsets

142 
of nodes.

143 

144 
Currentflow betweenness centrality uses an electrical current

145 
model for information spreading in contrast to betweenness

146 
centrality which uses shortest paths.

147 

148 
Currentflow betweenness centrality is also known as

149 
randomwalk 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/(n1)(n2) 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 
Currentflow betweenness can be computed in $O(I(n1)+mn \log n)$

193 
time [1]_, where $I(n1)$ 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. 533544. SpringerVerlag, 2005.

210 
http://algo.unikonstanz.de/publications/bfcmbcf05.pdf

211 

212 
.. [2] A measure of betweenness centrality based on random walks,

213 
M. E. J. Newman, Social Networks 27, 3954 (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") 