1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
|
"""
Laplacian centrality measures.
"""
import networkx as nx
__all__ = ["laplacian_centrality"]
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>`.
If None, the transition matrix is selected depending on the properties
of the graph. Otherwise can be `random`, `lazy`, or `pagerank`.
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.
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
import scipy.linalg # call as sp.linalg
if len(G) == 0:
raise nx.NetworkXPointlessConcept("null graph has no centrality defined")
if nodelist != 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])
new_energy = np.power(sp.linalg.eigh(A_2, eigvals_only=True), 2).sum()
lapl_cent = full_energy - new_energy
if normalized:
lapl_cent = lapl_cent / full_energy
laplace_centralities_dict[node] = lapl_cent
return laplace_centralities_dict
|
