Skip to main content
`Ctrl`+`K`

# Source code for networkx.algorithms.core

    """
    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

    """

    import networkx as nx

    __all__ = [
        "core_number",
        "k_core",
        "k_shell",
        "k_crust",
        "k_corona",
        "k_truss",
        "onion_layers",
    ]

    @nx.utils.not_implemented_for("multigraph")
    @nx._dispatchable
    def core_number(G):
        """Returns the core number for each node.

        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
           An undirected or directed graph

        Returns
        -------
        core_number : dictionary
           A dictionary keyed by node to the core number.

        Raises
        ------
        NetworkXNotImplemented
            If `G` is a multigraph or contains self loops.

        Notes
        -----
        For directed graphs the node degree is defined to be the
        in-degree + out-degree.

        Examples
        --------
        >>> degrees = [0, 1, 2, 2, 2, 2, 3]
        >>> H = nx.havel_hakimi_graph(degrees)
        >>> nx.core_number(H)
        {0: 1, 1: 2, 2: 2, 3: 2, 4: 1, 5: 2, 6: 0}
        >>> G = nx.DiGraph()
        >>> G.add_edges_from([(1, 2), (2, 1), (2, 3), (2, 4), (3, 4), (4, 3)])
        >>> nx.core_number(G)
        {1: 2, 2: 2, 3: 2, 4: 2}

        References
        ----------
        .. [1] An O(m) Algorithm for Cores Decomposition of Networks
           Vladimir Batagelj and Matjaz Zaversnik, 2003.
           https://arxiv.org/abs/cs.DS/0310049
        """
        if nx.number_of_selfloops(G) > 0:
            msg = (
                "Input graph has self loops which is not permitted; "
                "Consider using G.remove_edges_from(nx.selfloop_edges(G))."
            )
            raise nx.NetworkXNotImplemented(msg)
        degrees = dict(G.degree())
        # Sort nodes by degree.
        nodes = sorted(degrees, key=degrees.get)
        bin_boundaries = [0]
        curr_degree = 0
        for i, v in enumerate(nodes):
            if degrees[v] > curr_degree:
                bin_boundaries.extend([i] * (degrees[v] - curr_degree))
                curr_degree = degrees[v]
        node_pos = {v: pos for pos, v in enumerate(nodes)}
        # The initial guess for the core number of a node is its degree.
        core = degrees
        nbrs = {v: list(nx.all_neighbors(G, v)) for v in G}
        for v in nodes:
            for u in nbrs[v]:
                if core[u] > core[v]:
                    nbrs[u].remove(v)
                    pos = node_pos[u]
                    bin_start = bin_boundaries[core[u]]
                    node_pos[u] = bin_start
                    node_pos[nodes[bin_start]] = pos
                    nodes[bin_start], nodes[pos] = nodes[pos], nodes[bin_start]
                    bin_boundaries[core[u]] += 1
                    core[u] -= 1
        return core

    def _core_subgraph(G, k_filter, k=None, core=None):
        """Returns 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`.

        """
        if core is None:
            core = core_number(G)
        if k is None:
            k = max(core.values())
        nodes = (v for v in core if k_filter(v, k, core))
        return G.subgraph(nodes).copy()

    @nx._dispatchable(preserve_all_attrs=True, returns_graph=True)
    def k_core(G, k=None, core_number=None):
        """Returns the k-core of G.

        A k-core is a maximal subgraph that contains nodes of degree `k` or more.

        .. deprecated:: 3.3
           `k_core` will not accept `MultiGraph` objects in version 3.5.

        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
        ------
        NetworkXNotImplemented
          The k-core is not defined for multigraphs or graphs with self loops.

        Notes
        -----
        The main core is the core with `k` as the largest core_number.

        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.

        Examples
        --------
        >>> degrees = [0, 1, 2, 2, 2, 2, 3]
        >>> H = nx.havel_hakimi_graph(degrees)
        >>> H.degree
        DegreeView({0: 1, 1: 2, 2: 2, 3: 2, 4: 2, 5: 3, 6: 0})
        >>> nx.k_core(H).nodes
        NodeView((1, 2, 3, 5))

        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
        """

        import warnings

        if G.is_multigraph():
            warnings.warn(
                (
                    "\n\n`k_core` will not accept `MultiGraph` objects in version 3.5.\n"
                    "Convert it to an undirected graph instead, using::\n\n"
                    "\tG = nx.Graph(G)\n"
                ),
                category=DeprecationWarning,
                stacklevel=5,
            )

        def k_filter(v, k, c):
            return c[v] >= k

        return _core_subgraph(G, k_filter, k, core_number)

    @nx._dispatchable(preserve_all_attrs=True, returns_graph=True)
    def k_shell(G, k=None, core_number=None):
        """Returns 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.

        .. deprecated:: 3.3
           `k_shell` will not accept `MultiGraph` objects in version 3.5.

        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
        ------
        NetworkXNotImplemented
            The k-shell is not implemented for multigraphs or graphs with self loops.

        Notes
        -----
        This is similar to k_corona but in that case only neighbors in the
        k-core are considered.

        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.

        Examples
        --------
        >>> degrees = [0, 1, 2, 2, 2, 2, 3]
        >>> H = nx.havel_hakimi_graph(degrees)
        >>> H.degree
        DegreeView({0: 1, 1: 2, 2: 2, 3: 2, 4: 2, 5: 3, 6: 0})
        >>> nx.k_shell(H, k=1).nodes
        NodeView((0, 4))

        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
        """

        import warnings

        if G.is_multigraph():
            warnings.warn(
                (
                    "\n\n`k_shell` will not accept `MultiGraph` objects in version 3.5.\n"
                    "Convert it to an undirected graph instead, using::\n\n"
                    "\tG = nx.Graph(G)\n"
                ),
                category=DeprecationWarning,
                stacklevel=5,
            )

        def k_filter(v, k, c):
            return c[v] == k

        return _core_subgraph(G, k_filter, k, core_number)

    @nx._dispatchable(preserve_all_attrs=True, returns_graph=True)
    def k_crust(G, k=None, core_number=None):
        """Returns 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.

        .. deprecated:: 3.3
           `k_crust` will not accept `MultiGraph` objects in version 3.5.

        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
        ------
        NetworkXNotImplemented
            The k-crust is not implemented for multigraphs or graphs with self loops.

        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.

        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.

        Examples
        --------
        >>> degrees = [0, 1, 2, 2, 2, 2, 3]
        >>> H = nx.havel_hakimi_graph(degrees)
        >>> H.degree
        DegreeView({0: 1, 1: 2, 2: 2, 3: 2, 4: 2, 5: 3, 6: 0})
        >>> nx.k_crust(H, k=1).nodes
        NodeView((0, 4, 6))

        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
        """

        import warnings

        if G.is_multigraph():
            warnings.warn(
                (
                    "\n\n`k_crust` will not accept `MultiGraph` objects in version 3.5.\n"
                    "Convert it to an undirected graph instead, using::\n\n"
                    "\tG = nx.Graph(G)\n"
                ),
                category=DeprecationWarning,
                stacklevel=5,
            )

        # Default for k is one less than in _core_subgraph, so just inline.
        #    Filter is c[v] <= k
        if core_number is None:
            core_number = nx.core_number(G)
        if k is None:
            k = max(core_number.values()) - 1
        nodes = (v for v in core_number if core_number[v] <= k)
        return G.subgraph(nodes).copy()

    @nx._dispatchable(preserve_all_attrs=True, returns_graph=True)
    def k_corona(G, k, core_number=None):
        """Returns the k-corona of G.

        The k-corona is the subgraph of nodes in the k-core which have
        exactly k neighbors in the k-core.

        .. deprecated:: 3.3
           `k_corona` will not accept `MultiGraph` objects in version 3.5.

        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
        ------
        NetworkXNotImplemented
            The k-corona is not defined for multigraphs or graphs with self loops.

        Notes
        -----
        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.

        Examples
        --------
        >>> degrees = [0, 1, 2, 2, 2, 2, 3]
        >>> H = nx.havel_hakimi_graph(degrees)
        >>> H.degree
        DegreeView({0: 1, 1: 2, 2: 2, 3: 2, 4: 2, 5: 3, 6: 0})
        >>> nx.k_corona(H, k=2).nodes
        NodeView((1, 2, 3, 5))

        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
        """

        import warnings

        if G.is_multigraph():
            warnings.warn(
                (
                    "\n\n`k_corona` will not accept `MultiGraph` objects in version 3.5.\n"
                    "Convert it to an undirected graph instead, using::\n\n"
                    "\tG = nx.Graph(G)\n"
                ),
                category=DeprecationWarning,
                stacklevel=5,
            )

        def func(v, k, c):
            return c[v] == k and k == sum(1 for w in G[v] if c[w] >= k)

        return _core_subgraph(G, func, k, core_number)

    @nx.utils.not_implemented_for("directed")
    @nx.utils.not_implemented_for("multigraph")
    @nx._dispatchable(preserve_all_attrs=True, returns_graph=True)
    def k_truss(G, k):
        """Returns 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
        ------
        NetworkXNotImplemented
          If `G` is a multigraph or directed graph or if it contains self loops.

        Notes
        -----
        A k-clique is a (k-2)-truss and a k-truss is a (k+1)-core.

        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.

        Examples
        --------
        >>> degrees = [0, 1, 2, 2, 2, 2, 3]
        >>> H = nx.havel_hakimi_graph(degrees)
        >>> H.degree
        DegreeView({0: 1, 1: 2, 2: 2, 3: 2, 4: 2, 5: 3, 6: 0})
        >>> nx.k_truss(H, k=2).nodes
        NodeView((0, 1, 2, 3, 4, 5))

        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.
        """
        if nx.number_of_selfloops(G) > 0:
            msg = (
                "Input graph has self loops which is not permitted; "
                "Consider using G.remove_edges_from(nx.selfloop_edges(G))."
            )
            raise nx.NetworkXNotImplemented(msg)

        H = G.copy()

        n_dropped = 1
        while n_dropped > 0:
            n_dropped = 0
            to_drop = []
            seen = set()
            for u in H:
                nbrs_u = set(H[u])
                seen.add(u)
                new_nbrs = [v for v in nbrs_u if v not in seen]
                for v in new_nbrs:
                    if len(nbrs_u & set(H[v])) < (k - 2):
                        to_drop.append((u, v))
            H.remove_edges_from(to_drop)
            n_dropped = len(to_drop)
            H.remove_nodes_from(list(nx.isolates(H)))

        return H

    @nx.utils.not_implemented_for("multigraph")
    @nx.utils.not_implemented_for("directed")
    @nx._dispatchable
    def onion_layers(G):
        """Returns 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
            An undirected graph without self loops.

        Returns
        -------
        od_layers : dictionary
            A dictionary keyed by node to the onion layer. The layers are
            contiguous integers starting at 1.

        Raises
        ------
        NetworkXNotImplemented
            If `G` is a multigraph or directed graph or if it contains self loops.

        Examples
        --------
        >>> degrees = [0, 1, 2, 2, 2, 2, 3]
        >>> H = nx.havel_hakimi_graph(degrees)
        >>> H.degree
        DegreeView({0: 1, 1: 2, 2: 2, 3: 2, 4: 2, 5: 3, 6: 0})
        >>> nx.onion_layers(H)
        {6: 1, 0: 2, 4: 3, 1: 4, 2: 4, 3: 4, 5: 4}

        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
        """
        if nx.number_of_selfloops(G) > 0:
            msg = (
                "Input graph contains self loops which is not permitted; "
                "Consider using G.remove_edges_from(nx.selfloop_edges(G))."
            )
            raise nx.NetworkXNotImplemented(msg)
        # Dictionaries to register the k-core/onion decompositions.
        od_layers = {}
        # Adjacency list
        neighbors = {v: list(nx.all_neighbors(G, v)) for v in G}
        # Effective degree of nodes.
        degrees = dict(G.degree())
        # Performs the onion decomposition.
        current_core = 1
        current_layer = 1
        # Sets vertices of degree 0 to layer 1, if any.
        isolated_nodes = list(nx.isolates(G))
        if len(isolated_nodes) > 0:
            for v in isolated_nodes:
                od_layers[v] = current_layer
                degrees.pop(v)
            current_layer = 2
        # Finds the layer for the remaining nodes.
        while len(degrees) > 0:
            # Sets the order for looking at nodes.
            nodes = sorted(degrees, key=degrees.get)
            # Sets properly the current core.
            min_degree = degrees[nodes[0]]
            if min_degree > current_core:
                current_core = min_degree
            # Identifies vertices in the current layer.
            this_layer = []
            for n in nodes:
                if degrees[n] > current_core:
                    break
                this_layer.append(n)
            # Identifies the core/layer of the vertices in the current layer.
            for v in this_layer:
                od_layers[v] = current_layer
                for n in neighbors[v]:
                    neighbors[n].remove(v)
                    degrees[n] = degrees[n] - 1
                degrees.pop(v)
            # Updates the layer count.
            current_layer = current_layer + 1
        # Returns the dictionaries containing the onion layer of each vertices.
        return od_layers