ioftools / networkxMiCe / networkxmaster / networkx / algorithms / centrality / eigenvector.py @ 5cef0f13
History  View  Annotate  Download (8.47 KB)
1 
# * coding: utf8 *


2 
# Copyright (C) 20042019 by

3 
# Aric Hagberg <hagberg@lanl.gov>

4 
# Dan Schult <dschult@colgate.edu>

5 
# Pieter Swart <swart@lanl.gov>

6 
# All rights reserved.

7 
# BSD license.

8 
#

9 
# Authors:

10 
# Aric Hagberg <aric.hagberg@gmail.com>

11 
# Pieter Swart <swart@lanl.gov>

12 
# Sasha Gutfraind <ag362@cornell.edu>

13 
"""Functions for computing eigenvector centrality."""

14 
from __future__ import division 
15  
16 
from math import sqrt 
17  
18 
import networkx as nx 
19 
from networkx.utils import not_implemented_for 
20  
21 
__all__ = ['eigenvector_centrality', 'eigenvector_centrality_numpy'] 
22  
23  
24 
@not_implemented_for('multigraph') 
25 
def eigenvector_centrality(G, max_iter=100, tol=1.0e6, nstart=None, 
26 
weight=None):

27 
r"""Compute the eigenvector centrality for the graph `G`.

28 

29 
Eigenvector centrality computes the centrality for a node based on the

30 
centrality of its neighbors. The eigenvector centrality for node $i$ is

31 
the $i$th element of the vector $x$ defined by the equation

32 

33 
.. math::

34 

35 
Ax = \lambda x

36 

37 
where $A$ is the adjacency matrix of the graph `G` with eigenvalue

38 
$\lambda$. By virtue of the Perron–Frobenius theorem, there is a unique

39 
solution $x$, all of whose entries are positive, if $\lambda$ is the

40 
largest eigenvalue of the adjacency matrix $A$ ([2]_).

41 

42 
Parameters

43 


44 
G : graph

45 
A networkx graph

46 

47 
max_iter : integer, optional (default=100)

48 
Maximum number of iterations in power method.

49 

50 
tol : float, optional (default=1.0e6)

51 
Error tolerance used to check convergence in power method iteration.

52 

53 
nstart : dictionary, optional (default=None)

54 
Starting value of eigenvector iteration for each node.

55 

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

57 
If None, all edge weights are considered equal.

58 
Otherwise holds the name of the edge attribute used as weight.

59 

60 
Returns

61 


62 
nodes : dictionary

63 
Dictionary of nodes with eigenvector centrality as the value.

64 

65 
Examples

66 


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

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

69 
>>> sorted((v, '{:0.2f}'.format(c)) for v, c in centrality.items())

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

71 

72 
Raises

73 


74 
NetworkXPointlessConcept

75 
If the graph `G` is the null graph.

76 

77 
NetworkXError

78 
If each value in `nstart` is zero.

79 

80 
PowerIterationFailedConvergence

81 
If the algorithm fails to converge to the specified tolerance

82 
within the specified number of iterations of the power iteration

83 
method.

84 

85 
See Also

86 


87 
eigenvector_centrality_numpy

88 
pagerank

89 
hits

90 

91 
Notes

92 


93 
The measure was introduced by [1]_ and is discussed in [2]_.

94 

95 
The power iteration method is used to compute the eigenvector and

96 
convergence is **not** guaranteed. Our method stops after ``max_iter``

97 
iterations or when the change in the computed vector between two

98 
iterations is smaller than an error tolerance of

99 
``G.number_of_nodes() * tol``. This implementation uses ($A + I$)

100 
rather than the adjacency matrix $A$ because it shifts the spectrum

101 
to enable discerning the correct eigenvector even for networks with

102 
multiple dominant eigenvalues.

103 

104 
For directed graphs this is "left" eigenvector centrality which corresponds

105 
to the inedges in the graph. For outedges eigenvector centrality

106 
first reverse the graph with ``G.reverse()``.

107 

108 
References

109 


110 
.. [1] Phillip Bonacich.

111 
"Power and Centrality: A Family of Measures."

112 
*American Journal of Sociology* 92(5):1170–1182, 1986

113 
<http://www.leonidzhukov.net/hse/2014/socialnetworks/papers/BonacichCentrality.pdf>

114 
.. [2] Mark E. J. Newman.

115 
*Networks: An Introduction.*

116 
Oxford University Press, USA, 2010, pp. 169.

117 

118 
"""

119 
if len(G) == 0: 
120 
raise nx.NetworkXPointlessConcept('cannot compute centrality for the' 
121 
' null graph')

122 
# If no initial vector is provided, start with the allones vector.

123 
if nstart is None: 
124 
nstart = {v: 1 for v in G} 
125 
if all(v == 0 for v in nstart.values()): 
126 
raise nx.NetworkXError('initial vector cannot have all zero values') 
127 
# Normalize the initial vector so that each entry is in [0, 1]. This is

128 
# guaranteed to never have a dividebyzero error by the previous line.

129 
nstart_sum = sum(nstart.values())

130 
x = {k: v / nstart_sum for k, v in nstart.items()} 
131 
nnodes = G.number_of_nodes() 
132 
# make up to max_iter iterations

133 
for i in range(max_iter): 
134 
xlast = x 
135 
x = xlast.copy() # Start with xlast times I to iterate with (A+I)

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

137 
for n in x: 
138 
for nbr in G[n]: 
139 
w = G[n][nbr].get(weight, 1) if weight else 1 
140 
x[nbr] += xlast[n] * w 
141 
# Normalize the vector. The normalization denominator `norm`

142 
# should never be zero by the PerronFrobenius

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

144 
# assume the norm to be one instead.

145 
norm = sqrt(sum(z ** 2 for z in x.values())) or 1 
146 
x = {k: v / norm for k, v in x.items()} 
147 
# Check for convergence (in the L_1 norm).

148 
if sum(abs(x[n]  xlast[n]) for n in x) < nnodes * tol: 
149 
return x

150 
raise nx.PowerIterationFailedConvergence(max_iter)

151  
152  
153 
def eigenvector_centrality_numpy(G, weight=None, max_iter=50, tol=0): 
154 
r"""Compute the eigenvector centrality for the graph G.

155 

156 
Eigenvector centrality computes the centrality for a node based on the

157 
centrality of its neighbors. The eigenvector centrality for node $i$ is

158 

159 
.. math::

160 

161 
Ax = \lambda x

162 

163 
where $A$ is the adjacency matrix of the graph G with eigenvalue $\lambda$.

164 
By virtue of the Perron–Frobenius theorem, there is a unique and positive

165 
solution if $\lambda$ is the largest eigenvalue associated with the

166 
eigenvector of the adjacency matrix $A$ ([2]_).

167 

168 
Parameters

169 


170 
G : graph

171 
A networkx graph

172 

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

174 
The name of the edge attribute used as weight.

175 
If None, all edge weights are considered equal.

176 

177 
max_iter : integer, optional (default=100)

178 
Maximum number of iterations in power method.

179 

180 
tol : float, optional (default=1.0e6)

181 
Relative accuracy for eigenvalues (stopping criterion).

182 
The default value of 0 implies machine precision.

183 

184 
Returns

185 


186 
nodes : dictionary

187 
Dictionary of nodes with eigenvector centrality as the value.

188 

189 
Examples

190 


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

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

193 
>>> print(['{} {:0.2f}'.format(node, centrality[node]) for node in centrality])

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

195 

196 
See Also

197 


198 
eigenvector_centrality

199 
pagerank

200 
hits

201 

202 
Notes

203 


204 
The measure was introduced by [1]_.

205 

206 
This algorithm uses the SciPy sparse eigenvalue solver (ARPACK) to

207 
find the largest eigenvalue/eigenvector pair.

208 

209 
For directed graphs this is "left" eigenvector centrality which corresponds

210 
to the inedges in the graph. For outedges eigenvector centrality

211 
first reverse the graph with ``G.reverse()``.

212 

213 
Raises

214 


215 
NetworkXPointlessConcept

216 
If the graph ``G`` is the null graph.

217 

218 
References

219 


220 
.. [1] Phillip Bonacich:

221 
Power and Centrality: A Family of Measures.

222 
American Journal of Sociology 92(5):1170–1182, 1986

223 
http://www.leonidzhukov.net/hse/2014/socialnetworks/papers/BonacichCentrality.pdf

224 
.. [2] Mark E. J. Newman:

225 
Networks: An Introduction.

226 
Oxford University Press, USA, 2010, pp. 169.

227 
"""

228 
import scipy as sp 
229 
from scipy.sparse import linalg 
230 
if len(G) == 0: 
231 
raise nx.NetworkXPointlessConcept('cannot compute centrality for the' 
232 
' null graph')

233 
M = nx.to_scipy_sparse_matrix(G, nodelist=list(G), weight=weight,

234 
dtype=float)

235 
eigenvalue, eigenvector = linalg.eigs(M.T, k=1, which='LR', 
236 
maxiter=max_iter, tol=tol) 
237 
largest = eigenvector.flatten().real 
238 
norm = sp.sign(largest.sum()) * sp.linalg.norm(largest) 
239 
return dict(zip(G, largest / norm)) 
240  
241  
242 
# fixture for nose tests

243 
def setup_module(module): 
244 
from nose import SkipTest 
245 
try:

246 
import scipy 
247 
except:

248 
raise SkipTest("SciPy not available") 