annotate env/lib/python3.9/site-packages/networkx/algorithms/centrality/betweenness.py @ 0:4f3585e2f14bdraftdefaulttip

author shellac Mon, 22 Mar 2021 18:12:50 +0000
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
0
shellac
parents:
diff changeset
1 """Betweenness centrality measures."""
shellac
parents:
diff changeset
2 from heapq import heappush, heappop
shellac
parents:
diff changeset
3 from itertools import count
shellac
parents:
diff changeset
4 import warnings
shellac
parents:
diff changeset
5
shellac
parents:
diff changeset
6 from networkx.utils import py_random_state
shellac
parents:
diff changeset
7 from networkx.utils.decorators import not_implemented_for
shellac
parents:
diff changeset
8
shellac
parents:
diff changeset
9 __all__ = ["betweenness_centrality", "edge_betweenness_centrality", "edge_betweenness"]
shellac
parents:
diff changeset
10
shellac
parents:
diff changeset
11
shellac
parents:
diff changeset
12 @py_random_state(5)
shellac
parents:
diff changeset
13 @not_implemented_for("multigraph")
shellac
parents:
diff changeset
14 def betweenness_centrality(
shellac
parents:
diff changeset
15 G, k=None, normalized=True, weight=None, endpoints=False, seed=None
shellac
parents:
diff changeset
16 ):
shellac
parents:
diff changeset
17 r"""Compute the shortest-path betweenness centrality for nodes.
shellac
parents:
diff changeset
18
shellac
parents:
diff changeset
19 Betweenness centrality of a node $v$ is the sum of the
shellac
parents:
diff changeset
20 fraction of all-pairs shortest paths that pass through $v$
shellac
parents:
diff changeset
21
shellac
parents:
diff changeset
22 .. math::
shellac
parents:
diff changeset
23
shellac
parents:
diff changeset
24 c_B(v) =\sum_{s,t \in V} \frac{\sigma(s, t|v)}{\sigma(s, t)}
shellac
parents:
diff changeset
25
shellac
parents:
diff changeset
26 where $V$ is the set of nodes, $\sigma(s, t)$ is the number of
shellac
parents:
diff changeset
27 shortest $(s, t)$-paths, and $\sigma(s, t|v)$ is the number of
shellac
parents:
diff changeset
28 those paths passing through some node $v$ other than $s, t$.
shellac
parents:
diff changeset
29 If $s = t$, $\sigma(s, t) = 1$, and if $v \in {s, t}$,
shellac
parents:
diff changeset
30 $\sigma(s, t|v) = 0$ [2]_.
shellac
parents:
diff changeset
31
shellac
parents:
diff changeset
32 Parameters
shellac
parents:
diff changeset
33 ----------
shellac
parents:
diff changeset
34 G : graph
shellac
parents:
diff changeset
35 A NetworkX graph.
shellac
parents:
diff changeset
36
shellac
parents:
diff changeset
37 k : int, optional (default=None)
shellac
parents:
diff changeset
38 If k is not None use k node samples to estimate betweenness.
shellac
parents:
diff changeset
39 The value of k <= n where n is the number of nodes in the graph.
shellac
parents:
diff changeset
40 Higher values give better approximation.
shellac
parents:
diff changeset
41
shellac
parents:
diff changeset
42 normalized : bool, optional
shellac
parents:
diff changeset
43 If True the betweenness values are normalized by 2/((n-1)(n-2))
shellac
parents:
diff changeset
44 for graphs, and 1/((n-1)(n-2)) for directed graphs where n
shellac
parents:
diff changeset
45 is the number of nodes in G.
shellac
parents:
diff changeset
46
shellac
parents:
diff changeset
47 weight : None or string, optional (default=None)
shellac
parents:
diff changeset
48 If None, all edge weights are considered equal.
shellac
parents:
diff changeset
49 Otherwise holds the name of the edge attribute used as weight.
shellac
parents:
diff changeset
50
shellac
parents:
diff changeset
51 endpoints : bool, optional
shellac
parents:
diff changeset
52 If True include the endpoints in the shortest path counts.
shellac
parents:
diff changeset
53
shellac
parents:
diff changeset
54 seed : integer, random_state, or None (default)
shellac
parents:
diff changeset
55 Indicator of random number generation state.
shellac
parents:
diff changeset
56 See :ref:Randomness<randomness>.
shellac
parents:
diff changeset
57 Note that this is only used if k is not None.
shellac
parents:
diff changeset
58
shellac
parents:
diff changeset
59 Returns
shellac
parents:
diff changeset
60 -------
shellac
parents:
diff changeset
61 nodes : dictionary
shellac
parents:
diff changeset
62 Dictionary of nodes with betweenness centrality as the value.
shellac
parents:
diff changeset
63
shellac
parents:
diff changeset
shellac
parents:
diff changeset
65 --------
shellac
parents:
diff changeset
66 edge_betweenness_centrality
shellac
parents:
diff changeset
shellac
parents:
diff changeset
68
shellac
parents:
diff changeset
69 Notes
shellac
parents:
diff changeset
70 -----
shellac
parents:
diff changeset
71 The algorithm is from Ulrik Brandes [1]_.
shellac
parents:
diff changeset
72 See [4]_ for the original first published version and [2]_ for details on
shellac
parents:
diff changeset
73 algorithms for variations and related metrics.
shellac
parents:
diff changeset
74
shellac
parents:
diff changeset
75 For approximate betweenness calculations set k=#samples to use
shellac
parents:
diff changeset
76 k nodes ("pivots") to estimate the betweenness values. For an estimate
shellac
parents:
diff changeset
77 of the number of pivots needed see [3]_.
shellac
parents:
diff changeset
78
shellac
parents:
diff changeset
79 For weighted graphs the edge weights must be greater than zero.
shellac
parents:
diff changeset
80 Zero edge weights can produce an infinite number of equal length
shellac
parents:
diff changeset
81 paths between pairs of nodes.
shellac
parents:
diff changeset
82
shellac
parents:
diff changeset
83 The total number of paths between source and target is counted
shellac
parents:
diff changeset
84 differently for directed and undirected graphs. Directed paths
shellac
parents:
diff changeset
85 are easy to count. Undirected paths are tricky: should a path
shellac
parents:
diff changeset
86 from "u" to "v" count as 1 undirected path or as 2 directed paths?
shellac
parents:
diff changeset
87
shellac
parents:
diff changeset
88 For betweenness_centrality we report the number of undirected
shellac
parents:
diff changeset
89 paths when G is undirected.
shellac
parents:
diff changeset
90
shellac
parents:
diff changeset
91 For betweenness_centrality_subset the reporting is different.
shellac
parents:
diff changeset
92 If the source and target subsets are the same, then we want
shellac
parents:
diff changeset
93 to count undirected paths. But if the source and target subsets
shellac
parents:
diff changeset
94 differ -- for example, if sources is {0} and targets is {1},
shellac
parents:
diff changeset
95 then we are only counting the paths in one direction. They are
shellac
parents:
diff changeset
96 undirected paths but we are counting them in a directed way.
shellac
parents:
diff changeset
97 To count them as undirected paths, each should count as half a path.
shellac
parents:
diff changeset
98
shellac
parents:
diff changeset
99 References
shellac
parents:
diff changeset
100 ----------
shellac
parents:
diff changeset
101 .. [1] Ulrik Brandes:
shellac
parents:
diff changeset
102 A Faster Algorithm for Betweenness Centrality.
shellac
parents:
diff changeset
103 Journal of Mathematical Sociology 25(2):163-177, 2001.
shellac
parents:
diff changeset
104 http://www.inf.uni-konstanz.de/algo/publications/b-fabc-01.pdf
shellac
parents:
diff changeset
105 .. [2] Ulrik Brandes:
shellac
parents:
diff changeset
106 On Variants of Shortest-Path Betweenness
shellac
parents:
diff changeset
107 Centrality and their Generic Computation.
shellac
parents:
diff changeset
108 Social Networks 30(2):136-145, 2008.
shellac
parents:
diff changeset
109 http://www.inf.uni-konstanz.de/algo/publications/b-vspbc-08.pdf
shellac
parents:
diff changeset
110 .. [3] Ulrik Brandes and Christian Pich:
shellac
parents:
diff changeset
111 Centrality Estimation in Large Networks.
shellac
parents:
diff changeset
112 International Journal of Bifurcation and Chaos 17(7):2303-2318, 2007.
shellac
parents:
diff changeset
113 http://www.inf.uni-konstanz.de/algo/publications/bp-celn-06.pdf
shellac
parents:
diff changeset
114 .. [4] Linton C. Freeman:
shellac
parents:
diff changeset
115 A set of measures of centrality based on betweenness.
shellac
parents:
diff changeset
116 Sociometry 40: 35â€“41, 1977
shellac
parents:
diff changeset
117 http://moreno.ss.uci.edu/23.pdf
shellac
parents:
diff changeset
118 """
shellac
parents:
diff changeset
119 betweenness = dict.fromkeys(G, 0.0) # b[v]=0 for v in G
shellac
parents:
diff changeset
120 if k is None:
shellac
parents:
diff changeset
121 nodes = G
shellac
parents:
diff changeset
122 else:
shellac
parents:
diff changeset
123 nodes = seed.sample(G.nodes(), k)
shellac
parents:
diff changeset
124 for s in nodes:
shellac
parents:
diff changeset
125 # single source shortest paths
shellac
parents:
diff changeset
126 if weight is None: # use BFS
shellac
parents:
diff changeset
127 S, P, sigma = _single_source_shortest_path_basic(G, s)
shellac
parents:
diff changeset
128 else: # use Dijkstra's algorithm
shellac
parents:
diff changeset
129 S, P, sigma = _single_source_dijkstra_path_basic(G, s, weight)
shellac
parents:
diff changeset
130 # accumulation
shellac
parents:
diff changeset
131 if endpoints:
shellac
parents:
diff changeset
132 betweenness = _accumulate_endpoints(betweenness, S, P, sigma, s)
shellac
parents:
diff changeset
133 else:
shellac
parents:
diff changeset
134 betweenness = _accumulate_basic(betweenness, S, P, sigma, s)
shellac
parents:
diff changeset
135 # rescaling
shellac
parents:
diff changeset
136 betweenness = _rescale(
shellac
parents:
diff changeset
137 betweenness,
shellac
parents:
diff changeset
138 len(G),
shellac
parents:
diff changeset
139 normalized=normalized,
shellac
parents:
diff changeset
140 directed=G.is_directed(),
shellac
parents:
diff changeset
141 k=k,
shellac
parents:
diff changeset
142 endpoints=endpoints,
shellac
parents:
diff changeset
143 )
shellac
parents:
diff changeset
144 return betweenness
shellac
parents:
diff changeset
145
shellac
parents:
diff changeset
146
shellac
parents:
diff changeset
147 @py_random_state(4)
shellac
parents:
diff changeset
148 def edge_betweenness_centrality(G, k=None, normalized=True, weight=None, seed=None):
shellac
parents:
diff changeset
149 r"""Compute betweenness centrality for edges.
shellac
parents:
diff changeset
150
shellac
parents:
diff changeset
151 Betweenness centrality of an edge $e$ is the sum of the
shellac
parents:
diff changeset
152 fraction of all-pairs shortest paths that pass through $e$
shellac
parents:
diff changeset
153
shellac
parents:
diff changeset
154 .. math::
shellac
parents:
diff changeset
155
shellac
parents:
diff changeset
156 c_B(e) =\sum_{s,t \in V} \frac{\sigma(s, t|e)}{\sigma(s, t)}
shellac
parents:
diff changeset
157
shellac
parents:
diff changeset
158 where $V$ is the set of nodes, $\sigma(s, t)$ is the number of
shellac
parents:
diff changeset
159 shortest $(s, t)$-paths, and $\sigma(s, t|e)$ is the number of
shellac
parents:
diff changeset
160 those paths passing through edge $e$ [2]_.
shellac
parents:
diff changeset
161
shellac
parents:
diff changeset
162 Parameters
shellac
parents:
diff changeset
163 ----------
shellac
parents:
diff changeset
164 G : graph
shellac
parents:
diff changeset
165 A NetworkX graph.
shellac
parents:
diff changeset
166
shellac
parents:
diff changeset
167 k : int, optional (default=None)
shellac
parents:
diff changeset
168 If k is not None use k node samples to estimate betweenness.
shellac
parents:
diff changeset
169 The value of k <= n where n is the number of nodes in the graph.
shellac
parents:
diff changeset
170 Higher values give better approximation.
shellac
parents:
diff changeset
171
shellac
parents:
diff changeset
172 normalized : bool, optional
shellac
parents:
diff changeset
173 If True the betweenness values are normalized by $2/(n(n-1))$
shellac
parents:
diff changeset
174 for graphs, and $1/(n(n-1))$ for directed graphs where $n$
shellac
parents:
diff changeset
175 is the number of nodes in G.
shellac
parents:
diff changeset
176
shellac
parents:
diff changeset
177 weight : None or string, optional (default=None)
shellac
parents:
diff changeset
178 If None, all edge weights are considered equal.
shellac
parents:
diff changeset
179 Otherwise holds the name of the edge attribute used as weight.
shellac
parents:
diff changeset
180
shellac
parents:
diff changeset
181 seed : integer, random_state, or None (default)
shellac
parents:
diff changeset
182 Indicator of random number generation state.
shellac
parents:
diff changeset
183 See :ref:Randomness<randomness>.
shellac
parents:
diff changeset
184 Note that this is only used if k is not None.
shellac
parents:
diff changeset
185
shellac
parents:
diff changeset
186 Returns
shellac
parents:
diff changeset
187 -------
shellac
parents:
diff changeset
188 edges : dictionary
shellac
parents:
diff changeset
189 Dictionary of edges with betweenness centrality as the value.
shellac
parents:
diff changeset
190
shellac
parents:
diff changeset
shellac
parents:
diff changeset
192 --------
shellac
parents:
diff changeset
193 betweenness_centrality
shellac
parents:
diff changeset
shellac
parents:
diff changeset
195
shellac
parents:
diff changeset
196 Notes
shellac
parents:
diff changeset
197 -----
shellac
parents:
diff changeset
198 The algorithm is from Ulrik Brandes [1]_.
shellac
parents:
diff changeset
199
shellac
parents:
diff changeset
200 For weighted graphs the edge weights must be greater than zero.
shellac
parents:
diff changeset
201 Zero edge weights can produce an infinite number of equal length
shellac
parents:
diff changeset
202 paths between pairs of nodes.
shellac
parents:
diff changeset
203
shellac
parents:
diff changeset
204 References
shellac
parents:
diff changeset
205 ----------
shellac
parents:
diff changeset
206 .. [1] A Faster Algorithm for Betweenness Centrality. Ulrik Brandes,
shellac
parents:
diff changeset
207 Journal of Mathematical Sociology 25(2):163-177, 2001.
shellac
parents:
diff changeset
208 http://www.inf.uni-konstanz.de/algo/publications/b-fabc-01.pdf
shellac
parents:
diff changeset
209 .. [2] Ulrik Brandes: On Variants of Shortest-Path Betweenness
shellac
parents:
diff changeset
210 Centrality and their Generic Computation.
shellac
parents:
diff changeset
211 Social Networks 30(2):136-145, 2008.
shellac
parents:
diff changeset
212 http://www.inf.uni-konstanz.de/algo/publications/b-vspbc-08.pdf
shellac
parents:
diff changeset
213 """
shellac
parents:
diff changeset
214 betweenness = dict.fromkeys(G, 0.0) # b[v]=0 for v in G
shellac
parents:
diff changeset
215 # b[e]=0 for e in G.edges()
shellac
parents:
diff changeset
216 betweenness.update(dict.fromkeys(G.edges(), 0.0))
shellac
parents:
diff changeset
217 if k is None:
shellac
parents:
diff changeset
218 nodes = G
shellac
parents:
diff changeset
219 else:
shellac
parents:
diff changeset
220 nodes = seed.sample(G.nodes(), k)
shellac
parents:
diff changeset
221 for s in nodes:
shellac
parents:
diff changeset
222 # single source shortest paths
shellac
parents:
diff changeset
223 if weight is None: # use BFS
shellac
parents:
diff changeset
224 S, P, sigma = _single_source_shortest_path_basic(G, s)
shellac
parents:
diff changeset
225 else: # use Dijkstra's algorithm
shellac
parents:
diff changeset
226 S, P, sigma = _single_source_dijkstra_path_basic(G, s, weight)
shellac
parents:
diff changeset
227 # accumulation
shellac
parents:
diff changeset
228 betweenness = _accumulate_edges(betweenness, S, P, sigma, s)
shellac
parents:
diff changeset
229 # rescaling
shellac
parents:
diff changeset
230 for n in G: # remove nodes to only return edges
shellac
parents:
diff changeset
231 del betweenness[n]
shellac
parents:
diff changeset
232 betweenness = _rescale_e(
shellac
parents:
diff changeset
233 betweenness, len(G), normalized=normalized, directed=G.is_directed()
shellac
parents:
diff changeset
234 )
shellac
parents:
diff changeset
235 return betweenness
shellac
parents:
diff changeset
236
shellac
parents:
diff changeset
237
shellac
parents:
diff changeset
238 # obsolete name
shellac
parents:
diff changeset
239 def edge_betweenness(G, k=None, normalized=True, weight=None, seed=None):
shellac
parents:
diff changeset
240 warnings.warn(
shellac
parents:
diff changeset
241 "edge_betweeness is replaced by edge_betweenness_centrality", DeprecationWarning
shellac
parents:
diff changeset
242 )
shellac
parents:
diff changeset
243 return edge_betweenness_centrality(G, k, normalized, weight, seed)
shellac
parents:
diff changeset
244
shellac
parents:
diff changeset
245
shellac
parents:
diff changeset
246 # helpers for betweenness centrality
shellac
parents:
diff changeset
247
shellac
parents:
diff changeset
248
shellac
parents:
diff changeset
249 def _single_source_shortest_path_basic(G, s):
shellac
parents:
diff changeset
250 S = []
shellac
parents:
diff changeset
251 P = {}
shellac
parents:
diff changeset
252 for v in G:
shellac
parents:
diff changeset
253 P[v] = []
shellac
parents:
diff changeset
254 sigma = dict.fromkeys(G, 0.0) # sigma[v]=0 for v in G
shellac
parents:
diff changeset
255 D = {}
shellac
parents:
diff changeset
256 sigma[s] = 1.0
shellac
parents:
diff changeset
257 D[s] = 0
shellac
parents:
diff changeset
258 Q = [s]
shellac
parents:
diff changeset
259 while Q: # use BFS to find shortest paths
shellac
parents:
diff changeset
260 v = Q.pop(0)
shellac
parents:
diff changeset
261 S.append(v)
shellac
parents:
diff changeset
262 Dv = D[v]
shellac
parents:
diff changeset
263 sigmav = sigma[v]
shellac
parents:
diff changeset
264 for w in G[v]:
shellac
parents:
diff changeset
265 if w not in D:
shellac
parents:
diff changeset
266 Q.append(w)
shellac
parents:
diff changeset
267 D[w] = Dv + 1
shellac
parents:
diff changeset
268 if D[w] == Dv + 1: # this is a shortest path, count paths
shellac
parents:
diff changeset
269 sigma[w] += sigmav
shellac
parents:
diff changeset
270 P[w].append(v) # predecessors
shellac
parents:
diff changeset
271 return S, P, sigma
shellac
parents:
diff changeset
272
shellac
parents:
diff changeset
273
shellac
parents:
diff changeset
274 def _single_source_dijkstra_path_basic(G, s, weight):
shellac
parents:
diff changeset
275 # modified from Eppstein
shellac
parents:
diff changeset
276 S = []
shellac
parents:
diff changeset
277 P = {}
shellac
parents:
diff changeset
278 for v in G:
shellac
parents:
diff changeset
279 P[v] = []
shellac
parents:
diff changeset
280 sigma = dict.fromkeys(G, 0.0) # sigma[v]=0 for v in G
shellac
parents:
diff changeset
281 D = {}
shellac
parents:
diff changeset
282 sigma[s] = 1.0
shellac
parents:
diff changeset
283 push = heappush
shellac
parents:
diff changeset
284 pop = heappop
shellac
parents:
diff changeset
285 seen = {s: 0}
shellac
parents:
diff changeset
286 c = count()
shellac
parents:
diff changeset
287 Q = [] # use Q as heap with (distance,node id) tuples
shellac
parents:
diff changeset
288 push(Q, (0, next(c), s, s))
shellac
parents:
diff changeset
289 while Q:
shellac
parents:
diff changeset
290 (dist, _, pred, v) = pop(Q)
shellac
parents:
diff changeset
291 if v in D:
shellac
parents:
diff changeset
292 continue # already searched this node.
shellac
parents:
diff changeset
293 sigma[v] += sigma[pred] # count paths
shellac
parents:
diff changeset
294 S.append(v)
shellac
parents:
diff changeset
295 D[v] = dist
shellac
parents:
diff changeset
296 for w, edgedata in G[v].items():
shellac
parents:
diff changeset
297 vw_dist = dist + edgedata.get(weight, 1)
shellac
parents:
diff changeset
298 if w not in D and (w not in seen or vw_dist < seen[w]):
shellac
parents:
diff changeset
299 seen[w] = vw_dist
shellac
parents:
diff changeset
300 push(Q, (vw_dist, next(c), v, w))
shellac
parents:
diff changeset
301 sigma[w] = 0.0
shellac
parents:
diff changeset
302 P[w] = [v]
shellac
parents:
diff changeset
303 elif vw_dist == seen[w]: # handle equal paths
shellac
parents:
diff changeset
304 sigma[w] += sigma[v]
shellac
parents:
diff changeset
305 P[w].append(v)
shellac
parents:
diff changeset
306 return S, P, sigma
shellac
parents:
diff changeset
307
shellac
parents:
diff changeset
308
shellac
parents:
diff changeset
309 def _accumulate_basic(betweenness, S, P, sigma, s):
shellac
parents:
diff changeset
310 delta = dict.fromkeys(S, 0)
shellac
parents:
diff changeset
311 while S:
shellac
parents:
diff changeset
312 w = S.pop()
shellac
parents:
diff changeset
313 coeff = (1 + delta[w]) / sigma[w]
shellac
parents:
diff changeset
314 for v in P[w]:
shellac
parents:
diff changeset
315 delta[v] += sigma[v] * coeff
shellac
parents:
diff changeset
316 if w != s:
shellac
parents:
diff changeset
317 betweenness[w] += delta[w]
shellac
parents:
diff changeset
318 return betweenness
shellac
parents:
diff changeset
319
shellac
parents:
diff changeset
320
shellac
parents:
diff changeset
321 def _accumulate_endpoints(betweenness, S, P, sigma, s):
shellac
parents:
diff changeset
322 betweenness[s] += len(S) - 1
shellac
parents:
diff changeset
323 delta = dict.fromkeys(S, 0)
shellac
parents:
diff changeset
324 while S:
shellac
parents:
diff changeset
325 w = S.pop()
shellac
parents:
diff changeset
326 coeff = (1 + delta[w]) / sigma[w]
shellac
parents:
diff changeset
327 for v in P[w]:
shellac
parents:
diff changeset
328 delta[v] += sigma[v] * coeff
shellac
parents:
diff changeset
329 if w != s:
shellac
parents:
diff changeset
330 betweenness[w] += delta[w] + 1
shellac
parents:
diff changeset
331 return betweenness
shellac
parents:
diff changeset
332
shellac
parents:
diff changeset
333
shellac
parents:
diff changeset
334 def _accumulate_edges(betweenness, S, P, sigma, s):
shellac
parents:
diff changeset
335 delta = dict.fromkeys(S, 0)
shellac
parents:
diff changeset
336 while S:
shellac
parents:
diff changeset
337 w = S.pop()
shellac
parents:
diff changeset
338 coeff = (1 + delta[w]) / sigma[w]
shellac
parents:
diff changeset
339 for v in P[w]:
shellac
parents:
diff changeset
340 c = sigma[v] * coeff
shellac
parents:
diff changeset
341 if (v, w) not in betweenness:
shellac
parents:
diff changeset
342 betweenness[(w, v)] += c
shellac
parents:
diff changeset
343 else:
shellac
parents:
diff changeset
344 betweenness[(v, w)] += c
shellac
parents:
diff changeset
345 delta[v] += c
shellac
parents:
diff changeset
346 if w != s:
shellac
parents:
diff changeset
347 betweenness[w] += delta[w]
shellac
parents:
diff changeset
348 return betweenness
shellac
parents:
diff changeset
349
shellac
parents:
diff changeset
350
shellac
parents:
diff changeset
351 def _rescale(betweenness, n, normalized, directed=False, k=None, endpoints=False):
shellac
parents:
diff changeset
352 if normalized:
shellac
parents:
diff changeset
353 if endpoints:
shellac
parents:
diff changeset
354 if n < 2:
shellac
parents:
diff changeset
355 scale = None # no normalization
shellac
parents:
diff changeset
356 else:
shellac
parents:
diff changeset
357 # Scale factor should include endpoint nodes
shellac
parents:
diff changeset
358 scale = 1 / (n * (n - 1))
shellac
parents:
diff changeset
359 elif n <= 2:
shellac
parents:
diff changeset
360 scale = None # no normalization b=0 for all nodes
shellac
parents:
diff changeset
361 else:
shellac
parents:
diff changeset
362 scale = 1 / ((n - 1) * (n - 2))
shellac
parents:
diff changeset
363 else: # rescale by 2 for undirected graphs
shellac
parents:
diff changeset
364 if not directed:
shellac
parents:
diff changeset
365 scale = 0.5
shellac
parents:
diff changeset
366 else:
shellac
parents:
diff changeset
367 scale = None
shellac
parents:
diff changeset
368 if scale is not None:
shellac
parents:
diff changeset
369 if k is not None:
shellac
parents:
diff changeset
370 scale = scale * n / k
shellac
parents:
diff changeset
371 for v in betweenness:
shellac
parents:
diff changeset
372 betweenness[v] *= scale
shellac
parents:
diff changeset
373 return betweenness
shellac
parents:
diff changeset
374
shellac
parents:
diff changeset
375
shellac
parents:
diff changeset
376 def _rescale_e(betweenness, n, normalized, directed=False, k=None):
shellac
parents:
diff changeset
377 if normalized:
shellac
parents:
diff changeset
378 if n <= 1:
shellac
parents:
diff changeset
379 scale = None # no normalization b=0 for all nodes
shellac
parents:
diff changeset
380 else:
shellac
parents:
diff changeset
381 scale = 1 / (n * (n - 1))
shellac
parents:
diff changeset
382 else: # rescale by 2 for undirected graphs
shellac
parents:
diff changeset
383 if not directed:
shellac
parents:
diff changeset
384 scale = 0.5
shellac
parents:
diff changeset
385 else:
shellac
parents:
diff changeset
386 scale = None
shellac
parents:
diff changeset
387 if scale is not None:
shellac
parents:
diff changeset
388 if k is not None:
shellac
parents:
diff changeset
389 scale = scale * n / k
shellac
parents:
diff changeset
390 for v in betweenness: