Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/centrality/laplacian.py: 11%
37 statements
« prev ^ index » next coverage.py v7.3.2, created at 2023-10-20 07:00 +0000
1"""
2Laplacian centrality measures.
3"""
4import networkx as nx
6__all__ = ["laplacian_centrality"]
9@nx._dispatch(edge_attrs="weight")
10def laplacian_centrality(
11 G, normalized=True, nodelist=None, weight="weight", walk_type=None, alpha=0.95
12):
13 r"""Compute the Laplacian centrality for nodes in the graph `G`.
15 The Laplacian Centrality of a node ``i`` is measured by the drop in the
16 Laplacian Energy after deleting node ``i`` from the graph. The Laplacian Energy
17 is the sum of the squared eigenvalues of a graph's Laplacian matrix.
19 .. math::
21 C_L(u_i,G) = \frac{(\Delta E)_i}{E_L (G)} = \frac{E_L (G)-E_L (G_i)}{E_L (G)}
23 E_L (G) = \sum_{i=0}^n \lambda_i^2
25 Where $E_L (G)$ is the Laplacian energy of graph `G`,
26 E_L (G_i) is the Laplacian energy of graph `G` after deleting node ``i``
27 and $\lambda_i$ are the eigenvalues of `G`'s Laplacian matrix.
28 This formula shows the normalized value. Without normalization,
29 the numerator on the right side is returned.
31 Parameters
32 ----------
33 G : graph
34 A networkx graph
36 normalized : bool (default = True)
37 If True the centrality score is scaled so the sum over all nodes is 1.
38 If False the centrality score for each node is the drop in Laplacian
39 energy when that node is removed.
41 nodelist : list, optional (default = None)
42 The rows and columns are ordered according to the nodes in nodelist.
43 If nodelist is None, then the ordering is produced by G.nodes().
45 weight: string or None, optional (default=`weight`)
46 Optional parameter `weight` to compute the Laplacian matrix.
47 The edge data key used to compute each value in the matrix.
48 If None, then each edge has weight 1.
50 walk_type : string or None, optional (default=None)
51 Optional parameter `walk_type` used when calling
52 :func:`directed_laplacian_matrix <networkx.directed_laplacian_matrix>`.
53 If None, the transition matrix is selected depending on the properties
54 of the graph. Otherwise can be `random`, `lazy`, or `pagerank`.
56 alpha : real (default = 0.95)
57 Optional parameter `alpha` used when calling
58 :func:`directed_laplacian_matrix <networkx.directed_laplacian_matrix>`.
59 (1 - alpha) is the teleportation probability used with pagerank.
61 Returns
62 -------
63 nodes : dictionary
64 Dictionary of nodes with Laplacian centrality as the value.
66 Examples
67 --------
68 >>> G = nx.Graph()
69 >>> edges = [(0, 1, 4), (0, 2, 2), (2, 1, 1), (1, 3, 2), (1, 4, 2), (4, 5, 1)]
70 >>> G.add_weighted_edges_from(edges)
71 >>> sorted((v, f"{c:0.2f}") for v, c in laplacian_centrality(G).items())
72 [(0, '0.70'), (1, '0.90'), (2, '0.28'), (3, '0.22'), (4, '0.26'), (5, '0.04')]
74 Notes
75 -----
76 The algorithm is implemented based on [1]_ with an extension to directed graphs
77 using the ``directed_laplacian_matrix`` function.
79 Raises
80 ------
81 NetworkXPointlessConcept
82 If the graph `G` is the null graph.
83 ZeroDivisionError
84 If the graph `G` has no edges (is empty) and normalization is requested.
86 References
87 ----------
88 .. [1] Qi, X., Fuller, E., Wu, Q., Wu, Y., and Zhang, C.-Q. (2012).
89 Laplacian centrality: A new centrality measure for weighted networks.
90 Information Sciences, 194:240-253.
91 https://math.wvu.edu/~cqzhang/Publication-files/my-paper/INS-2012-Laplacian-W.pdf
93 See Also
94 --------
95 :func:`~networkx.linalg.laplacianmatrix.directed_laplacian_matrix`
96 :func:`~networkx.linalg.laplacianmatrix.laplacian_matrix`
97 """
98 import numpy as np
99 import scipy as sp
101 if len(G) == 0:
102 raise nx.NetworkXPointlessConcept("null graph has no centrality defined")
103 if G.size(weight=weight) == 0:
104 if normalized:
105 raise ZeroDivisionError("graph with no edges has zero full energy")
106 return {n: 0 for n in G}
108 if nodelist is not None:
109 nodeset = set(G.nbunch_iter(nodelist))
110 if len(nodeset) != len(nodelist):
111 raise nx.NetworkXError("nodelist has duplicate nodes or nodes not in G")
112 nodes = nodelist + [n for n in G if n not in nodeset]
113 else:
114 nodelist = nodes = list(G)
116 if G.is_directed():
117 lap_matrix = nx.directed_laplacian_matrix(G, nodes, weight, walk_type, alpha)
118 else:
119 lap_matrix = nx.laplacian_matrix(G, nodes, weight).toarray()
121 full_energy = np.power(sp.linalg.eigh(lap_matrix, eigvals_only=True), 2).sum()
123 # calculate laplacian centrality
124 laplace_centralities_dict = {}
125 for i, node in enumerate(nodelist):
126 # remove row and col i from lap_matrix
127 all_but_i = list(np.arange(lap_matrix.shape[0]))
128 all_but_i.remove(i)
129 A_2 = lap_matrix[all_but_i, :][:, all_but_i]
131 # Adjust diagonal for removed row
132 new_diag = lap_matrix.diagonal() - abs(lap_matrix[:, i])
133 np.fill_diagonal(A_2, new_diag[all_but_i])
135 if len(all_but_i) > 0: # catches degenerate case of single node
136 new_energy = np.power(sp.linalg.eigh(A_2, eigvals_only=True), 2).sum()
137 else:
138 new_energy = 0.0
140 lapl_cent = full_energy - new_energy
141 if normalized:
142 lapl_cent = lapl_cent / full_energy
144 laplace_centralities_dict[node] = lapl_cent
146 return laplace_centralities_dict