Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/centrality/group.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 """Group centrality measures.""" | |
2 from itertools import combinations | |
3 | |
4 | |
5 import networkx as nx | |
6 from networkx.utils.decorators import not_implemented_for | |
7 | |
8 | |
9 __all__ = [ | |
10 "group_betweenness_centrality", | |
11 "group_closeness_centrality", | |
12 "group_degree_centrality", | |
13 "group_in_degree_centrality", | |
14 "group_out_degree_centrality", | |
15 ] | |
16 | |
17 | |
18 def group_betweenness_centrality(G, C, normalized=True, weight=None): | |
19 r"""Compute the group betweenness centrality for a group of nodes. | |
20 | |
21 Group betweenness centrality of a group of nodes $C$ is the sum of the | |
22 fraction of all-pairs shortest paths that pass through any vertex in $C$ | |
23 | |
24 .. math:: | |
25 | |
26 c_B(C) =\sum_{s,t \in V-C; s<t} \frac{\sigma(s, t|C)}{\sigma(s, t)} | |
27 | |
28 where $V$ is the set of nodes, $\sigma(s, t)$ is the number of | |
29 shortest $(s, t)$-paths, and $\sigma(s, t|C)$ is the number of | |
30 those paths passing through some node in group $C$. Note that | |
31 $(s, t)$ are not members of the group ($V-C$ is the set of nodes | |
32 in $V$ that are not in $C$). | |
33 | |
34 Parameters | |
35 ---------- | |
36 G : graph | |
37 A NetworkX graph. | |
38 | |
39 C : list or set | |
40 C is a group of nodes which belong to G, for which group betweenness | |
41 centrality is to be calculated. | |
42 | |
43 normalized : bool, optional | |
44 If True, group betweenness is normalized by `2/((|V|-|C|)(|V|-|C|-1))` | |
45 for graphs and `1/((|V|-|C|)(|V|-|C|-1))` for directed graphs where `|V|` | |
46 is the number of nodes in G and `|C|` is the number of nodes in C. | |
47 | |
48 weight : None or string, optional (default=None) | |
49 If None, all edge weights are considered equal. | |
50 Otherwise holds the name of the edge attribute used as weight. | |
51 | |
52 Raises | |
53 ------ | |
54 NodeNotFound | |
55 If node(s) in C are not present in G. | |
56 | |
57 Returns | |
58 ------- | |
59 betweenness : float | |
60 Group betweenness centrality of the group C. | |
61 | |
62 See Also | |
63 -------- | |
64 betweenness_centrality | |
65 | |
66 Notes | |
67 ----- | |
68 The measure is described in [1]_. | |
69 The algorithm is an extension of the one proposed by Ulrik Brandes for | |
70 betweenness centrality of nodes. Group betweenness is also mentioned in | |
71 his paper [2]_ along with the algorithm. The importance of the measure is | |
72 discussed in [3]_. | |
73 | |
74 The number of nodes in the group must be a maximum of n - 2 where `n` | |
75 is the total number of nodes in the graph. | |
76 | |
77 For weighted graphs the edge weights must be greater than zero. | |
78 Zero edge weights can produce an infinite number of equal length | |
79 paths between pairs of nodes. | |
80 | |
81 References | |
82 ---------- | |
83 .. [1] M G Everett and S P Borgatti: | |
84 The Centrality of Groups and Classes. | |
85 Journal of Mathematical Sociology. 23(3): 181-201. 1999. | |
86 http://www.analytictech.com/borgatti/group_centrality.htm | |
87 .. [2] Ulrik Brandes: | |
88 On Variants of Shortest-Path Betweenness | |
89 Centrality and their Generic Computation. | |
90 Social Networks 30(2):136-145, 2008. | |
91 http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.72.9610&rep=rep1&type=pdf | |
92 .. [3] Sourav Medya et. al.: | |
93 Group Centrality Maximization via Network Design. | |
94 SIAM International Conference on Data Mining, SDM 2018, 126–134. | |
95 https://sites.cs.ucsb.edu/~arlei/pubs/sdm18.pdf | |
96 """ | |
97 betweenness = 0 # initialize betweenness to 0 | |
98 V = set(G) # set of nodes in G | |
99 C = set(C) # set of nodes in C (group) | |
100 if len(C - V) != 0: # element(s) of C not in V | |
101 raise nx.NodeNotFound( | |
102 "The node(s) " + str(list(C - V)) + " are not " "in the graph." | |
103 ) | |
104 V_C = V - C # set of nodes in V but not in C | |
105 # accumulation | |
106 for pair in combinations(V_C, 2): # (s, t) pairs of V_C | |
107 try: | |
108 paths = 0 | |
109 paths_through_C = 0 | |
110 for path in nx.all_shortest_paths( | |
111 G, source=pair[0], target=pair[1], weight=weight | |
112 ): | |
113 if set(path) & C: | |
114 paths_through_C += 1 | |
115 paths += 1 | |
116 betweenness += paths_through_C / paths | |
117 except nx.exception.NetworkXNoPath: | |
118 betweenness += 0 | |
119 # rescaling | |
120 v, c = len(G), len(C) | |
121 if normalized: | |
122 scale = 1 / ((v - c) * (v - c - 1)) | |
123 if not G.is_directed(): | |
124 scale *= 2 | |
125 else: | |
126 scale = None | |
127 if scale is not None: | |
128 betweenness *= scale | |
129 return betweenness | |
130 | |
131 | |
132 def group_closeness_centrality(G, S, weight=None): | |
133 r"""Compute the group closeness centrality for a group of nodes. | |
134 | |
135 Group closeness centrality of a group of nodes $S$ is a measure | |
136 of how close the group is to the other nodes in the graph. | |
137 | |
138 .. math:: | |
139 | |
140 c_{close}(S) = \frac{|V-S|}{\sum_{v \in V-S} d_{S, v}} | |
141 | |
142 d_{S, v} = min_{u \in S} (d_{u, v}) | |
143 | |
144 where $V$ is the set of nodes, $d_{S, v}$ is the distance of | |
145 the group $S$ from $v$ defined as above. ($V-S$ is the set of nodes | |
146 in $V$ that are not in $S$). | |
147 | |
148 Parameters | |
149 ---------- | |
150 G : graph | |
151 A NetworkX graph. | |
152 | |
153 S : list or set | |
154 S is a group of nodes which belong to G, for which group closeness | |
155 centrality is to be calculated. | |
156 | |
157 weight : None or string, optional (default=None) | |
158 If None, all edge weights are considered equal. | |
159 Otherwise holds the name of the edge attribute used as weight. | |
160 | |
161 Raises | |
162 ------ | |
163 NodeNotFound | |
164 If node(s) in S are not present in G. | |
165 | |
166 Returns | |
167 ------- | |
168 closeness : float | |
169 Group closeness centrality of the group S. | |
170 | |
171 See Also | |
172 -------- | |
173 closeness_centrality | |
174 | |
175 Notes | |
176 ----- | |
177 The measure was introduced in [1]_. | |
178 The formula implemented here is described in [2]_. | |
179 | |
180 Higher values of closeness indicate greater centrality. | |
181 | |
182 It is assumed that 1 / 0 is 0 (required in the case of directed graphs, | |
183 or when a shortest path length is 0). | |
184 | |
185 The number of nodes in the group must be a maximum of n - 1 where `n` | |
186 is the total number of nodes in the graph. | |
187 | |
188 For directed graphs, the incoming distance is utilized here. To use the | |
189 outward distance, act on `G.reverse()`. | |
190 | |
191 For weighted graphs the edge weights must be greater than zero. | |
192 Zero edge weights can produce an infinite number of equal length | |
193 paths between pairs of nodes. | |
194 | |
195 References | |
196 ---------- | |
197 .. [1] M G Everett and S P Borgatti: | |
198 The Centrality of Groups and Classes. | |
199 Journal of Mathematical Sociology. 23(3): 181-201. 1999. | |
200 http://www.analytictech.com/borgatti/group_centrality.htm | |
201 .. [2] J. Zhao et. al.: | |
202 Measuring and Maximizing Group Closeness Centrality over | |
203 Disk Resident Graphs. | |
204 WWWConference Proceedings, 2014. 689-694. | |
205 http://wwwconference.org/proceedings/www2014/companion/p689.pdf | |
206 """ | |
207 if G.is_directed(): | |
208 G = G.reverse() # reverse view | |
209 closeness = 0 # initialize to 0 | |
210 V = set(G) # set of nodes in G | |
211 S = set(S) # set of nodes in group S | |
212 V_S = V - S # set of nodes in V but not S | |
213 shortest_path_lengths = nx.multi_source_dijkstra_path_length(G, S, weight=weight) | |
214 # accumulation | |
215 for v in V_S: | |
216 try: | |
217 closeness += shortest_path_lengths[v] | |
218 except KeyError: # no path exists | |
219 closeness += 0 | |
220 try: | |
221 closeness = len(V_S) / closeness | |
222 except ZeroDivisionError: # 1 / 0 assumed as 0 | |
223 closeness = 0 | |
224 return closeness | |
225 | |
226 | |
227 def group_degree_centrality(G, S): | |
228 """Compute the group degree centrality for a group of nodes. | |
229 | |
230 Group degree centrality of a group of nodes $S$ is the fraction | |
231 of non-group members connected to group members. | |
232 | |
233 Parameters | |
234 ---------- | |
235 G : graph | |
236 A NetworkX graph. | |
237 | |
238 S : list or set | |
239 S is a group of nodes which belong to G, for which group degree | |
240 centrality is to be calculated. | |
241 | |
242 Raises | |
243 ------ | |
244 NetworkXError | |
245 If node(s) in S are not in G. | |
246 | |
247 Returns | |
248 ------- | |
249 centrality : float | |
250 Group degree centrality of the group S. | |
251 | |
252 See Also | |
253 -------- | |
254 degree_centrality | |
255 group_in_degree_centrality | |
256 group_out_degree_centrality | |
257 | |
258 Notes | |
259 ----- | |
260 The measure was introduced in [1]_. | |
261 | |
262 The number of nodes in the group must be a maximum of n - 1 where `n` | |
263 is the total number of nodes in the graph. | |
264 | |
265 References | |
266 ---------- | |
267 .. [1] M G Everett and S P Borgatti: | |
268 The Centrality of Groups and Classes. | |
269 Journal of Mathematical Sociology. 23(3): 181-201. 1999. | |
270 http://www.analytictech.com/borgatti/group_centrality.htm | |
271 """ | |
272 centrality = len(set().union(*list(set(G.neighbors(i)) for i in S)) - set(S)) | |
273 centrality /= len(G.nodes()) - len(S) | |
274 return centrality | |
275 | |
276 | |
277 @not_implemented_for("undirected") | |
278 def group_in_degree_centrality(G, S): | |
279 """Compute the group in-degree centrality for a group of nodes. | |
280 | |
281 Group in-degree centrality of a group of nodes $S$ is the fraction | |
282 of non-group members connected to group members by incoming edges. | |
283 | |
284 Parameters | |
285 ---------- | |
286 G : graph | |
287 A NetworkX graph. | |
288 | |
289 S : list or set | |
290 S is a group of nodes which belong to G, for which group in-degree | |
291 centrality is to be calculated. | |
292 | |
293 Returns | |
294 ------- | |
295 centrality : float | |
296 Group in-degree centrality of the group S. | |
297 | |
298 Raises | |
299 ------ | |
300 NetworkXNotImplemented | |
301 If G is undirected. | |
302 | |
303 NodeNotFound | |
304 If node(s) in S are not in G. | |
305 | |
306 See Also | |
307 -------- | |
308 degree_centrality | |
309 group_degree_centrality | |
310 group_out_degree_centrality | |
311 | |
312 Notes | |
313 ----- | |
314 The number of nodes in the group must be a maximum of n - 1 where `n` | |
315 is the total number of nodes in the graph. | |
316 | |
317 `G.neighbors(i)` gives nodes with an outward edge from i, in a DiGraph, | |
318 so for group in-degree centrality, the reverse graph is used. | |
319 """ | |
320 return group_degree_centrality(G.reverse(), S) | |
321 | |
322 | |
323 @not_implemented_for("undirected") | |
324 def group_out_degree_centrality(G, S): | |
325 """Compute the group out-degree centrality for a group of nodes. | |
326 | |
327 Group out-degree centrality of a group of nodes $S$ is the fraction | |
328 of non-group members connected to group members by outgoing edges. | |
329 | |
330 Parameters | |
331 ---------- | |
332 G : graph | |
333 A NetworkX graph. | |
334 | |
335 S : list or set | |
336 S is a group of nodes which belong to G, for which group in-degree | |
337 centrality is to be calculated. | |
338 | |
339 Returns | |
340 ------- | |
341 centrality : float | |
342 Group out-degree centrality of the group S. | |
343 | |
344 Raises | |
345 ------ | |
346 NetworkXNotImplemented | |
347 If G is undirected. | |
348 | |
349 NodeNotFound | |
350 If node(s) in S are not in G. | |
351 | |
352 See Also | |
353 -------- | |
354 degree_centrality | |
355 group_degree_centrality | |
356 group_in_degree_centrality | |
357 | |
358 Notes | |
359 ----- | |
360 The number of nodes in the group must be a maximum of n - 1 where `n` | |
361 is the total number of nodes in the graph. | |
362 | |
363 `G.neighbors(i)` gives nodes with an outward edge from i, in a DiGraph, | |
364 so for group out-degree centrality, the graph itself is used. | |
365 """ | |
366 return group_degree_centrality(G, S) |