### annotate env/lib/python3.9/site-packages/networkx/algorithms/centrality/eigenvector.py @ 0:4f3585e2f14bdraftdefaulttip

author shellac Mon, 22 Mar 2021 18:12:50 +0000
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
0
shellac
parents:
diff changeset
1 """Functions for computing eigenvector centrality."""
shellac
parents:
diff changeset
2
shellac
parents:
diff changeset
3 from math import sqrt
shellac
parents:
diff changeset
4
shellac
parents:
diff changeset
5 import networkx as nx
shellac
parents:
diff changeset
6 from networkx.utils import not_implemented_for
shellac
parents:
diff changeset
7
shellac
parents:
diff changeset
8 __all__ = ["eigenvector_centrality", "eigenvector_centrality_numpy"]
shellac
parents:
diff changeset
9
shellac
parents:
diff changeset
10
shellac
parents:
diff changeset
11 @not_implemented_for("multigraph")
shellac
parents:
diff changeset
12 def eigenvector_centrality(G, max_iter=100, tol=1.0e-6, nstart=None, weight=None):
shellac
parents:
diff changeset
13 r"""Compute the eigenvector centrality for the graph G.
shellac
parents:
diff changeset
14
shellac
parents:
diff changeset
15 Eigenvector centrality computes the centrality for a node based on the
shellac
parents:
diff changeset
16 centrality of its neighbors. The eigenvector centrality for node $i$ is
shellac
parents:
diff changeset
17 the $i$-th element of the vector $x$ defined by the equation
shellac
parents:
diff changeset
18
shellac
parents:
diff changeset
19 .. math::
shellac
parents:
diff changeset
20
shellac
parents:
diff changeset
21 Ax = \lambda x
shellac
parents:
diff changeset
22
shellac
parents:
diff changeset
23 where $A$ is the adjacency matrix of the graph G with eigenvalue
shellac
parents:
diff changeset
24 $\lambda$. By virtue of the Perron–Frobenius theorem, there is a unique
shellac
parents:
diff changeset
25 solution $x$, all of whose entries are positive, if $\lambda$ is the
shellac
parents:
diff changeset
26 largest eigenvalue of the adjacency matrix $A$ ([2]_).
shellac
parents:
diff changeset
27
shellac
parents:
diff changeset
28 Parameters
shellac
parents:
diff changeset
29 ----------
shellac
parents:
diff changeset
30 G : graph
shellac
parents:
diff changeset
31 A networkx graph
shellac
parents:
diff changeset
32
shellac
parents:
diff changeset
33 max_iter : integer, optional (default=100)
shellac
parents:
diff changeset
34 Maximum number of iterations in power method.
shellac
parents:
diff changeset
35
shellac
parents:
diff changeset
36 tol : float, optional (default=1.0e-6)
shellac
parents:
diff changeset
37 Error tolerance used to check convergence in power method iteration.
shellac
parents:
diff changeset
38
shellac
parents:
diff changeset
39 nstart : dictionary, optional (default=None)
shellac
parents:
diff changeset
40 Starting value of eigenvector iteration for each node.
shellac
parents:
diff changeset
41
shellac
parents:
diff changeset
42 weight : None or string, optional (default=None)
shellac
parents:
diff changeset
43 If None, all edge weights are considered equal.
shellac
parents:
diff changeset
44 Otherwise holds the name of the edge attribute used as weight.
shellac
parents:
diff changeset
45
shellac
parents:
diff changeset
46 Returns
shellac
parents:
diff changeset
47 -------
shellac
parents:
diff changeset
48 nodes : dictionary
shellac
parents:
diff changeset
49 Dictionary of nodes with eigenvector centrality as the value.
shellac
parents:
diff changeset
50
shellac
parents:
diff changeset
51 Examples
shellac
parents:
diff changeset
52 --------
shellac
parents:
diff changeset
53 >>> G = nx.path_graph(4)
shellac
parents:
diff changeset
54 >>> centrality = nx.eigenvector_centrality(G)
shellac
parents:
diff changeset
55 >>> sorted((v, f"{c:0.2f}") for v, c in centrality.items())
shellac
parents:
diff changeset
56 [(0, '0.37'), (1, '0.60'), (2, '0.60'), (3, '0.37')]
shellac
parents:
diff changeset
57
shellac
parents:
diff changeset
58 Raises
shellac
parents:
diff changeset
59 ------
shellac
parents:
diff changeset
60 NetworkXPointlessConcept
shellac
parents:
diff changeset
61 If the graph G is the null graph.
shellac
parents:
diff changeset
62
shellac
parents:
diff changeset
63 NetworkXError
shellac
parents:
diff changeset
64 If each value in nstart is zero.
shellac
parents:
diff changeset
65
shellac
parents:
diff changeset
66 PowerIterationFailedConvergence
shellac
parents:
diff changeset
67 If the algorithm fails to converge to the specified tolerance
shellac
parents:
diff changeset
68 within the specified number of iterations of the power iteration
shellac
parents:
diff changeset
69 method.
shellac
parents:
diff changeset
70
shellac
parents:
diff changeset
shellac
parents:
diff changeset
72 --------
shellac
parents:
diff changeset
73 eigenvector_centrality_numpy
shellac
parents:
diff changeset
74 pagerank
shellac
parents:
diff changeset
75 hits
shellac
parents:
diff changeset
76
shellac
parents:
diff changeset
77 Notes
shellac
parents:
diff changeset
78 -----
shellac
parents:
diff changeset
79 The measure was introduced by [1]_ and is discussed in [2]_.
shellac
parents:
diff changeset
80
shellac
parents:
diff changeset
81 The power iteration method is used to compute the eigenvector and
shellac
parents:
diff changeset
82 convergence is **not** guaranteed. Our method stops after max_iter
shellac
parents:
diff changeset
83 iterations or when the change in the computed vector between two
shellac
parents:
diff changeset
84 iterations is smaller than an error tolerance of
shellac
parents:
diff changeset
85 G.number_of_nodes() * tol. This implementation uses ($A + I$)
shellac
parents:
diff changeset
86 rather than the adjacency matrix $A$ because it shifts the spectrum
shellac
parents:
diff changeset
87 to enable discerning the correct eigenvector even for networks with
shellac
parents:
diff changeset
88 multiple dominant eigenvalues.
shellac
parents:
diff changeset
89
shellac
parents:
diff changeset
90 For directed graphs this is "left" eigenvector centrality which corresponds
shellac
parents:
diff changeset
91 to the in-edges in the graph. For out-edges eigenvector centrality
shellac
parents:
diff changeset
92 first reverse the graph with G.reverse().
shellac
parents:
diff changeset
93
shellac
parents:
diff changeset
94 References
shellac
parents:
diff changeset
95 ----------
shellac
parents:
diff changeset
96 .. [1] Phillip Bonacich.
shellac
parents:
diff changeset
97 "Power and Centrality: A Family of Measures."
shellac
parents:
diff changeset
98 *American Journal of Sociology* 92(5):1170–1182, 1986
shellac
parents:
diff changeset
99 <http://www.leonidzhukov.net/hse/2014/socialnetworks/papers/Bonacich-Centrality.pdf>
shellac
parents:
diff changeset
100 .. [2] Mark E. J. Newman.
shellac
parents:
diff changeset
101 *Networks: An Introduction.*
shellac
parents:
diff changeset
102 Oxford University Press, USA, 2010, pp. 169.
shellac
parents:
diff changeset
103
shellac
parents:
diff changeset
104 """
shellac
parents:
diff changeset
105 if len(G) == 0:
shellac
parents:
diff changeset
106 raise nx.NetworkXPointlessConcept(
shellac
parents:
diff changeset
107 "cannot compute centrality for the null graph"
shellac
parents:
diff changeset
108 )
shellac
parents:
diff changeset
109 # If no initial vector is provided, start with the all-ones vector.
shellac
parents:
diff changeset
110 if nstart is None:
shellac
parents:
diff changeset
111 nstart = {v: 1 for v in G}
shellac
parents:
diff changeset
112 if all(v == 0 for v in nstart.values()):
shellac
parents:
diff changeset
113 raise nx.NetworkXError("initial vector cannot have all zero values")
shellac
parents:
diff changeset
114 # Normalize the initial vector so that each entry is in [0, 1]. This is
shellac
parents:
diff changeset
115 # guaranteed to never have a divide-by-zero error by the previous line.
shellac
parents:
diff changeset
116 nstart_sum = sum(nstart.values())
shellac
parents:
diff changeset
117 x = {k: v / nstart_sum for k, v in nstart.items()}
shellac
parents:
diff changeset
118 nnodes = G.number_of_nodes()
shellac
parents:
diff changeset
119 # make up to max_iter iterations
shellac
parents:
diff changeset
120 for i in range(max_iter):
shellac
parents:
diff changeset
121 xlast = x
shellac
parents:
diff changeset
122 x = xlast.copy() # Start with xlast times I to iterate with (A+I)
shellac
parents:
diff changeset
123 # do the multiplication y^T = x^T A (left eigenvector)
shellac
parents:
diff changeset
124 for n in x:
shellac
parents:
diff changeset
125 for nbr in G[n]:
shellac
parents:
diff changeset
126 w = G[n][nbr].get(weight, 1) if weight else 1
shellac
parents:
diff changeset
127 x[nbr] += xlast[n] * w
shellac
parents:
diff changeset
128 # Normalize the vector. The normalization denominator norm
shellac
parents:
diff changeset
129 # should never be zero by the Perron--Frobenius
shellac
parents:
diff changeset
130 # theorem. However, in case it is due to numerical error, we
shellac
parents:
diff changeset
131 # assume the norm to be one instead.
shellac
parents:
diff changeset
132 norm = sqrt(sum(z ** 2 for z in x.values())) or 1
shellac
parents:
diff changeset
133 x = {k: v / norm for k, v in x.items()}
shellac
parents:
diff changeset
134 # Check for convergence (in the L_1 norm).
shellac
parents:
diff changeset
135 if sum(abs(x[n] - xlast[n]) for n in x) < nnodes * tol:
shellac
parents:
diff changeset
136 return x
shellac
parents:
diff changeset
137 raise nx.PowerIterationFailedConvergence(max_iter)
shellac
parents:
diff changeset
138
shellac
parents:
diff changeset
139
shellac
parents:
diff changeset
140 def eigenvector_centrality_numpy(G, weight=None, max_iter=50, tol=0):
shellac
parents:
diff changeset
141 r"""Compute the eigenvector centrality for the graph G.
shellac
parents:
diff changeset
142
shellac
parents:
diff changeset
143 Eigenvector centrality computes the centrality for a node based on the
shellac
parents:
diff changeset
144 centrality of its neighbors. The eigenvector centrality for node $i$ is
shellac
parents:
diff changeset
145
shellac
parents:
diff changeset
146 .. math::
shellac
parents:
diff changeset
147
shellac
parents:
diff changeset
148 Ax = \lambda x
shellac
parents:
diff changeset
149
shellac
parents:
diff changeset
150 where $A$ is the adjacency matrix of the graph G with eigenvalue $\lambda$.
shellac
parents:
diff changeset
151 By virtue of the Perron–Frobenius theorem, there is a unique and positive
shellac
parents:
diff changeset
152 solution if $\lambda$ is the largest eigenvalue associated with the
shellac
parents:
diff changeset
153 eigenvector of the adjacency matrix $A$ ([2]_).
shellac
parents:
diff changeset
154
shellac
parents:
diff changeset
155 Parameters
shellac
parents:
diff changeset
156 ----------
shellac
parents:
diff changeset
157 G : graph
shellac
parents:
diff changeset
158 A networkx graph
shellac
parents:
diff changeset
159
shellac
parents:
diff changeset
160 weight : None or string, optional (default=None)
shellac
parents:
diff changeset
161 The name of the edge attribute used as weight.
shellac
parents:
diff changeset
162 If None, all edge weights are considered equal.
shellac
parents:
diff changeset
163
shellac
parents:
diff changeset
164 max_iter : integer, optional (default=100)
shellac
parents:
diff changeset
165 Maximum number of iterations in power method.
shellac
parents:
diff changeset
166
shellac
parents:
diff changeset
167 tol : float, optional (default=1.0e-6)
shellac
parents:
diff changeset
168 Relative accuracy for eigenvalues (stopping criterion).
shellac
parents:
diff changeset
169 The default value of 0 implies machine precision.
shellac
parents:
diff changeset
170
shellac
parents:
diff changeset
171 Returns
shellac
parents:
diff changeset
172 -------
shellac
parents:
diff changeset
173 nodes : dictionary
shellac
parents:
diff changeset
174 Dictionary of nodes with eigenvector centrality as the value.
shellac
parents:
diff changeset
175
shellac
parents:
diff changeset
176 Examples
shellac
parents:
diff changeset
177 --------
shellac
parents:
diff changeset
178 >>> G = nx.path_graph(4)
shellac
parents:
diff changeset
179 >>> centrality = nx.eigenvector_centrality_numpy(G)
shellac
parents:
diff changeset
180 >>> print([f"{node} {centrality[node]:0.2f}" for node in centrality])
shellac
parents:
diff changeset
181 ['0 0.37', '1 0.60', '2 0.60', '3 0.37']
shellac
parents:
diff changeset
182
shellac
parents:
diff changeset
shellac
parents:
diff changeset
184 --------
shellac
parents:
diff changeset
185 eigenvector_centrality
shellac
parents:
diff changeset
186 pagerank
shellac
parents:
diff changeset
187 hits
shellac
parents:
diff changeset
188
shellac
parents:
diff changeset
189 Notes
shellac
parents:
diff changeset
190 -----
shellac
parents:
diff changeset
191 The measure was introduced by [1]_.
shellac
parents:
diff changeset
192
shellac
parents:
diff changeset
193 This algorithm uses the SciPy sparse eigenvalue solver (ARPACK) to
shellac
parents:
diff changeset
194 find the largest eigenvalue/eigenvector pair.
shellac
parents:
diff changeset
195
shellac
parents:
diff changeset
196 For directed graphs this is "left" eigenvector centrality which corresponds
shellac
parents:
diff changeset
197 to the in-edges in the graph. For out-edges eigenvector centrality
shellac
parents:
diff changeset
198 first reverse the graph with G.reverse().
shellac
parents:
diff changeset
199
shellac
parents:
diff changeset
200 Raises
shellac
parents:
diff changeset
201 ------
shellac
parents:
diff changeset
202 NetworkXPointlessConcept
shellac
parents:
diff changeset
203 If the graph G is the null graph.
shellac
parents:
diff changeset
204
shellac
parents:
diff changeset
205 References
shellac
parents:
diff changeset
206 ----------
shellac
parents:
diff changeset
207 .. [1] Phillip Bonacich:
shellac
parents:
diff changeset
208 Power and Centrality: A Family of Measures.
shellac
parents:
diff changeset
209 American Journal of Sociology 92(5):1170–1182, 1986
shellac
parents:
diff changeset
210 http://www.leonidzhukov.net/hse/2014/socialnetworks/papers/Bonacich-Centrality.pdf
shellac
parents:
diff changeset
211 .. [2] Mark E. J. Newman:
shellac
parents:
diff changeset
212 Networks: An Introduction.
shellac
parents:
diff changeset
213 Oxford University Press, USA, 2010, pp. 169.
shellac
parents:
diff changeset
214 """
shellac
parents:
diff changeset
215 import numpy as np
shellac
parents:
diff changeset
216 import scipy as sp
shellac
parents:
diff changeset
217 from scipy.sparse import linalg
shellac
parents:
diff changeset
218
shellac
parents:
diff changeset
219 if len(G) == 0:
shellac
parents:
diff changeset
220 raise nx.NetworkXPointlessConcept(
shellac
parents:
diff changeset
221 "cannot compute centrality for the null graph"
shellac
parents:
diff changeset
222 )
shellac
parents:
diff changeset
223 M = nx.to_scipy_sparse_matrix(G, nodelist=list(G), weight=weight, dtype=float)
shellac
parents:
diff changeset
224 eigenvalue, eigenvector = linalg.eigs(
shellac
parents:
diff changeset
225 M.T, k=1, which="LR", maxiter=max_iter, tol=tol
shellac
parents:
diff changeset
226 )
shellac
parents:
diff changeset
227 largest = eigenvector.flatten().real