Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/centrality/betweenness_subset.py @ 0:4f3585e2f14b draft default tip
"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
author | shellac |
---|---|
date | Mon, 22 Mar 2021 18:12:50 +0000 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:4f3585e2f14b |
---|---|
1 """Betweenness centrality measures for subsets of nodes.""" | |
2 import warnings | |
3 | |
4 from networkx.algorithms.centrality.betweenness import ( | |
5 _single_source_dijkstra_path_basic as dijkstra, | |
6 ) | |
7 from networkx.algorithms.centrality.betweenness import ( | |
8 _single_source_shortest_path_basic as shortest_path, | |
9 ) | |
10 | |
11 __all__ = [ | |
12 "betweenness_centrality_subset", | |
13 "betweenness_centrality_source", | |
14 "edge_betweenness_centrality_subset", | |
15 ] | |
16 | |
17 | |
18 def betweenness_centrality_subset(G, sources, targets, normalized=False, weight=None): | |
19 r"""Compute betweenness centrality for a subset of nodes. | |
20 | |
21 .. math:: | |
22 | |
23 c_B(v) =\sum_{s\in S, t \in T} \frac{\sigma(s, t|v)}{\sigma(s, t)} | |
24 | |
25 where $S$ is the set of sources, $T$ is the set of targets, | |
26 $\sigma(s, t)$ is the number of shortest $(s, t)$-paths, | |
27 and $\sigma(s, t|v)$ is the number of those paths | |
28 passing through some node $v$ other than $s, t$. | |
29 If $s = t$, $\sigma(s, t) = 1$, | |
30 and if $v \in {s, t}$, $\sigma(s, t|v) = 0$ [2]_. | |
31 | |
32 | |
33 Parameters | |
34 ---------- | |
35 G : graph | |
36 A NetworkX graph. | |
37 | |
38 sources: list of nodes | |
39 Nodes to use as sources for shortest paths in betweenness | |
40 | |
41 targets: list of nodes | |
42 Nodes to use as targets for shortest paths in betweenness | |
43 | |
44 normalized : bool, optional | |
45 If True the betweenness values are normalized by $2/((n-1)(n-2))$ | |
46 for graphs, and $1/((n-1)(n-2))$ for directed graphs where $n$ | |
47 is the number of nodes in G. | |
48 | |
49 weight : None or string, optional (default=None) | |
50 If None, all edge weights are considered equal. | |
51 Otherwise holds the name of the edge attribute used as weight. | |
52 | |
53 Returns | |
54 ------- | |
55 nodes : dictionary | |
56 Dictionary of nodes with betweenness centrality as the value. | |
57 | |
58 See Also | |
59 -------- | |
60 edge_betweenness_centrality | |
61 load_centrality | |
62 | |
63 Notes | |
64 ----- | |
65 The basic algorithm is from [1]_. | |
66 | |
67 For weighted graphs the edge weights must be greater than zero. | |
68 Zero edge weights can produce an infinite number of equal length | |
69 paths between pairs of nodes. | |
70 | |
71 The normalization might seem a little strange but it is | |
72 designed to make betweenness_centrality(G) be the same as | |
73 betweenness_centrality_subset(G,sources=G.nodes(),targets=G.nodes()). | |
74 | |
75 The total number of paths between source and target is counted | |
76 differently for directed and undirected graphs. Directed paths | |
77 are easy to count. Undirected paths are tricky: should a path | |
78 from "u" to "v" count as 1 undirected path or as 2 directed paths? | |
79 | |
80 For betweenness_centrality we report the number of undirected | |
81 paths when G is undirected. | |
82 | |
83 For betweenness_centrality_subset the reporting is different. | |
84 If the source and target subsets are the same, then we want | |
85 to count undirected paths. But if the source and target subsets | |
86 differ -- for example, if sources is {0} and targets is {1}, | |
87 then we are only counting the paths in one direction. They are | |
88 undirected paths but we are counting them in a directed way. | |
89 To count them as undirected paths, each should count as half a path. | |
90 | |
91 References | |
92 ---------- | |
93 .. [1] Ulrik Brandes, A Faster Algorithm for Betweenness Centrality. | |
94 Journal of Mathematical Sociology 25(2):163-177, 2001. | |
95 http://www.inf.uni-konstanz.de/algo/publications/b-fabc-01.pdf | |
96 .. [2] Ulrik Brandes: On Variants of Shortest-Path Betweenness | |
97 Centrality and their Generic Computation. | |
98 Social Networks 30(2):136-145, 2008. | |
99 http://www.inf.uni-konstanz.de/algo/publications/b-vspbc-08.pdf | |
100 """ | |
101 b = dict.fromkeys(G, 0.0) # b[v]=0 for v in G | |
102 for s in sources: | |
103 # single source shortest paths | |
104 if weight is None: # use BFS | |
105 S, P, sigma = shortest_path(G, s) | |
106 else: # use Dijkstra's algorithm | |
107 S, P, sigma = dijkstra(G, s, weight) | |
108 b = _accumulate_subset(b, S, P, sigma, s, targets) | |
109 b = _rescale(b, len(G), normalized=normalized, directed=G.is_directed()) | |
110 return b | |
111 | |
112 | |
113 def edge_betweenness_centrality_subset( | |
114 G, sources, targets, normalized=False, weight=None | |
115 ): | |
116 r"""Compute betweenness centrality for edges for a subset of nodes. | |
117 | |
118 .. math:: | |
119 | |
120 c_B(v) =\sum_{s\in S,t \in T} \frac{\sigma(s, t|e)}{\sigma(s, t)} | |
121 | |
122 where $S$ is the set of sources, $T$ is the set of targets, | |
123 $\sigma(s, t)$ is the number of shortest $(s, t)$-paths, | |
124 and $\sigma(s, t|e)$ is the number of those paths | |
125 passing through edge $e$ [2]_. | |
126 | |
127 Parameters | |
128 ---------- | |
129 G : graph | |
130 A networkx graph. | |
131 | |
132 sources: list of nodes | |
133 Nodes to use as sources for shortest paths in betweenness | |
134 | |
135 targets: list of nodes | |
136 Nodes to use as targets for shortest paths in betweenness | |
137 | |
138 normalized : bool, optional | |
139 If True the betweenness values are normalized by `2/(n(n-1))` | |
140 for graphs, and `1/(n(n-1))` for directed graphs where `n` | |
141 is the number of nodes in G. | |
142 | |
143 weight : None or string, optional (default=None) | |
144 If None, all edge weights are considered equal. | |
145 Otherwise holds the name of the edge attribute used as weight. | |
146 | |
147 Returns | |
148 ------- | |
149 edges : dictionary | |
150 Dictionary of edges with Betweenness centrality as the value. | |
151 | |
152 See Also | |
153 -------- | |
154 betweenness_centrality | |
155 edge_load | |
156 | |
157 Notes | |
158 ----- | |
159 The basic algorithm is from [1]_. | |
160 | |
161 For weighted graphs the edge weights must be greater than zero. | |
162 Zero edge weights can produce an infinite number of equal length | |
163 paths between pairs of nodes. | |
164 | |
165 The normalization might seem a little strange but it is the same | |
166 as in edge_betweenness_centrality() and is designed to make | |
167 edge_betweenness_centrality(G) be the same as | |
168 edge_betweenness_centrality_subset(G,sources=G.nodes(),targets=G.nodes()). | |
169 | |
170 References | |
171 ---------- | |
172 .. [1] Ulrik Brandes, A Faster Algorithm for Betweenness Centrality. | |
173 Journal of Mathematical Sociology 25(2):163-177, 2001. | |
174 http://www.inf.uni-konstanz.de/algo/publications/b-fabc-01.pdf | |
175 .. [2] Ulrik Brandes: On Variants of Shortest-Path Betweenness | |
176 Centrality and their Generic Computation. | |
177 Social Networks 30(2):136-145, 2008. | |
178 http://www.inf.uni-konstanz.de/algo/publications/b-vspbc-08.pdf | |
179 """ | |
180 b = dict.fromkeys(G, 0.0) # b[v]=0 for v in G | |
181 b.update(dict.fromkeys(G.edges(), 0.0)) # b[e] for e in G.edges() | |
182 for s in sources: | |
183 # single source shortest paths | |
184 if weight is None: # use BFS | |
185 S, P, sigma = shortest_path(G, s) | |
186 else: # use Dijkstra's algorithm | |
187 S, P, sigma = dijkstra(G, s, weight) | |
188 b = _accumulate_edges_subset(b, S, P, sigma, s, targets) | |
189 for n in G: # remove nodes to only return edges | |
190 del b[n] | |
191 b = _rescale_e(b, len(G), normalized=normalized, directed=G.is_directed()) | |
192 return b | |
193 | |
194 | |
195 # obsolete name | |
196 def betweenness_centrality_source(G, normalized=True, weight=None, sources=None): | |
197 msg = "betweenness_centrality_source --> betweenness_centrality_subset" | |
198 warnings.warn(msg, DeprecationWarning) | |
199 if sources is None: | |
200 sources = G.nodes() | |
201 targets = list(G) | |
202 return betweenness_centrality_subset(G, sources, targets, normalized, weight) | |
203 | |
204 | |
205 def _accumulate_subset(betweenness, S, P, sigma, s, targets): | |
206 delta = dict.fromkeys(S, 0.0) | |
207 target_set = set(targets) - {s} | |
208 while S: | |
209 w = S.pop() | |
210 if w in target_set: | |
211 coeff = (delta[w] + 1.0) / sigma[w] | |
212 else: | |
213 coeff = delta[w] / sigma[w] | |
214 for v in P[w]: | |
215 delta[v] += sigma[v] * coeff | |
216 if w != s: | |
217 betweenness[w] += delta[w] | |
218 return betweenness | |
219 | |
220 | |
221 def _accumulate_edges_subset(betweenness, S, P, sigma, s, targets): | |
222 """edge_betweenness_centrality_subset helper.""" | |
223 delta = dict.fromkeys(S, 0) | |
224 target_set = set(targets) | |
225 while S: | |
226 w = S.pop() | |
227 for v in P[w]: | |
228 if w in target_set: | |
229 c = (sigma[v] / sigma[w]) * (1.0 + delta[w]) | |
230 else: | |
231 c = delta[w] / len(P[w]) | |
232 if (v, w) not in betweenness: | |
233 betweenness[(w, v)] += c | |
234 else: | |
235 betweenness[(v, w)] += c | |
236 delta[v] += c | |
237 if w != s: | |
238 betweenness[w] += delta[w] | |
239 return betweenness | |
240 | |
241 | |
242 def _rescale(betweenness, n, normalized, directed=False): | |
243 """betweenness_centrality_subset helper.""" | |
244 if normalized: | |
245 if n <= 2: | |
246 scale = None # no normalization b=0 for all nodes | |
247 else: | |
248 scale = 1.0 / ((n - 1) * (n - 2)) | |
249 else: # rescale by 2 for undirected graphs | |
250 if not directed: | |
251 scale = 0.5 | |
252 else: | |
253 scale = None | |
254 if scale is not None: | |
255 for v in betweenness: | |
256 betweenness[v] *= scale | |
257 return betweenness | |
258 | |
259 | |
260 def _rescale_e(betweenness, n, normalized, directed=False): | |
261 """edge_betweenness_centrality_subset helper.""" | |
262 if normalized: | |
263 if n <= 1: | |
264 scale = None # no normalization b=0 for all nodes | |
265 else: | |
266 scale = 1.0 / (n * (n - 1)) | |
267 else: # rescale by 2 for undirected graphs | |
268 if not directed: | |
269 scale = 0.5 | |
270 else: | |
271 scale = None | |
272 if scale is not None: | |
273 for v in betweenness: | |
274 betweenness[v] *= scale | |
275 return betweenness |