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

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