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"""Functions for computing eigenvector centrality."""
3import math
5import networkx as nx
6from networkx.utils import not_implemented_for
8__all__ = ["eigenvector_centrality", "eigenvector_centrality_numpy"]
11@not_implemented_for("multigraph")
12@nx._dispatchable(edge_attrs="weight")
13def eigenvector_centrality(G, max_iter=100, tol=1.0e-6, nstart=None, weight=None):
14 r"""Compute the eigenvector centrality for the graph G.
16 Eigenvector centrality computes the centrality for a node by adding
17 the centrality of its predecessors. The centrality for node $i$ is the
18 $i$-th element of a left eigenvector associated with the eigenvalue $\lambda$
19 of maximum modulus that is positive. Such an eigenvector $x$ is
20 defined up to a multiplicative constant by the equation
22 .. math::
24 \lambda x^T = x^T A,
26 where $A$ is the adjacency matrix of the graph G. By definition of
27 row-column product, the equation above is equivalent to
29 .. math::
31 \lambda x_i = \sum_{j\to i}x_j.
33 That is, adding the eigenvector centralities of the predecessors of
34 $i$ one obtains the eigenvector centrality of $i$ multiplied by
35 $\lambda$. In the case of undirected graphs, $x$ also solves the familiar
36 right-eigenvector equation $Ax = \lambda x$.
38 By virtue of the Perron–Frobenius theorem [1]_, if G is strongly
39 connected there is a unique eigenvector $x$, and all its entries
40 are strictly positive.
42 If G is not strongly connected there might be several left
43 eigenvectors associated with $\lambda$, and some of their elements
44 might be zero.
46 Parameters
47 ----------
48 G : graph
49 A networkx graph.
51 max_iter : integer, optional (default=100)
52 Maximum number of power iterations.
54 tol : float, optional (default=1.0e-6)
55 Error tolerance (in Euclidean norm) used to check convergence in
56 power iteration.
58 nstart : dictionary, optional (default=None)
59 Starting value of power iteration for each node. Must have a nonzero
60 projection on the desired eigenvector for the power method to converge.
61 If None, this implementation uses an all-ones vector, which is a safe
62 choice.
64 weight : None or string, optional (default=None)
65 If None, all edge weights are considered equal. Otherwise holds the
66 name of the edge attribute used as weight. In this measure the
67 weight is interpreted as the connection strength.
69 Returns
70 -------
71 nodes : dictionary
72 Dictionary of nodes with eigenvector centrality as the value. The
73 associated vector has unit Euclidean norm and the values are
74 nonegative.
76 Examples
77 --------
78 >>> G = nx.path_graph(4)
79 >>> centrality = nx.eigenvector_centrality(G)
80 >>> sorted((v, f"{c:0.2f}") for v, c in centrality.items())
81 [(0, '0.37'), (1, '0.60'), (2, '0.60'), (3, '0.37')]
83 Raises
84 ------
85 NetworkXPointlessConcept
86 If the graph G is the null graph.
88 NetworkXError
89 If each value in `nstart` is zero.
91 PowerIterationFailedConvergence
92 If the algorithm fails to converge to the specified tolerance
93 within the specified number of iterations of the power iteration
94 method.
96 See Also
97 --------
98 eigenvector_centrality_numpy
99 :func:`~networkx.algorithms.link_analysis.pagerank_alg.pagerank`
100 :func:`~networkx.algorithms.link_analysis.hits_alg.hits`
102 Notes
103 -----
104 Eigenvector centrality was introduced by Landau [2]_ for chess
105 tournaments. It was later rediscovered by Wei [3]_ and then
106 popularized by Kendall [4]_ in the context of sport ranking. Berge
107 introduced a general definition for graphs based on social connections
108 [5]_. Bonacich [6]_ reintroduced again eigenvector centrality and made
109 it popular in link analysis.
111 This function computes the left dominant eigenvector, which corresponds
112 to adding the centrality of predecessors: this is the usual approach.
113 To add the centrality of successors first reverse the graph with
114 ``G.reverse()``.
116 The implementation uses power iteration [7]_ to compute a dominant
117 eigenvector starting from the provided vector `nstart`. Convergence is
118 guaranteed as long as `nstart` has a nonzero projection on a dominant
119 eigenvector, which certainly happens using the default value.
121 The method stops when the change in the computed vector between two
122 iterations is smaller than an error tolerance of ``G.number_of_nodes()
123 * tol`` or after ``max_iter`` iterations, but in the second case it
124 raises an exception.
126 This implementation uses $(A + I)$ rather than the adjacency matrix
127 $A$ because the change preserves eigenvectors, but it shifts the
128 spectrum, thus guaranteeing convergence even for networks with
129 negative eigenvalues of maximum modulus.
131 References
132 ----------
133 .. [1] Abraham Berman and Robert J. Plemmons.
134 "Nonnegative Matrices in the Mathematical Sciences."
135 Classics in Applied Mathematics. SIAM, 1994.
137 .. [2] Edmund Landau.
138 "Zur relativen Wertbemessung der Turnierresultate."
139 Deutsches Wochenschach, 11:366–369, 1895.
141 .. [3] Teh-Hsing Wei.
142 "The Algebraic Foundations of Ranking Theory."
143 PhD thesis, University of Cambridge, 1952.
145 .. [4] Maurice G. Kendall.
146 "Further contributions to the theory of paired comparisons."
147 Biometrics, 11(1):43–62, 1955.
148 https://www.jstor.org/stable/3001479
150 .. [5] Claude Berge
151 "Théorie des graphes et ses applications."
152 Dunod, Paris, France, 1958.
154 .. [6] Phillip Bonacich.
155 "Technique for analyzing overlapping memberships."
156 Sociological Methodology, 4:176–185, 1972.
157 https://www.jstor.org/stable/270732
159 .. [7] Power iteration:: https://en.wikipedia.org/wiki/Power_iteration
161 """
162 if len(G) == 0:
163 raise nx.NetworkXPointlessConcept(
164 "cannot compute centrality for the null graph"
165 )
166 # If no initial vector is provided, start with the all-ones vector.
167 if nstart is None:
168 nstart = {v: 1 for v in G}
169 if all(v == 0 for v in nstart.values()):
170 raise nx.NetworkXError("initial vector cannot have all zero values")
171 # Normalize the initial vector so that each entry is in [0, 1]. This is
172 # guaranteed to never have a divide-by-zero error by the previous line.
173 nstart_sum = sum(nstart.values())
174 x = {k: v / nstart_sum for k, v in nstart.items()}
175 nnodes = G.number_of_nodes()
176 # make up to max_iter iterations
177 for _ in range(max_iter):
178 xlast = x
179 x = xlast.copy() # Start with xlast times I to iterate with (A+I)
180 # do the multiplication y^T = x^T A (left eigenvector)
181 for n in x:
182 for nbr in G[n]:
183 w = G[n][nbr].get(weight, 1) if weight else 1
184 x[nbr] += xlast[n] * w
185 # Normalize the vector. The normalization denominator `norm`
186 # should never be zero by the Perron--Frobenius
187 # theorem. However, in case it is due to numerical error, we
188 # assume the norm to be one instead.
189 norm = math.hypot(*x.values()) or 1
190 x = {k: v / norm for k, v in x.items()}
191 # Check for convergence (in the L_1 norm).
192 if sum(abs(x[n] - xlast[n]) for n in x) < nnodes * tol:
193 return x
194 raise nx.PowerIterationFailedConvergence(max_iter)
197@nx._dispatchable(edge_attrs="weight")
198def eigenvector_centrality_numpy(G, weight=None, max_iter=50, tol=0):
199 r"""Compute the eigenvector centrality for the graph `G`.
201 Eigenvector centrality computes the centrality for a node by adding
202 the centrality of its predecessors. The centrality for node $i$ is the
203 $i$-th element of a left eigenvector associated with the eigenvalue $\lambda$
204 of maximum modulus that is positive. Such an eigenvector $x$ is
205 defined up to a multiplicative constant by the equation
207 .. math::
209 \lambda x^T = x^T A,
211 where $A$ is the adjacency matrix of the graph `G`. By definition of
212 row-column product, the equation above is equivalent to
214 .. math::
216 \lambda x_i = \sum_{j\to i}x_j.
218 That is, adding the eigenvector centralities of the predecessors of
219 $i$ one obtains the eigenvector centrality of $i$ multiplied by
220 $\lambda$. In the case of undirected graphs, $x$ also solves the familiar
221 right-eigenvector equation $Ax = \lambda x$.
223 By virtue of the Perron--Frobenius theorem [1]_, if `G` is (strongly)
224 connected, there is a unique eigenvector $x$, and all its entries
225 are strictly positive.
227 However, if `G` is not (strongly) connected, there might be several left
228 eigenvectors associated with $\lambda$, and some of their elements
229 might be zero.
230 Depending on the method used to choose eigenvectors, round-off error can affect
231 which of the infinitely many eigenvectors is reported.
232 This can lead to inconsistent results for the same graph,
233 which the underlying implementation is not robust to.
234 For this reason, only (strongly) connected graphs are accepted.
236 Parameters
237 ----------
238 G : graph
239 A connected NetworkX graph.
241 weight : None or string, optional (default=None)
242 If ``None``, all edge weights are considered equal. Otherwise holds the
243 name of the edge attribute used as weight. In this measure the
244 weight is interpreted as the connection strength.
246 max_iter : integer, optional (default=50)
247 Maximum number of Arnoldi update iterations allowed.
249 tol : float, optional (default=0)
250 Relative accuracy for eigenvalues (stopping criterion).
251 The default value of 0 implies machine precision.
253 Returns
254 -------
255 nodes : dict of nodes
256 Dictionary of nodes with eigenvector centrality as the value. The
257 associated vector has unit Euclidean norm and the values are
258 nonnegative.
260 Examples
261 --------
262 >>> G = nx.path_graph(4)
263 >>> centrality = nx.eigenvector_centrality_numpy(G)
264 >>> print([f"{node} {centrality[node]:0.2f}" for node in centrality])
265 ['0 0.37', '1 0.60', '2 0.60', '3 0.37']
267 Raises
268 ------
269 NetworkXPointlessConcept
270 If the graph `G` is the null graph.
272 ArpackNoConvergence
273 When the requested convergence is not obtained. The currently
274 converged eigenvalues and eigenvectors can be found as
275 eigenvalues and eigenvectors attributes of the exception object.
277 AmbiguousSolution
278 If `G` is not connected.
280 See Also
281 --------
282 :func:`scipy.sparse.linalg.eigs`
283 eigenvector_centrality
284 :func:`~networkx.algorithms.link_analysis.pagerank_alg.pagerank`
285 :func:`~networkx.algorithms.link_analysis.hits_alg.hits`
287 Notes
288 -----
289 Eigenvector centrality was introduced by Landau [2]_ for chess
290 tournaments. It was later rediscovered by Wei [3]_ and then
291 popularized by Kendall [4]_ in the context of sport ranking. Berge
292 introduced a general definition for graphs based on social connections
293 [5]_. Bonacich [6]_ reintroduced again eigenvector centrality and made
294 it popular in link analysis.
296 This function computes the left dominant eigenvector, which corresponds
297 to adding the centrality of predecessors: this is the usual approach.
298 To add the centrality of successors first reverse the graph with
299 ``G.reverse()``.
301 This implementation uses the
302 :func:`SciPy sparse eigenvalue solver<scipy.sparse.linalg.eigs>` (ARPACK)
303 to find the largest eigenvalue/eigenvector pair using Arnoldi iterations
304 [7]_.
306 References
307 ----------
308 .. [1] Abraham Berman and Robert J. Plemmons.
309 "Nonnegative Matrices in the Mathematical Sciences".
310 Classics in Applied Mathematics. SIAM, 1994.
312 .. [2] Edmund Landau.
313 "Zur relativen Wertbemessung der Turnierresultate".
314 Deutsches Wochenschach, 11:366--369, 1895.
316 .. [3] Teh-Hsing Wei.
317 "The Algebraic Foundations of Ranking Theory".
318 PhD thesis, University of Cambridge, 1952.
320 .. [4] Maurice G. Kendall.
321 "Further contributions to the theory of paired comparisons".
322 Biometrics, 11(1):43--62, 1955.
323 https://www.jstor.org/stable/3001479
325 .. [5] Claude Berge.
326 "Théorie des graphes et ses applications".
327 Dunod, Paris, France, 1958.
329 .. [6] Phillip Bonacich.
330 "Technique for analyzing overlapping memberships".
331 Sociological Methodology, 4:176--185, 1972.
332 https://www.jstor.org/stable/270732
334 .. [7] Arnoldi, W. E. (1951).
335 "The principle of minimized iterations in the solution of the matrix eigenvalue problem".
336 Quarterly of Applied Mathematics. 9 (1): 17--29.
337 https://doi.org/10.1090/qam/42792
338 """
339 import numpy as np
340 import scipy as sp
342 if len(G) == 0:
343 raise nx.NetworkXPointlessConcept(
344 "cannot compute centrality for the null graph"
345 )
346 connected = nx.is_strongly_connected(G) if G.is_directed() else nx.is_connected(G)
347 if not connected: # See gh-6888.
348 raise nx.AmbiguousSolution(
349 "`eigenvector_centrality_numpy` does not give consistent results for disconnected graphs"
350 )
351 M = nx.to_scipy_sparse_array(G, nodelist=list(G), weight=weight, dtype=float)
352 _, eigenvector = sp.sparse.linalg.eigs(
353 M.T, k=1, which="LR", maxiter=max_iter, tol=tol
354 )
355 largest = eigenvector.flatten().real
356 norm = np.sign(largest.sum()) * sp.linalg.norm(largest)
357 return dict(zip(G, (largest / norm).tolist()))