Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/centrality/eigenvector.py @ 0:4f3585e2f14b draft default tip
"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
author | shellac |
---|---|
date | Mon, 22 Mar 2021 18:12:50 +0000 |
parents | |
children |
comparison
equal
deleted
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 | |
71 See Also | |
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 | |
183 See Also | |
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)) |