## Mercurial > repos > shellac > sam_consensus_v3

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

Find changesets by keywords (author, files, the commit message), revision
number or hash, or revset expression.

"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)) |