Skip to main content
`Ctrl`+`K`

# Source code for networkx.algorithms.centrality.laplacian

    """
    Laplacian centrality measures.
    """

    import networkx as nx

    __all__ = ["laplacian_centrality"]

    @nx._dispatchable(edge_attrs="weight")
    def laplacian_centrality(
        G, normalized=True, nodelist=None, weight="weight", walk_type=None, alpha=0.95
    ):
        r"""Compute the Laplacian centrality for nodes in the graph `G`.

        The Laplacian Centrality of a node ``i`` is measured by the drop in the
        Laplacian Energy after deleting node ``i`` from the graph. The Laplacian Energy
        is the sum of the squared eigenvalues of a graph's Laplacian matrix.

        .. math::

            C_L(u_i,G) = \frac{(\Delta E)_i}{E_L (G)} = \frac{E_L (G)-E_L (G_i)}{E_L (G)}

            E_L (G) = \sum_{i=0}^n \lambda_i^2

        Where $E_L (G)$ is the Laplacian energy of graph `G`,
        E_L (G_i) is the Laplacian energy of graph `G` after deleting node ``i``
        and $\lambda_i$ are the eigenvalues of `G`'s Laplacian matrix.
        This formula shows the normalized value. Without normalization,
        the numerator on the right side is returned.

        Parameters
        ----------
        G : graph
            A networkx graph

        normalized : bool (default = True)
            If True the centrality score is scaled so the sum over all nodes is 1.
            If False the centrality score for each node is the drop in Laplacian
            energy when that node is removed.

        nodelist : list, optional (default = None)
            The rows and columns are ordered according to the nodes in nodelist.
            If nodelist is None, then the ordering is produced by G.nodes().

        weight: string or None, optional (default=`weight`)
            Optional parameter `weight` to compute the Laplacian matrix.
            The edge data key used to compute each value in the matrix.
            If None, then each edge has weight 1.

        walk_type : string or None, optional (default=None)
            Optional parameter `walk_type` used when calling
            :func:`directed_laplacian_matrix <networkx.directed_laplacian_matrix>`.
            One of ``"random"``, ``"lazy"``, or ``"pagerank"``. If ``walk_type=None``
            (the default), then a value is selected according to the properties of `G`:
            - ``walk_type="random"`` if `G` is strongly connected and aperiodic
            - ``walk_type="lazy"`` if `G` is strongly connected but not aperiodic
            - ``walk_type="pagerank"`` for all other cases.

        alpha : real (default = 0.95)
            Optional parameter `alpha` used when calling
            :func:`directed_laplacian_matrix <networkx.directed_laplacian_matrix>`.
            (1 - alpha) is the teleportation probability used with pagerank.

        Returns
        -------
        nodes : dictionary
           Dictionary of nodes with Laplacian centrality as the value.

        Examples
        --------
        >>> G = nx.Graph()
        >>> edges = [(0, 1, 4), (0, 2, 2), (2, 1, 1), (1, 3, 2), (1, 4, 2), (4, 5, 1)]
        >>> G.add_weighted_edges_from(edges)
        >>> sorted((v, f"{c:0.2f}") for v, c in laplacian_centrality(G).items())
        [(0, '0.70'), (1, '0.90'), (2, '0.28'), (3, '0.22'), (4, '0.26'), (5, '0.04')]

        Notes
        -----
        The algorithm is implemented based on [1]_ with an extension to directed graphs
        using the ``directed_laplacian_matrix`` function.

        Raises
        ------
        NetworkXPointlessConcept
            If the graph `G` is the null graph.
        ZeroDivisionError
            If the graph `G` has no edges (is empty) and normalization is requested.

        References
        ----------
        .. [1] Qi, X., Fuller, E., Wu, Q., Wu, Y., and Zhang, C.-Q. (2012).
           Laplacian centrality: A new centrality measure for weighted networks.
           Information Sciences, 194:240-253.
           https://math.wvu.edu/~cqzhang/Publication-files/my-paper/INS-2012-Laplacian-W.pdf

        See Also
        --------
        :func:`~networkx.linalg.laplacianmatrix.directed_laplacian_matrix`
        :func:`~networkx.linalg.laplacianmatrix.laplacian_matrix`
        """
        import numpy as np
        import scipy as sp

        if len(G) == 0:
            raise nx.NetworkXPointlessConcept("null graph has no centrality defined")
        if G.size(weight=weight) == 0:
            if normalized:
                raise ZeroDivisionError("graph with no edges has zero full energy")
            return {n: 0 for n in G}

        if nodelist is not None:
            nodeset = set(G.nbunch_iter(nodelist))
            if len(nodeset) != len(nodelist):
                raise nx.NetworkXError("nodelist has duplicate nodes or nodes not in G")
            nodes = nodelist + [n for n in G if n not in nodeset]
        else:
            nodelist = nodes = list(G)

        if G.is_directed():
            lap_matrix = nx.directed_laplacian_matrix(G, nodes, weight, walk_type, alpha)
        else:
            lap_matrix = nx.laplacian_matrix(G, nodes, weight).toarray()

        full_energy = np.power(sp.linalg.eigh(lap_matrix, eigvals_only=True), 2).sum()

        # calculate laplacian centrality
        laplace_centralities_dict = {}
        for i, node in enumerate(nodelist):
            # remove row and col i from lap_matrix
            all_but_i = list(np.arange(lap_matrix.shape[0]))
            all_but_i.remove(i)
            A_2 = lap_matrix[all_but_i, :][:, all_but_i]

            # Adjust diagonal for removed row
            new_diag = lap_matrix.diagonal() - abs(lap_matrix[:, i])
            np.fill_diagonal(A_2, new_diag[all_but_i])

            if len(all_but_i) > 0:  # catches degenerate case of single node
                new_energy = np.power(sp.linalg.eigh(A_2, eigvals_only=True), 2).sum()
            else:
                new_energy = 0.0

            lapl_cent = full_energy - new_energy
            if normalized:
                lapl_cent = lapl_cent / full_energy

            laplace_centralities_dict[node] = float(lapl_cent)

        return laplace_centralities_dict