o 3ήc=@sdZddlZddlmZddlmZgdZedddZd d Z dd d Z dd dZ dddZ dddZ dddZededddZededddZdS)u Find the k-cores of a graph. The k-core is found by recursively pruning nodes with degrees less than k. See the following references for details: An O(m) Algorithm for Cores Decomposition of Networks Vladimir Batagelj and Matjaz Zaversnik, 2003. https://arxiv.org/abs/cs.DS/0310049 Generalized Cores Vladimir Batagelj and Matjaz Zaversnik, 2002. https://arxiv.org/pdf/cs/0202039 For directed graphs a more general notion is that of D-cores which looks at (k, l) restrictions on (in, out) degree. The (k, k) D-core is the k-core. D-cores: Measuring Collaboration of Directed Graphs Based on Degeneracy Christos Giatsidis, Dimitrios M. Thilikos, Michalis Vazirgiannis, ICDM 2011. http://www.graphdegeneracy.org/dcores_ICDM_2011.pdf Multi-scale structure and topological anomaly detection via a new network statistic: The onion decomposition L. Hébert-Dufresne, J. A. Grochow, and A. Allard Scientific Reports 6, 31708 (2016) http://doi.org/10.1038/srep31708 N) NetworkXError)not_implemented_for) core_number find_coresk_corek_shellk_crustk_coronak_truss onion_layers multigraphcsDtdkr d}t|t}t||jd}dg}d}t|D]\}}|||kr=||g|||||}q#ddt|D}|} fddD} |D]K}| |D]D} | | | |kr| |  ||| } || | } | || <| ||| <|| || || <|| <|| | d7<| | d8<qZqT| S)aReturns the core number for each vertex. A k-core is a maximal subgraph that contains nodes of degree k or more. The core number of a node is the largest value k of a k-core containing that node. Parameters ---------- G : NetworkX graph A graph or directed graph Returns ------- core_number : dictionary A dictionary keyed by node to the core number. Raises ------ NetworkXError The k-core is not implemented for graphs with self loops or parallel edges. Notes ----- Not implemented for graphs with parallel edges or self loops. For directed graphs the node degree is defined to be the in-degree + out-degree. References ---------- .. [1] An O(m) Algorithm for Cores Decomposition of Networks Vladimir Batagelj and Matjaz Zaversnik, 2003. https://arxiv.org/abs/cs.DS/0310049 rzlInput graph has self loops which is not permitted; Consider using G.remove_edges_from(nx.selfloop_edges(G)).keycSsi|]\}}||qSr).0posvrr?/tmp/pip-target-vg8gfxp4/lib/python/networkx/algorithms/core.py dszcore_number..ci|] }|tt|qSrlistnx all_neighborsrrGrrrg) rnumber_of_selfloopsrdictdegreesortedget enumerateextendremove)rmsgdegreesnodesbin_boundaries curr_degreeirnode_poscorenbrsur bin_startrrrr/s<&      rcCs&ddl}d}|j|tddt|S)Nrz find_cores is deprecated as of version 2.7 and will be removed in version 3.0. The find_cores function is renamed core_number ) stacklevel)warningswarnDeprecationWarningrr)rr4r'rrrrvs  rcsHdurt|durtfddD}||S)aReturns the subgraph induced by nodes passing filter `k_filter`. Parameters ---------- G : NetworkX graph The graph or directed graph to process k_filter : filter function This function filters the nodes chosen. It takes three inputs: A node of G, the filter's cutoff, and the core dict of the graph. The function should return a Boolean value. k : int, optional The order of the core. If not specified use the max core number. This value is used as the cutoff for the filter. core : dict, optional Precomputed core numbers keyed by node for the graph `G`. If not specified, the core numbers will be computed from `G`. Nc3s |] }|r|VqdSNrrr.kk_filterrr z!_core_subgraph..)rmaxvaluessubgraphcopy)rr:r9r.r)rr8r_core_subgraphs  rAcCdd}t||||S)aJReturns the k-core of G. A k-core is a maximal subgraph that contains nodes of degree k or more. Parameters ---------- G : NetworkX graph A graph or directed graph k : int, optional The order of the core. If not specified return the main core. core_number : dictionary, optional Precomputed core numbers for the graph G. Returns ------- G : NetworkX graph The k-core subgraph Raises ------ NetworkXError The k-core is not defined for graphs with self loops or parallel edges. Notes ----- The main core is the core with the largest degree. Not implemented for graphs with parallel edges or self loops. For directed graphs the node degree is defined to be the in-degree + out-degree. Graph, node, and edge attributes are copied to the subgraph. See Also -------- core_number References ---------- .. [1] An O(m) Algorithm for Cores Decomposition of Networks Vladimir Batagelj and Matjaz Zaversnik, 2003. https://arxiv.org/abs/cs.DS/0310049 cSs |||kSr7rrr9crrrr: zk_core..k_filterrArr9rr:rrrrs.rcCrB)a7Returns the k-shell of G. The k-shell is the subgraph induced by nodes with core number k. That is, nodes in the k-core that are not in the (k+1)-core. Parameters ---------- G : NetworkX graph A graph or directed graph. k : int, optional The order of the shell. If not specified return the outer shell. core_number : dictionary, optional Precomputed core numbers for the graph G. Returns ------- G : NetworkX graph The k-shell subgraph Raises ------ NetworkXError The k-shell is not implemented for graphs with self loops or parallel edges. Notes ----- This is similar to k_corona but in that case only neighbors in the k-core are considered. Not implemented for graphs with parallel edges or self loops. For directed graphs the node degree is defined to be the in-degree + out-degree. Graph, node, and edge attributes are copied to the subgraph. See Also -------- core_number k_corona References ---------- .. [1] A model of Internet topology using k-shell decomposition Shai Carmi, Shlomo Havlin, Scott Kirkpatrick, Yuval Shavitt, and Eran Shir, PNAS July 3, 2007 vol. 104 no. 27 11150-11154 http://www.pnas.org/content/104/27/11150.full cSs |||kSr7rrCrrrr:rEzk_shell..k_filterrFrGrrrrs5rcsLdur t|durtdfddD}||S)abReturns the k-crust of G. The k-crust is the graph G with the edges of the k-core removed and isolated nodes found after the removal of edges are also removed. Parameters ---------- G : NetworkX graph A graph or directed graph. k : int, optional The order of the shell. If not specified return the main crust. core_number : dictionary, optional Precomputed core numbers for the graph G. Returns ------- G : NetworkX graph The k-crust subgraph Raises ------ NetworkXError The k-crust is not implemented for graphs with self loops or parallel edges. Notes ----- This definition of k-crust is different than the definition in [1]_. The k-crust in [1]_ is equivalent to the k+1 crust of this algorithm. Not implemented for graphs with parallel edges or self loops. For directed graphs the node degree is defined to be the in-degree + out-degree. Graph, node, and edge attributes are copied to the subgraph. See Also -------- core_number References ---------- .. [1] A model of Internet topology using k-shell decomposition Shai Carmi, Shlomo Havlin, Scott Kirkpatrick, Yuval Shavitt, and Eran Shir, PNAS July 3, 2007 vol. 104 no. 27 11150-11154 http://www.pnas.org/content/104/27/11150.full Nrc3s |] }|kr|VqdSr7rrrr9rrr;Cr<zk_crust..)rrr=r>r?r@)rr9rr)rrHrr s 3 rcsfdd}t|||S)aReturns the k-corona of G. The k-corona is the subgraph of nodes in the k-core which have exactly k neighbours in the k-core. Parameters ---------- G : NetworkX graph A graph or directed graph k : int The order of the corona. core_number : dictionary, optional Precomputed core numbers for the graph G. Returns ------- G : NetworkX graph The k-corona subgraph Raises ------ NetworkXError The k-cornoa is not defined for graphs with self loops or parallel edges. Notes ----- Not implemented for graphs with parallel edges or self loops. For directed graphs the node degree is defined to be the in-degree + out-degree. Graph, node, and edge attributes are copied to the subgraph. See Also -------- core_number References ---------- .. [1] k -core (bootstrap) percolation on complex networks: Critical phenomena and nonlocal effects, A. V. Goltsev, S. N. Dorogovtsev, and J. F. F. Mendes, Phys. Rev. E 73, 056101 (2006) http://link.aps.org/doi/10.1103/PhysRevE.73.056101 cs,|kotfdd|DkS)Nc3s |] }|krdVqdS)rNr)rwrDr9rrr;xr<z)k_corona..func..)sumrCrrJrfuncws,zk_corona..funcrF)rr9rrLrrrr Gs 0r directedc s|}d}|dkr[d}g}t|D]0}t||}|fdd|D}|D]}t|t||@|dkrB|||fq+q||t|}|tt ||dks |S)atReturns the k-truss of `G`. The k-truss is the maximal induced subgraph of `G` which contains at least three vertices where every edge is incident to at least `k-2` triangles. Parameters ---------- G : NetworkX graph An undirected graph k : int The order of the truss Returns ------- H : NetworkX graph The k-truss subgraph Raises ------ NetworkXError The k-truss is not defined for graphs with self loops or parallel edges or directed graphs. Notes ----- A k-clique is a (k-2)-truss and a k-truss is a (k+1)-core. Not implemented for digraphs or graphs with parallel edges or self loops. Graph, node, and edge attributes are copied to the subgraph. K-trusses were originally defined in [2] which states that the k-truss is the maximal induced subgraph where each edge belongs to at least `k-2` triangles. A more recent paper, [1], uses a slightly different definition requiring that each edge belong to at least `k` triangles. This implementation uses the original definition of `k-2` triangles. References ---------- .. [1] Bounds and Algorithms for k-truss. Paul Burkhardt, Vance Faber, David G. Harris, 2018. https://arxiv.org/abs/1806.05523v2 .. [2] Trusses: Cohesive Subgraphs for Social Network Analysis. Jonathan Cohen, 2005. rrcsg|]}|vr|qSrrrseenrr szk_truss..r2) r@setaddlenappendremove_edges_fromremove_nodes_fromrrisolates) rr9H n_droppedto_dropr0nbrs_unew_nbrsrrrNrr }s(0   r c s>tdkr d}t|i}fddD}t}d}d}ddtD}t|dkrB|D] }|||<||q4d}t|dkrt||j d } || d} | |kr[| }g} | D]} || |krin| | q_| D]!}|||<||D]} ||  ||| d|| <q{||qq|d}t|dksH|S) ulReturns the layer of each vertex in an onion decomposition of the graph. The onion decomposition refines the k-core decomposition by providing information on the internal organization of each k-shell. It is usually used alongside the `core numbers`. Parameters ---------- G : NetworkX graph A simple graph without self loops or parallel edges Returns ------- od_layers : dictionary A dictionary keyed by vertex to the onion layer. The layers are contiguous integers starting at 1. Raises ------ NetworkXError The onion decomposition is not implemented for graphs with self loops or parallel edges or for directed graphs. Notes ----- Not implemented for graphs with parallel edges or self loops. Not implemented for directed graphs. See Also -------- core_number References ---------- .. [1] Multi-scale structure and topological anomaly detection via a new network statistic: The onion decomposition L. Hébert-Dufresne, J. A. Grochow, and A. Allard Scientific Reports 6, 31708 (2016) http://doi.org/10.1038/srep31708 .. [2] Percolation and the effective structure of complex networks A. Allard and L. Hébert-Dufresne Physical Review X 9, 011023 (2019) http://doi.org/10.1103/PhysRevX.9.011023 rzqInput graph contains self loops which is not permitted; Consider using G.remove_edges_from(nx.selfloop_edges(G)).crrrrrrrrrz onion_layers..rcSsg|]}|qSrrrrrrrPsz onion_layers..r2r ) rrrr r!rWrSpopr"r#rTr&) rr' od_layers neighborsr( current_core current_layerisolated_nodesrr) min_degree this_layernrrrr sD0          r )NNr7)__doc__networkxrnetworkx.exceptionrnetworkx.utilsr__all__rrrArrrr r r rrrrs&   F  4 ; ;6 C