1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
|
"""
Eigenvector centrality.
"""
# Copyright (C) 2004-2010 by
# Aric Hagberg <hagberg@lanl.gov>
# Dan Schult <dschult@colgate.edu>
# Pieter Swart <swart@lanl.gov>
# All rights reserved.
# BSD license.
__author__ = "\n".join(['Aric Hagberg (hagberg@lanl.gov)',
'Pieter Swart (swart@lanl.gov)',
'Sasha Gutfraind (ag362@cornell.edu)'])
__all__ = ['eigenvector_centrality',
'eigenvector_centrality_numpy']
import networkx as nx
def eigenvector_centrality(G,max_iter=100,tol=1.0e-6,nstart=None):
"""Compute the eigenvector centrality for the graph G.
Uses the power method to find the eigenvector for the
largest eigenvalue of the adjacency matrix of G.
Parameters
----------
G : graph
A networkx graph
max_iter : interger, optional
Maximum number of iterations in power method.
tol : float, optional
Error tolerance used to check convergence in power method iteration.
nstart : dictionary, optional
Starting value of eigenvector iteration for each node.
Returns
-------
nodes : dictionary
Dictionary of nodes with eigenvector centrality as the value.
Examples
--------
>>> G=nx.path_graph(4)
>>> centrality=nx.eigenvector_centrality(G)
>>> print(['%s %0.2f'%(node,centrality[node]) for node in centrality])
['0 0.37', '1 0.60', '2 0.60', '3 0.37']
Notes
------
The eigenvector calculation is done by the power iteration method
and has no guarantee of convergence. The iteration will stop
after max_iter iterations or an error tolerance of
number_of_nodes(G)*tol has been reached.
For directed graphs this is "right" eigevector centrality. For
"left" eigenvector centrality, first reverse the graph with
G.reverse().
See Also
--------
eigenvector_centrality_numpy
pagerank
hits
"""
from math import sqrt
if type(G) == nx.MultiGraph or type(G) == nx.MultiDiGraph:
raise Exception(\
"eigenvector_centrality() not defined for multigraphs.")
if len(G)==0:
raise nx.NetworkXException(\
"eigenvector_centrality_numpy(): empty graph.")
if nstart is None:
# choose starting vector with entries of 1/len(G)
x=dict([(n,1.0/len(G)) for n in G])
else:
x=nstart
# normalize starting vector
s=1.0/sum(x.values())
for k in x: x[k]*=s
nnodes=G.number_of_nodes()
# make up to max_iter iterations
for i in range(max_iter):
xlast=x
x=dict.fromkeys(xlast.keys(),0)
# do the multiplication y=Ax
for n in x:
for nbr in G[n]:
x[n]+=xlast[nbr]*G[n][nbr].get('weight',1)
# normalize vector
try:
s=1.0/sqrt(sum(v**2 for v in x.values()))
except ZeroDivisionError:
s=1.0
for n in x: x[n]*=s
# check convergence
err=sum([abs(x[n]-xlast[n]) for n in x])
if err < nnodes*tol:
return x
raise nx.NetworkXError("""eigenvector_centrality():
power iteration failed to converge in %d iterations."%(i+1))""")
def eigenvector_centrality_numpy(G):
"""Compute the eigenvector centrality for the graph G.
Parameters
----------
G : graph
A networkx graph
Returns
-------
nodes : dictionary
Dictionary of nodes with eigenvector centrality as the value.
Examples
--------
>>> G=nx.path_graph(4)
>>> centrality=nx.eigenvector_centrality_numpy(G)
>>> print(['%s %0.2f'%(node,centrality[node]) for node in centrality])
['0 0.37', '1 0.60', '2 0.60', '3 0.37']
Notes
------
This algorithm uses the NumPy eigenvalue solver.
For directed graphs this is "right" eigevector centrality. For
"left" eigenvector centrality, first reverse the graph with
G.reverse().
See Also
--------
eigenvector_centrality
pagerank
hits
"""
try:
import numpy as np
except ImportError:
raise ImportError(\
"eigenvector_centrality_numpy() requires NumPy: http://scipy.org/")
if type(G) == nx.MultiGraph or type(G) == nx.MultiDiGraph:
raise Exception(\
"eigenvector_centrality_numpy() not defined for multigraphs.")
if len(G)==0:
raise nx.NetworkXException(\
"eigenvector_centrality_numpy(): empty graph.")
A=nx.adj_matrix(G,nodelist=G.nodes())
eigenvalues,eigenvectors=np.linalg.eig(A)
# eigenvalue indices in reverse sorted order
ind=eigenvalues.argsort()[::-1]
# eigenvector of largest eigenvalue at ind[0], normalized
largest=np.array(eigenvectors[:,ind[0]]).flatten()
norm=np.sign(largest.sum())*np.linalg.norm(largest)
centrality=dict(zip(G,largest/norm))
return centrality
|
