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"""
2Laplacian centrality measures.
3"""
5import networkx as nx
7__all__ = ["laplacian_centrality"]
10@nx._dispatchable(edge_attrs="weight")
11def laplacian_centrality(
12 G, normalized=True, nodelist=None, weight="weight", walk_type=None, alpha=0.95
13):
14 r"""Compute the Laplacian centrality for nodes in the graph `G`.
16 The Laplacian Centrality of a node ``i`` is measured by the drop in the
17 Laplacian Energy after deleting node ``i`` from the graph. The Laplacian Energy
18 is the sum of the squared eigenvalues of a graph's Laplacian matrix.
20 .. math::
22 C_L(u_i,G) = \frac{(\Delta E)_i}{E_L (G)} = \frac{E_L (G)-E_L (G_i)}{E_L (G)}
24 E_L (G) = \sum_{i=0}^n \lambda_i^2
26 Where $E_L (G)$ is the Laplacian energy of graph `G`,
27 E_L (G_i) is the Laplacian energy of graph `G` after deleting node ``i``
28 and $\lambda_i$ are the eigenvalues of `G`'s Laplacian matrix.
29 This formula shows the normalized value. Without normalization,
30 the numerator on the right side is returned.
32 Parameters
33 ----------
34 G : graph
35 A networkx graph
37 normalized : bool (default = True)
38 If True the centrality score is scaled so the sum over all nodes is 1.
39 If False the centrality score for each node is the drop in Laplacian
40 energy when that node is removed.
42 nodelist : list, optional (default = None)
43 The rows and columns are ordered according to the nodes in nodelist.
44 If nodelist is None, then the ordering is produced by G.nodes().
46 weight: string or None, optional (default=`weight`)
47 Optional parameter `weight` to compute the Laplacian matrix.
48 The edge data key used to compute each value in the matrix.
49 If None, then each edge has weight 1.
51 walk_type : string or None, optional (default=None)
52 Optional parameter `walk_type` used when calling
53 :func:`directed_laplacian_matrix <networkx.directed_laplacian_matrix>`.
54 One of ``"random"``, ``"lazy"``, or ``"pagerank"``. If ``walk_type=None``
55 (the default), then a value is selected according to the properties of `G`:
56 - ``walk_type="random"`` if `G` is strongly connected and aperiodic
57 - ``walk_type="lazy"`` if `G` is strongly connected but not aperiodic
58 - ``walk_type="pagerank"`` for all other cases.
60 alpha : real (default = 0.95)
61 Optional parameter `alpha` used when calling
62 :func:`directed_laplacian_matrix <networkx.directed_laplacian_matrix>`.
63 (1 - alpha) is the teleportation probability used with pagerank.
65 Returns
66 -------
67 nodes : dictionary
68 Dictionary of nodes with Laplacian centrality as the value.
70 Examples
71 --------
72 >>> G = nx.Graph()
73 >>> edges = [(0, 1, 4), (0, 2, 2), (2, 1, 1), (1, 3, 2), (1, 4, 2), (4, 5, 1)]
74 >>> G.add_weighted_edges_from(edges)
75 >>> sorted((v, f"{c:0.2f}") for v, c in laplacian_centrality(G).items())
76 [(0, '0.70'), (1, '0.90'), (2, '0.28'), (3, '0.22'), (4, '0.26'), (5, '0.04')]
78 Notes
79 -----
80 The algorithm is implemented based on [1]_ with an extension to directed graphs
81 using the ``directed_laplacian_matrix`` function.
83 Raises
84 ------
85 NetworkXPointlessConcept
86 If the graph `G` is the null graph.
87 ZeroDivisionError
88 If the graph `G` has no edges (is empty) and normalization is requested.
90 References
91 ----------
92 .. [1] Qi, X., Fuller, E., Wu, Q., Wu, Y., and Zhang, C.-Q. (2012).
93 Laplacian centrality: A new centrality measure for weighted networks.
94 Information Sciences, 194:240-253.
95 https://math.wvu.edu/~cqzhang/Publication-files/my-paper/INS-2012-Laplacian-W.pdf
97 See Also
98 --------
99 :func:`~networkx.linalg.laplacianmatrix.directed_laplacian_matrix`
100 :func:`~networkx.linalg.laplacianmatrix.laplacian_matrix`
101 """
102 import numpy as np
103 import scipy as sp
105 if len(G) == 0:
106 raise nx.NetworkXPointlessConcept("null graph has no centrality defined")
107 if G.size(weight=weight) == 0:
108 if normalized:
109 raise ZeroDivisionError("graph with no edges has zero full energy")
110 return {n: 0 for n in G}
112 if nodelist is not None:
113 nodeset = set(G.nbunch_iter(nodelist))
114 if len(nodeset) != len(nodelist):
115 raise nx.NetworkXError("nodelist has duplicate nodes or nodes not in G")
116 nodes = nodelist + [n for n in G if n not in nodeset]
117 else:
118 nodelist = nodes = list(G)
120 if G.is_directed():
121 lap_matrix = nx.directed_laplacian_matrix(G, nodes, weight, walk_type, alpha)
122 else:
123 lap_matrix = nx.laplacian_matrix(G, nodes, weight).toarray()
125 full_energy = np.sum(lap_matrix**2)
127 # calculate laplacian centrality
128 laplace_centralities_dict = {}
129 for i, node in enumerate(nodelist):
130 # remove row and col i from lap_matrix
131 all_but_i = list(np.arange(lap_matrix.shape[0]))
132 all_but_i.remove(i)
133 A_2 = lap_matrix[all_but_i, :][:, all_but_i]
135 # Adjust diagonal for removed row
136 new_diag = lap_matrix.diagonal() - abs(lap_matrix[:, i])
137 np.fill_diagonal(A_2, new_diag[all_but_i])
139 if len(all_but_i) > 0: # catches degenerate case of single node
140 new_energy = np.sum(A_2**2)
141 else:
142 new_energy = 0.0
144 lapl_cent = full_energy - new_energy
145 if normalized:
146 lapl_cent = lapl_cent / full_energy
148 laplace_centralities_dict[node] = float(lapl_cent)
150 return laplace_centralities_dict