← Back to branch summary

~ubuntu-branches/ubuntu/utopic/python-networkx/utopic

« back to all changes in this revision

Viewing changes to networkx/algorithms/centrality/eigenvector.py

  • Committer: Package Import Robot
  • Author(s): Sandro Tosi
  • Date: 2012-08-11 12:41:30 UTC
  • mfrom: (1.4.1) (5.1.13 sid)
  • Revision ID: package-import@ubuntu.com-20120811124130-whr6uso7fncyg8bi
Tags: 1.7-1
* New upstream release
* debian/patches/changeset_*
  - removed, included upstream

Show diffs side-by-side

added added

removed removed

Lines of Context:
networkx/algorithms/centrality/eigenvector.py
1
1
"""
2
2
Eigenvector centrality.
3
 
 
4
3
"""
5
 
#    Copyright (C) 2004-2010 by 
 
4
#    Copyright (C) 2004-2011 by 
6
5
#    Aric Hagberg <hagberg@lanl.gov>
7
6
#    Dan Schult <dschult@colgate.edu>
8
7
#    Pieter Swart <swart@lanl.gov>
9
8
#    All rights reserved.
10
9
#    BSD license.
 
10
import networkx as nx
11
11
__author__ = "\n".join(['Aric Hagberg (hagberg@lanl.gov)',
12
12
                        'Pieter Swart (swart@lanl.gov)',
13
13
                        'Sasha Gutfraind (ag362@cornell.edu)'])
14
 
 
15
14
__all__ = ['eigenvector_centrality',
16
15
           'eigenvector_centrality_numpy']
17
16
 
18
 
import networkx as nx
19
 
 
20
17
def eigenvector_centrality(G,max_iter=100,tol=1.0e-6,nstart=None):
21
18
    """Compute the eigenvector centrality for the graph G.
22
19
 
68
65
    """
69
66
    from math import sqrt
70
67
    if type(G) == nx.MultiGraph or type(G) == nx.MultiDiGraph:
71
 
        raise Exception(\
72
 
            "eigenvector_centrality() not defined for multigraphs.")
 
68
        raise nx.NetworkXException("Not defined for multigraphs.")
73
69
 
74
70
    if len(G)==0:
75
 
        raise nx.NetworkXException(\
76
 
            "eigenvector_centrality_numpy(): empty graph.")
 
71
        raise nx.NetworkXException("Empty graph.")
77
72
 
78
73
    if nstart is None:
79
74
        # choose starting vector with entries of 1/len(G) 
87
82
    # make up to max_iter iterations        
88
83
    for i in range(max_iter):
89
84
        xlast=x
90
 
        x=dict.fromkeys(list(xlast.keys()),0)
 
85
        x=dict.fromkeys(xlast, 0)
91
86
        # do the multiplication y=Ax
92
87
        for n in x:
93
88
            for nbr in G[n]:
95
90
        # normalize vector
96
91
        try:
97
92
            s=1.0/sqrt(sum(v**2 for v in x.values()))
 
93
        # this should never be zero?
98
94
        except ZeroDivisionError:
99
95
            s=1.0
100
96
        for n in x: x[n]*=s
144
140
    try:
145
141
        import numpy as np
146
142
    except ImportError:
147
 
        raise ImportError(\
148
 
            "eigenvector_centrality_numpy() requires NumPy: http://scipy.org/")
 
143
        raise ImportError('Requires NumPy: http://scipy.org/')
149
144
 
150
145
    if type(G) == nx.MultiGraph or type(G) == nx.MultiDiGraph:
151
 
        raise Exception(\
152
 
            "eigenvector_centrality_numpy() not defined for multigraphs.")
 
146
        raise nx.NetworkXException('Not defined for multigraphs.')
153
147
 
154
148
    if len(G)==0:
155
 
        raise nx.NetworkXException(\
156
 
            "eigenvector_centrality_numpy(): empty graph.")
 
149
        raise nx.NetworkXException('Empty graph.')
157
150
 
158
151
    A=nx.adj_matrix(G,nodelist=G.nodes())
159
152
    eigenvalues,eigenvectors=np.linalg.eig(A)
160
153
    # eigenvalue indices in reverse sorted order
161
154
    ind=eigenvalues.argsort()[::-1]
162
155
    # eigenvector of largest eigenvalue at ind[0], normalized
163
 
    largest=np.array(eigenvectors[:,ind[0]]).flatten()
 
156
    largest=np.array(eigenvectors[:,ind[0]]).flatten().real
164
157
    norm=np.sign(largest.sum())*np.linalg.norm(largest)
165
 
    centrality=dict(zip(G,largest/norm))
 
158
    centrality=dict(zip(G,map(float,largest/norm)))
166
159
    return centrality
167
160
 
168
161
 
170
163
def setup_module(module):
171
164
    from nose import SkipTest
172
165
    try:
173
 
        import pyparsing
 
166
        import numpy
 
167
        import numpy.linalg
174
168
    except:
175
 
        raise SkipTest("pyparsing not available")
 
169
        raise SkipTest("numpy not available")