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
167
168
169
170
171
172
|
"""
Eigenvector centrality.
"""
# Copyright (C) 2004-2014 by
# Aric Hagberg <hagberg@lanl.gov>
# Dan Schult <dschult@colgate.edu>
# Pieter Swart <swart@lanl.gov>
# All rights reserved.
# BSD license.
import networkx as nx
__author__ = "\n".join(['Aric Hagberg (aric.hagberg@gmail.com)',
'Pieter Swart (swart@lanl.gov)',
'Sasha Gutfraind (ag362@cornell.edu)'])
__all__ = ['eigenvector_centrality',
'eigenvector_centrality_numpy']
def eigenvector_centrality(G, max_iter=100, tol=1.0e-6, nstart=None,
weight='weight'):
"""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.
weight : None or string, optional
If None, all edge weights are considered equal.
Otherwise holds the name of the edge attribute used as weight.
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 "left" eigevector centrality which corresponds
to the in-edges in the graph. For out-edges 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 nx.NetworkXException("Not defined for multigraphs.")
if len(G) == 0:
raise nx.NetworkXException("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, 0)
# do the multiplication y^T = x^T A
for n in x:
for nbr in G[n]:
x[nbr] += xlast[n] * G[n][nbr].get(weight, 1)
# normalize vector
try:
s = 1.0/sqrt(sum(v**2 for v in x.values()))
# this should never be zero?
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, weight='weight'):
"""Compute the eigenvector centrality for the graph G.
Parameters
----------
G : graph
A networkx graph
weight : None or string, optional
The name of the edge attribute used as weight.
If None, all edge weights are considered equal.
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 SciPy sparse eigenvalue solver (ARPACK) to
find the largest eigenvalue/eigenvector pair.
For directed graphs this is "left" eigevector centrality which corresponds
to the in-edges in the graph. For out-edges eigenvector centrality
first reverse the graph with G.reverse().
See Also
--------
eigenvector_centrality
pagerank
hits
"""
import scipy as sp
from scipy.sparse import linalg
if len(G) == 0:
raise nx.NetworkXException('Empty graph.')
M = nx.to_scipy_sparse_matrix(G, nodelist=G.nodes(), weight=weight,
dtype=float)
eigenvalue, eigenvector = linalg.eigs(M.T, k=1, which='LR')
largest = eigenvector.flatten().real
norm = sp.sign(largest.sum())*sp.linalg.norm(largest)
centrality = dict(zip(G,map(float,largest/norm)))
return centrality
# fixture for nose tests
def setup_module(module):
from nose import SkipTest
try:
import scipy
except:
raise SkipTest("SciPy not available")
|
