Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/centrality/eigenvector.py: 23%

1"""Functions for computing eigenvector centrality.""" 

2import math 

3 

4import networkx as nx 

5from networkx.utils import not_implemented_for 

6 

7__all__ = ["eigenvector_centrality", "eigenvector_centrality_numpy"] 

8 

9 

10@not_implemented_for("multigraph") 

11@nx._dispatch(edge_attrs="weight") 

12def 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 by adding 

16 the centrality of its predecessors. The centrality for node $i$ is the 

17 $i$-th element of a left eigenvector associated with the eigenvalue $\lambda$ 

18 of maximum modulus that is positive. Such an eigenvector $x$ is 

19 defined up to a multiplicative constant by the equation 

20 

21 .. math:: 

22 

23 \lambda x^T = x^T A, 

24 

25 where $A$ is the adjacency matrix of the graph G. By definition of 

26 row-column product, the equation above is equivalent to 

27 

28 .. math:: 

29 

30 \lambda x_i = \sum_{j\to i}x_j. 

31 

32 That is, adding the eigenvector centralities of the predecessors of 

33 $i$ one obtains the eigenvector centrality of $i$ multiplied by 

34 $\lambda$. In the case of undirected graphs, $x$ also solves the familiar 

35 right-eigenvector equation $Ax = \lambda x$. 

36 

37 By virtue of the Perron–Frobenius theorem [1]_, if G is strongly 

38 connected there is a unique eigenvector $x$, and all its entries 

39 are strictly positive. 

40 

41 If G is not strongly connected there might be several left 

42 eigenvectors associated with $\lambda$, and some of their elements 

43 might be zero. 

44 

45 Parameters 

46 ---------- 

47 G : graph 

48 A networkx graph. 

49 

50 max_iter : integer, optional (default=100) 

51 Maximum number of power iterations. 

52 

53 tol : float, optional (default=1.0e-6) 

54 Error tolerance (in Euclidean norm) used to check convergence in 

55 power iteration. 

56 

57 nstart : dictionary, optional (default=None) 

58 Starting value of power iteration for each node. Must have a nonzero 

59 projection on the desired eigenvector for the power method to converge. 

60 If None, this implementation uses an all-ones vector, which is a safe 

61 choice. 

62 

63 weight : None or string, optional (default=None) 

64 If None, all edge weights are considered equal. Otherwise holds the 

65 name of the edge attribute used as weight. In this measure the 

66 weight is interpreted as the connection strength. 

67 

68 Returns 

69 ------- 

70 nodes : dictionary 

71 Dictionary of nodes with eigenvector centrality as the value. The 

72 associated vector has unit Euclidean norm and the values are 

73 nonegative. 

74 

75 Examples 

76 -------- 

77 >>> G = nx.path_graph(4) 

78 >>> centrality = nx.eigenvector_centrality(G) 

79 >>> sorted((v, f"{c:0.2f}") for v, c in centrality.items()) 

80 [(0, '0.37'), (1, '0.60'), (2, '0.60'), (3, '0.37')] 

81 

82 Raises 

83 ------ 

84 NetworkXPointlessConcept 

85 If the graph G is the null graph. 

86 

87 NetworkXError 

88 If each value in `nstart` is zero. 

89 

90 PowerIterationFailedConvergence 

91 If the algorithm fails to converge to the specified tolerance 

92 within the specified number of iterations of the power iteration 

93 method. 

94 

95 See Also 

96 -------- 

97 eigenvector_centrality_numpy 

98 :func:`~networkx.algorithms.link_analysis.pagerank_alg.pagerank` 

99 :func:`~networkx.algorithms.link_analysis.hits_alg.hits` 

100 

101 Notes 

102 ----- 

103 Eigenvector centrality was introduced by Landau [2]_ for chess 

104 tournaments. It was later rediscovered by Wei [3]_ and then 

105 popularized by Kendall [4]_ in the context of sport ranking. Berge 

106 introduced a general definition for graphs based on social connections 

107 [5]_. Bonacich [6]_ reintroduced again eigenvector centrality and made 

108 it popular in link analysis. 

109 

110 This function computes the left dominant eigenvector, which corresponds 

111 to adding the centrality of predecessors: this is the usual approach. 

112 To add the centrality of successors first reverse the graph with 

113 ``G.reverse()``. 

114 

115 The implementation uses power iteration [7]_ to compute a dominant 

116 eigenvector starting from the provided vector `nstart`. Convergence is 

117 guaranteed as long as `nstart` has a nonzero projection on a dominant 

118 eigenvector, which certainly happens using the default value. 

119 

120 The method stops when the change in the computed vector between two 

121 iterations is smaller than an error tolerance of ``G.number_of_nodes() 

122 * tol`` or after ``max_iter`` iterations, but in the second case it 

123 raises an exception. 

124 

125 This implementation uses $(A + I)$ rather than the adjacency matrix 

126 $A$ because the change preserves eigenvectors, but it shifts the 

127 spectrum, thus guaranteeing convergence even for networks with 

128 negative eigenvalues of maximum modulus. 

129 

130 References 

131 ---------- 

132 .. [1] Abraham Berman and Robert J. Plemmons. 

133 "Nonnegative Matrices in the Mathematical Sciences." 

134 Classics in Applied Mathematics. SIAM, 1994. 

135 

136 .. [2] Edmund Landau. 

137 "Zur relativen Wertbemessung der Turnierresultate." 

138 Deutsches Wochenschach, 11:366–369, 1895. 

139 

140 .. [3] Teh-Hsing Wei. 

141 "The Algebraic Foundations of Ranking Theory." 

142 PhD thesis, University of Cambridge, 1952. 

143 

144 .. [4] Maurice G. Kendall. 

145 "Further contributions to the theory of paired comparisons." 

146 Biometrics, 11(1):43–62, 1955. 

147 https://www.jstor.org/stable/3001479 

148 

149 .. [5] Claude Berge 

150 "Théorie des graphes et ses applications." 

151 Dunod, Paris, France, 1958. 

152 

153 .. [6] Phillip Bonacich. 

154 "Technique for analyzing overlapping memberships." 

155 Sociological Methodology, 4:176–185, 1972. 

156 https://www.jstor.org/stable/270732 

157 

158 .. [7] Power iteration:: https://en.wikipedia.org/wiki/Power_iteration 

159 

160 """ 

161 if len(G) == 0: 

162 raise nx.NetworkXPointlessConcept( 

163 "cannot compute centrality for the null graph" 

164 ) 

165 # If no initial vector is provided, start with the all-ones vector. 

166 if nstart is None: 

167 nstart = {v: 1 for v in G} 

168 if all(v == 0 for v in nstart.values()): 

169 raise nx.NetworkXError("initial vector cannot have all zero values") 

170 # Normalize the initial vector so that each entry is in [0, 1]. This is 

171 # guaranteed to never have a divide-by-zero error by the previous line. 

172 nstart_sum = sum(nstart.values()) 

173 x = {k: v / nstart_sum for k, v in nstart.items()} 

174 nnodes = G.number_of_nodes() 

175 # make up to max_iter iterations 

176 for _ in range(max_iter): 

177 xlast = x 

178 x = xlast.copy() # Start with xlast times I to iterate with (A+I) 

179 # do the multiplication y^T = x^T A (left eigenvector) 

180 for n in x: 

181 for nbr in G[n]: 

182 w = G[n][nbr].get(weight, 1) if weight else 1 

183 x[nbr] += xlast[n] * w 

184 # Normalize the vector. The normalization denominator `norm` 

185 # should never be zero by the Perron--Frobenius 

186 # theorem. However, in case it is due to numerical error, we 

187 # assume the norm to be one instead. 

188 norm = math.hypot(*x.values()) or 1 

189 x = {k: v / norm for k, v in x.items()} 

190 # Check for convergence (in the L_1 norm). 

191 if sum(abs(x[n] - xlast[n]) for n in x) < nnodes * tol: 

192 return x 

193 raise nx.PowerIterationFailedConvergence(max_iter) 

194 

195 

196@nx._dispatch(edge_attrs="weight") 

197def eigenvector_centrality_numpy(G, weight=None, max_iter=50, tol=0): 

198 r"""Compute the eigenvector centrality for the graph G. 

199 

200 Eigenvector centrality computes the centrality for a node by adding 

201 the centrality of its predecessors. The centrality for node $i$ is the 

202 $i$-th element of a left eigenvector associated with the eigenvalue $\lambda$ 

203 of maximum modulus that is positive. Such an eigenvector $x$ is 

204 defined up to a multiplicative constant by the equation 

205 

206 .. math:: 

207 

208 \lambda x^T = x^T A, 

209 

210 where $A$ is the adjacency matrix of the graph G. By definition of 

211 row-column product, the equation above is equivalent to 

212 

213 .. math:: 

214 

215 \lambda x_i = \sum_{j\to i}x_j. 

216 

217 That is, adding the eigenvector centralities of the predecessors of 

218 $i$ one obtains the eigenvector centrality of $i$ multiplied by 

219 $\lambda$. In the case of undirected graphs, $x$ also solves the familiar 

220 right-eigenvector equation $Ax = \lambda x$. 

221 

222 By virtue of the Perron–Frobenius theorem [1]_, if G is strongly 

223 connected there is a unique eigenvector $x$, and all its entries 

224 are strictly positive. 

225 

226 If G is not strongly connected there might be several left 

227 eigenvectors associated with $\lambda$, and some of their elements 

228 might be zero. 

229 

230 Parameters 

231 ---------- 

232 G : graph 

233 A networkx graph. 

234 

235 max_iter : integer, optional (default=50) 

236 Maximum number of Arnoldi update iterations allowed. 

237 

238 tol : float, optional (default=0) 

239 Relative accuracy for eigenvalues (stopping criterion). 

240 The default value of 0 implies machine precision. 

241 

242 weight : None or string, optional (default=None) 

243 If None, all edge weights are considered equal. Otherwise holds the 

244 name of the edge attribute used as weight. In this measure the 

245 weight is interpreted as the connection strength. 

246 

247 Returns 

248 ------- 

249 nodes : dictionary 

250 Dictionary of nodes with eigenvector centrality as the value. The 

251 associated vector has unit Euclidean norm and the values are 

252 nonegative. 

253 

254 Examples 

255 -------- 

256 >>> G = nx.path_graph(4) 

257 >>> centrality = nx.eigenvector_centrality_numpy(G) 

258 >>> print([f"{node} {centrality[node]:0.2f}" for node in centrality]) 

259 ['0 0.37', '1 0.60', '2 0.60', '3 0.37'] 

260 

261 Raises 

262 ------ 

263 NetworkXPointlessConcept 

264 If the graph G is the null graph. 

265 

266 ArpackNoConvergence 

267 When the requested convergence is not obtained. The currently 

268 converged eigenvalues and eigenvectors can be found as 

269 eigenvalues and eigenvectors attributes of the exception object. 

270 

271 See Also 

272 -------- 

273 :func:`scipy.sparse.linalg.eigs` 

274 eigenvector_centrality 

275 :func:`~networkx.algorithms.link_analysis.pagerank_alg.pagerank` 

276 :func:`~networkx.algorithms.link_analysis.hits_alg.hits` 

277 

278 Notes 

279 ----- 

280 Eigenvector centrality was introduced by Landau [2]_ for chess 

281 tournaments. It was later rediscovered by Wei [3]_ and then 

282 popularized by Kendall [4]_ in the context of sport ranking. Berge 

283 introduced a general definition for graphs based on social connections 

284 [5]_. Bonacich [6]_ reintroduced again eigenvector centrality and made 

285 it popular in link analysis. 

286 

287 This function computes the left dominant eigenvector, which corresponds 

288 to adding the centrality of predecessors: this is the usual approach. 

289 To add the centrality of successors first reverse the graph with 

290 ``G.reverse()``. 

291 

292 This implementation uses the 

293 :func:`SciPy sparse eigenvalue solver<scipy.sparse.linalg.eigs>` (ARPACK) 

294 to find the largest eigenvalue/eigenvector pair using Arnoldi iterations 

295 [7]_. 

296 

297 References 

298 ---------- 

299 .. [1] Abraham Berman and Robert J. Plemmons. 

300 "Nonnegative Matrices in the Mathematical Sciences." 

301 Classics in Applied Mathematics. SIAM, 1994. 

302 

303 .. [2] Edmund Landau. 

304 "Zur relativen Wertbemessung der Turnierresultate." 

305 Deutsches Wochenschach, 11:366–369, 1895. 

306 

307 .. [3] Teh-Hsing Wei. 

308 "The Algebraic Foundations of Ranking Theory." 

309 PhD thesis, University of Cambridge, 1952. 

310 

311 .. [4] Maurice G. Kendall. 

312 "Further contributions to the theory of paired comparisons." 

313 Biometrics, 11(1):43–62, 1955. 

314 https://www.jstor.org/stable/3001479 

315 

316 .. [5] Claude Berge 

317 "Théorie des graphes et ses applications." 

318 Dunod, Paris, France, 1958. 

319 

320 .. [6] Phillip Bonacich. 

321 "Technique for analyzing overlapping memberships." 

322 Sociological Methodology, 4:176–185, 1972. 

323 https://www.jstor.org/stable/270732 

324 

325 .. [7] Arnoldi iteration:: https://en.wikipedia.org/wiki/Arnoldi_iteration 

326 

327 """ 

328 import numpy as np 

329 import scipy as sp 

330 

331 if len(G) == 0: 

332 raise nx.NetworkXPointlessConcept( 

333 "cannot compute centrality for the null graph" 

334 ) 

335 M = nx.to_scipy_sparse_array(G, nodelist=list(G), weight=weight, dtype=float) 

336 _, eigenvector = sp.sparse.linalg.eigs( 

337 M.T, k=1, which="LR", maxiter=max_iter, tol=tol 

338 ) 

339 largest = eigenvector.flatten().real 

340 norm = np.sign(largest.sum()) * sp.linalg.norm(largest) 

341 return dict(zip(G, largest / norm))