Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/core.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 """ | |
2 Find the k-cores of a graph. | |
3 | |
4 The k-core is found by recursively pruning nodes with degrees less than k. | |
5 | |
6 See the following references for details: | |
7 | |
8 An O(m) Algorithm for Cores Decomposition of Networks | |
9 Vladimir Batagelj and Matjaz Zaversnik, 2003. | |
10 https://arxiv.org/abs/cs.DS/0310049 | |
11 | |
12 Generalized Cores | |
13 Vladimir Batagelj and Matjaz Zaversnik, 2002. | |
14 https://arxiv.org/pdf/cs/0202039 | |
15 | |
16 For directed graphs a more general notion is that of D-cores which | |
17 looks at (k, l) restrictions on (in, out) degree. The (k, k) D-core | |
18 is the k-core. | |
19 | |
20 D-cores: Measuring Collaboration of Directed Graphs Based on Degeneracy | |
21 Christos Giatsidis, Dimitrios M. Thilikos, Michalis Vazirgiannis, ICDM 2011. | |
22 http://www.graphdegeneracy.org/dcores_ICDM_2011.pdf | |
23 | |
24 Multi-scale structure and topological anomaly detection via a new network \ | |
25 statistic: The onion decomposition | |
26 L. Hébert-Dufresne, J. A. Grochow, and A. Allard | |
27 Scientific Reports 6, 31708 (2016) | |
28 http://doi.org/10.1038/srep31708 | |
29 | |
30 """ | |
31 import networkx as nx | |
32 from networkx.exception import NetworkXError | |
33 from networkx.utils import not_implemented_for | |
34 | |
35 __all__ = [ | |
36 "core_number", | |
37 "find_cores", | |
38 "k_core", | |
39 "k_shell", | |
40 "k_crust", | |
41 "k_corona", | |
42 "k_truss", | |
43 "onion_layers", | |
44 ] | |
45 | |
46 | |
47 @not_implemented_for("multigraph") | |
48 def core_number(G): | |
49 """Returns the core number for each vertex. | |
50 | |
51 A k-core is a maximal subgraph that contains nodes of degree k or more. | |
52 | |
53 The core number of a node is the largest value k of a k-core containing | |
54 that node. | |
55 | |
56 Parameters | |
57 ---------- | |
58 G : NetworkX graph | |
59 A graph or directed graph | |
60 | |
61 Returns | |
62 ------- | |
63 core_number : dictionary | |
64 A dictionary keyed by node to the core number. | |
65 | |
66 Raises | |
67 ------ | |
68 NetworkXError | |
69 The k-core is not implemented for graphs with self loops | |
70 or parallel edges. | |
71 | |
72 Notes | |
73 ----- | |
74 Not implemented for graphs with parallel edges or self loops. | |
75 | |
76 For directed graphs the node degree is defined to be the | |
77 in-degree + out-degree. | |
78 | |
79 References | |
80 ---------- | |
81 .. [1] An O(m) Algorithm for Cores Decomposition of Networks | |
82 Vladimir Batagelj and Matjaz Zaversnik, 2003. | |
83 https://arxiv.org/abs/cs.DS/0310049 | |
84 """ | |
85 if nx.number_of_selfloops(G) > 0: | |
86 msg = ( | |
87 "Input graph has self loops which is not permitted; " | |
88 "Consider using G.remove_edges_from(nx.selfloop_edges(G))." | |
89 ) | |
90 raise NetworkXError(msg) | |
91 degrees = dict(G.degree()) | |
92 # Sort nodes by degree. | |
93 nodes = sorted(degrees, key=degrees.get) | |
94 bin_boundaries = [0] | |
95 curr_degree = 0 | |
96 for i, v in enumerate(nodes): | |
97 if degrees[v] > curr_degree: | |
98 bin_boundaries.extend([i] * (degrees[v] - curr_degree)) | |
99 curr_degree = degrees[v] | |
100 node_pos = {v: pos for pos, v in enumerate(nodes)} | |
101 # The initial guess for the core number of a node is its degree. | |
102 core = degrees | |
103 nbrs = {v: list(nx.all_neighbors(G, v)) for v in G} | |
104 for v in nodes: | |
105 for u in nbrs[v]: | |
106 if core[u] > core[v]: | |
107 nbrs[u].remove(v) | |
108 pos = node_pos[u] | |
109 bin_start = bin_boundaries[core[u]] | |
110 node_pos[u] = bin_start | |
111 node_pos[nodes[bin_start]] = pos | |
112 nodes[bin_start], nodes[pos] = nodes[pos], nodes[bin_start] | |
113 bin_boundaries[core[u]] += 1 | |
114 core[u] -= 1 | |
115 return core | |
116 | |
117 | |
118 find_cores = core_number | |
119 | |
120 | |
121 def _core_subgraph(G, k_filter, k=None, core=None): | |
122 """Returns the subgraph induced by nodes passing filter `k_filter`. | |
123 | |
124 Parameters | |
125 ---------- | |
126 G : NetworkX graph | |
127 The graph or directed graph to process | |
128 k_filter : filter function | |
129 This function filters the nodes chosen. It takes three inputs: | |
130 A node of G, the filter's cutoff, and the core dict of the graph. | |
131 The function should return a Boolean value. | |
132 k : int, optional | |
133 The order of the core. If not specified use the max core number. | |
134 This value is used as the cutoff for the filter. | |
135 core : dict, optional | |
136 Precomputed core numbers keyed by node for the graph `G`. | |
137 If not specified, the core numbers will be computed from `G`. | |
138 | |
139 """ | |
140 if core is None: | |
141 core = core_number(G) | |
142 if k is None: | |
143 k = max(core.values()) | |
144 nodes = (v for v in core if k_filter(v, k, core)) | |
145 return G.subgraph(nodes).copy() | |
146 | |
147 | |
148 def k_core(G, k=None, core_number=None): | |
149 """Returns the k-core of G. | |
150 | |
151 A k-core is a maximal subgraph that contains nodes of degree k or more. | |
152 | |
153 Parameters | |
154 ---------- | |
155 G : NetworkX graph | |
156 A graph or directed graph | |
157 k : int, optional | |
158 The order of the core. If not specified return the main core. | |
159 core_number : dictionary, optional | |
160 Precomputed core numbers for the graph G. | |
161 | |
162 Returns | |
163 ------- | |
164 G : NetworkX graph | |
165 The k-core subgraph | |
166 | |
167 Raises | |
168 ------ | |
169 NetworkXError | |
170 The k-core is not defined for graphs with self loops or parallel edges. | |
171 | |
172 Notes | |
173 ----- | |
174 The main core is the core with the largest degree. | |
175 | |
176 Not implemented for graphs with parallel edges or self loops. | |
177 | |
178 For directed graphs the node degree is defined to be the | |
179 in-degree + out-degree. | |
180 | |
181 Graph, node, and edge attributes are copied to the subgraph. | |
182 | |
183 See Also | |
184 -------- | |
185 core_number | |
186 | |
187 References | |
188 ---------- | |
189 .. [1] An O(m) Algorithm for Cores Decomposition of Networks | |
190 Vladimir Batagelj and Matjaz Zaversnik, 2003. | |
191 https://arxiv.org/abs/cs.DS/0310049 | |
192 """ | |
193 | |
194 def k_filter(v, k, c): | |
195 return c[v] >= k | |
196 | |
197 return _core_subgraph(G, k_filter, k, core_number) | |
198 | |
199 | |
200 def k_shell(G, k=None, core_number=None): | |
201 """Returns the k-shell of G. | |
202 | |
203 The k-shell is the subgraph induced by nodes with core number k. | |
204 That is, nodes in the k-core that are not in the (k+1)-core. | |
205 | |
206 Parameters | |
207 ---------- | |
208 G : NetworkX graph | |
209 A graph or directed graph. | |
210 k : int, optional | |
211 The order of the shell. If not specified return the outer shell. | |
212 core_number : dictionary, optional | |
213 Precomputed core numbers for the graph G. | |
214 | |
215 | |
216 Returns | |
217 ------- | |
218 G : NetworkX graph | |
219 The k-shell subgraph | |
220 | |
221 Raises | |
222 ------ | |
223 NetworkXError | |
224 The k-shell is not implemented for graphs with self loops | |
225 or parallel edges. | |
226 | |
227 Notes | |
228 ----- | |
229 This is similar to k_corona but in that case only neighbors in the | |
230 k-core are considered. | |
231 | |
232 Not implemented for graphs with parallel edges or self loops. | |
233 | |
234 For directed graphs the node degree is defined to be the | |
235 in-degree + out-degree. | |
236 | |
237 Graph, node, and edge attributes are copied to the subgraph. | |
238 | |
239 See Also | |
240 -------- | |
241 core_number | |
242 k_corona | |
243 | |
244 | |
245 References | |
246 ---------- | |
247 .. [1] A model of Internet topology using k-shell decomposition | |
248 Shai Carmi, Shlomo Havlin, Scott Kirkpatrick, Yuval Shavitt, | |
249 and Eran Shir, PNAS July 3, 2007 vol. 104 no. 27 11150-11154 | |
250 http://www.pnas.org/content/104/27/11150.full | |
251 """ | |
252 | |
253 def k_filter(v, k, c): | |
254 return c[v] == k | |
255 | |
256 return _core_subgraph(G, k_filter, k, core_number) | |
257 | |
258 | |
259 def k_crust(G, k=None, core_number=None): | |
260 """Returns the k-crust of G. | |
261 | |
262 The k-crust is the graph G with the k-core removed. | |
263 | |
264 Parameters | |
265 ---------- | |
266 G : NetworkX graph | |
267 A graph or directed graph. | |
268 k : int, optional | |
269 The order of the shell. If not specified return the main crust. | |
270 core_number : dictionary, optional | |
271 Precomputed core numbers for the graph G. | |
272 | |
273 Returns | |
274 ------- | |
275 G : NetworkX graph | |
276 The k-crust subgraph | |
277 | |
278 Raises | |
279 ------ | |
280 NetworkXError | |
281 The k-crust is not implemented for graphs with self loops | |
282 or parallel edges. | |
283 | |
284 Notes | |
285 ----- | |
286 This definition of k-crust is different than the definition in [1]_. | |
287 The k-crust in [1]_ is equivalent to the k+1 crust of this algorithm. | |
288 | |
289 Not implemented for graphs with parallel edges or self loops. | |
290 | |
291 For directed graphs the node degree is defined to be the | |
292 in-degree + out-degree. | |
293 | |
294 Graph, node, and edge attributes are copied to the subgraph. | |
295 | |
296 See Also | |
297 -------- | |
298 core_number | |
299 | |
300 References | |
301 ---------- | |
302 .. [1] A model of Internet topology using k-shell decomposition | |
303 Shai Carmi, Shlomo Havlin, Scott Kirkpatrick, Yuval Shavitt, | |
304 and Eran Shir, PNAS July 3, 2007 vol. 104 no. 27 11150-11154 | |
305 http://www.pnas.org/content/104/27/11150.full | |
306 """ | |
307 # Default for k is one less than in _core_subgraph, so just inline. | |
308 # Filter is c[v] <= k | |
309 if core_number is None: | |
310 core_number = find_cores(G) | |
311 if k is None: | |
312 k = max(core_number.values()) - 1 | |
313 nodes = (v for v in core_number if core_number[v] <= k) | |
314 return G.subgraph(nodes).copy() | |
315 | |
316 | |
317 def k_corona(G, k, core_number=None): | |
318 """Returns the k-corona of G. | |
319 | |
320 The k-corona is the subgraph of nodes in the k-core which have | |
321 exactly k neighbours in the k-core. | |
322 | |
323 Parameters | |
324 ---------- | |
325 G : NetworkX graph | |
326 A graph or directed graph | |
327 k : int | |
328 The order of the corona. | |
329 core_number : dictionary, optional | |
330 Precomputed core numbers for the graph G. | |
331 | |
332 Returns | |
333 ------- | |
334 G : NetworkX graph | |
335 The k-corona subgraph | |
336 | |
337 Raises | |
338 ------ | |
339 NetworkXError | |
340 The k-cornoa is not defined for graphs with self loops or | |
341 parallel edges. | |
342 | |
343 Notes | |
344 ----- | |
345 Not implemented for graphs with parallel edges or self loops. | |
346 | |
347 For directed graphs the node degree is defined to be the | |
348 in-degree + out-degree. | |
349 | |
350 Graph, node, and edge attributes are copied to the subgraph. | |
351 | |
352 See Also | |
353 -------- | |
354 core_number | |
355 | |
356 References | |
357 ---------- | |
358 .. [1] k -core (bootstrap) percolation on complex networks: | |
359 Critical phenomena and nonlocal effects, | |
360 A. V. Goltsev, S. N. Dorogovtsev, and J. F. F. Mendes, | |
361 Phys. Rev. E 73, 056101 (2006) | |
362 http://link.aps.org/doi/10.1103/PhysRevE.73.056101 | |
363 """ | |
364 | |
365 def func(v, k, c): | |
366 return c[v] == k and k == sum(1 for w in G[v] if c[w] >= k) | |
367 | |
368 return _core_subgraph(G, func, k, core_number) | |
369 | |
370 | |
371 @not_implemented_for("directed") | |
372 @not_implemented_for("multigraph") | |
373 def k_truss(G, k): | |
374 """Returns the k-truss of `G`. | |
375 | |
376 The k-truss is the maximal induced subgraph of `G` which contains at least | |
377 three vertices where every edge is incident to at least `k-2` triangles. | |
378 | |
379 Parameters | |
380 ---------- | |
381 G : NetworkX graph | |
382 An undirected graph | |
383 k : int | |
384 The order of the truss | |
385 | |
386 Returns | |
387 ------- | |
388 H : NetworkX graph | |
389 The k-truss subgraph | |
390 | |
391 Raises | |
392 ------ | |
393 NetworkXError | |
394 | |
395 The k-truss is not defined for graphs with self loops or parallel edges | |
396 or directed graphs. | |
397 | |
398 Notes | |
399 ----- | |
400 A k-clique is a (k-2)-truss and a k-truss is a (k+1)-core. | |
401 | |
402 Not implemented for digraphs or graphs with parallel edges or self loops. | |
403 | |
404 Graph, node, and edge attributes are copied to the subgraph. | |
405 | |
406 K-trusses were originally defined in [2] which states that the k-truss | |
407 is the maximal induced subgraph where each edge belongs to at least | |
408 `k-2` triangles. A more recent paper, [1], uses a slightly different | |
409 definition requiring that each edge belong to at least `k` triangles. | |
410 This implementation uses the original definition of `k-2` triangles. | |
411 | |
412 References | |
413 ---------- | |
414 .. [1] Bounds and Algorithms for k-truss. Paul Burkhardt, Vance Faber, | |
415 David G. Harris, 2018. https://arxiv.org/abs/1806.05523v2 | |
416 .. [2] Trusses: Cohesive Subgraphs for Social Network Analysis. Jonathan | |
417 Cohen, 2005. | |
418 """ | |
419 H = G.copy() | |
420 | |
421 n_dropped = 1 | |
422 while n_dropped > 0: | |
423 n_dropped = 0 | |
424 to_drop = [] | |
425 seen = set() | |
426 for u in H: | |
427 nbrs_u = set(H[u]) | |
428 seen.add(u) | |
429 new_nbrs = [v for v in nbrs_u if v not in seen] | |
430 for v in new_nbrs: | |
431 if len(nbrs_u & set(H[v])) < (k - 2): | |
432 to_drop.append((u, v)) | |
433 H.remove_edges_from(to_drop) | |
434 n_dropped = len(to_drop) | |
435 H.remove_nodes_from(list(nx.isolates(H))) | |
436 | |
437 return H | |
438 | |
439 | |
440 @not_implemented_for("multigraph") | |
441 @not_implemented_for("directed") | |
442 def onion_layers(G): | |
443 """Returns the layer of each vertex in an onion decomposition of the graph. | |
444 | |
445 The onion decomposition refines the k-core decomposition by providing | |
446 information on the internal organization of each k-shell. It is usually | |
447 used alongside the `core numbers`. | |
448 | |
449 Parameters | |
450 ---------- | |
451 G : NetworkX graph | |
452 A simple graph without self loops or parallel edges | |
453 | |
454 Returns | |
455 ------- | |
456 od_layers : dictionary | |
457 A dictionary keyed by vertex to the onion layer. The layers are | |
458 contiguous integers starting at 1. | |
459 | |
460 Raises | |
461 ------ | |
462 NetworkXError | |
463 The onion decomposition is not implemented for graphs with self loops | |
464 or parallel edges or for directed graphs. | |
465 | |
466 Notes | |
467 ----- | |
468 Not implemented for graphs with parallel edges or self loops. | |
469 | |
470 Not implemented for directed graphs. | |
471 | |
472 See Also | |
473 -------- | |
474 core_number | |
475 | |
476 References | |
477 ---------- | |
478 .. [1] Multi-scale structure and topological anomaly detection via a new | |
479 network statistic: The onion decomposition | |
480 L. Hébert-Dufresne, J. A. Grochow, and A. Allard | |
481 Scientific Reports 6, 31708 (2016) | |
482 http://doi.org/10.1038/srep31708 | |
483 .. [2] Percolation and the effective structure of complex networks | |
484 A. Allard and L. Hébert-Dufresne | |
485 Physical Review X 9, 011023 (2019) | |
486 http://doi.org/10.1103/PhysRevX.9.011023 | |
487 """ | |
488 if nx.number_of_selfloops(G) > 0: | |
489 msg = ( | |
490 "Input graph contains self loops which is not permitted; " | |
491 "Consider using G.remove_edges_from(nx.selfloop_edges(G))." | |
492 ) | |
493 raise NetworkXError(msg) | |
494 # Dictionaries to register the k-core/onion decompositions. | |
495 od_layers = {} | |
496 # Adjacency list | |
497 neighbors = {v: list(nx.all_neighbors(G, v)) for v in G} | |
498 # Effective degree of nodes. | |
499 degrees = dict(G.degree()) | |
500 # Performs the onion decomposition. | |
501 current_core = 1 | |
502 current_layer = 1 | |
503 # Sets vertices of degree 0 to layer 1, if any. | |
504 isolated_nodes = [v for v in nx.isolates(G)] | |
505 if len(isolated_nodes) > 0: | |
506 for v in isolated_nodes: | |
507 od_layers[v] = current_layer | |
508 degrees.pop(v) | |
509 current_layer = 2 | |
510 # Finds the layer for the remaining nodes. | |
511 while len(degrees) > 0: | |
512 # Sets the order for looking at nodes. | |
513 nodes = sorted(degrees, key=degrees.get) | |
514 # Sets properly the current core. | |
515 min_degree = degrees[nodes[0]] | |
516 if min_degree > current_core: | |
517 current_core = min_degree | |
518 # Identifies vertices in the current layer. | |
519 this_layer = [] | |
520 for n in nodes: | |
521 if degrees[n] > current_core: | |
522 break | |
523 this_layer.append(n) | |
524 # Identifies the core/layer of the vertices in the current layer. | |
525 for v in this_layer: | |
526 od_layers[v] = current_layer | |
527 for n in neighbors[v]: | |
528 neighbors[n].remove(v) | |
529 degrees[n] = degrees[n] - 1 | |
530 degrees.pop(v) | |
531 # Updates the layer count. | |
532 current_layer = current_layer + 1 | |
533 # Returns the dictionaries containing the onion layer of each vertices. | |
534 return od_layers |