laplacian_centrality

laplacian_centrality(G, normalized=True, nodelist=None, weight='weight', walk_type=None, alpha=0.95)

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.

\[ \begin{align}\begin{aligned}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\end{aligned}\end{align} \]

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:

Ggraph

A networkx graph

normalizedbool (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.

nodelistlist, 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_typestring or None, optional (default=None)

Optional parameter walk_type used when calling directed_laplacian_matrix. If None, the transition matrix is selected depending on the properties of the graph. Otherwise can be random, lazy, or pagerank.

alphareal (default = 0.95)

Optional parameter alpha used when calling directed_laplacian_matrix. (1 - alpha) is the teleportation probability used with pagerank.

Returns:

nodesdictionary

Dictionary of nodes with Laplacian centrality as the value.

Raises:

NetworkXPointlessConcept

If the graph G is the null graph.

ZeroDivisionError

If the graph G has no edges (is empty) and normalization is requested.

See also

directed_laplacian_matrix()

laplacian_matrix()

Notes

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

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

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')]