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