2
# Copyright (C) 2004-2008 by
3
# Aric Hagberg <hagberg@lanl.gov>
4
# Dan Schult <dschult@colgate.edu>
5
# Pieter Swart <swart@lanl.gov>
8
# NetworkX:http://networkx.lanl.gov/.
9
__author__ = """Aric Hagberg (hagberg@lanl.gov)"""
12
from networkx.exception import NetworkXError
13
__all__ = ['pagerank','pagerank_numpy','pagerank_scipy','google_matrix']
15
def pagerank(G,alpha=0.85,max_iter=100,tol=1.0e-8,nstart=None):
16
"""Return the PageRank of the nodes in the graph.
18
PageRank computes the largest eigenvector of the stochastic
19
adjacency matrix of G.
27
alpha : float, optional
28
Parameter for PageRank, default=0.85
30
max_iter : interger, optional
31
Maximum number of iterations in power method.
34
Error tolerance used to check convergence in power method iteration.
36
nstart : dictionary, optional
37
Starting value of PageRank iteration for each node.
42
Dictionary of nodes with value as PageRank
47
>>> G=nx.DiGraph(nx.path_graph(4))
48
>>> pr=nx.pagerank(G,alpha=0.9)
52
The eigenvector calculation is done by the power iteration method
53
and has no guarantee of convergence. The iteration will stop
54
after max_iter iterations or an error tolerance of
55
number_of_nodes(G)*tol has been reached.
57
The PageRank algorithm was designed for directed graphs but this
58
algorithm does not check if the input graph is directed and will
59
execute on undirected graphs.
62
A. Langville and C. Meyer, "A survey of eigenvector methods of web
63
information retrieval." http://citeseer.ist.psu.edu/713792.html
67
if type(G) == networkx.MultiGraph or type(G) == networkx.MultiDiGraph:
68
raise Exception("pagerank() not defined for graphs with multiedges.")
70
# create a copy in (right) stochastic form
71
W=networkx.stochastic_graph(G)
73
# choose fixed starting vector if not given
75
x=dict.fromkeys(W,1.0/W.number_of_nodes())
78
# normalize starting vector to 1
82
nnodes=W.number_of_nodes()
83
# "dangling" nodes, no links out from them
84
out_degree=W.out_degree(with_labels=True)
85
# dangle=[n for n in W if sum(W[n].values())==0.0]
86
dangle=[n for n in W if out_degree[n]==0.0]
87
# pagerank power iteration: make up to max_iter iterations
88
for i in range(max_iter):
90
x=dict.fromkeys(xlast.keys(),0)
91
danglesum=alpha/nnodes*sum(xlast[n] for n in dangle)
92
teleportsum=(1.0-alpha)/nnodes*sum(xlast.values())
94
# this matrix multiply looks odd because it is
95
# doing a left multiply x^T=xlast^T*W
97
x[nbr]+=alpha*xlast[n]*W[n][nbr]['weight']
98
x[n]+=danglesum+teleportsum
99
# normalize vector to 1
100
s=1.0/sum(x.values())
102
# check convergence, l1 norm
103
err=sum([abs(x[n]-xlast[n]) for n in x])
107
raise NetworkXError("pagerank: power iteration failed to converge in %d iterations."%(i+1))
111
def google_matrix(G,alpha=0.85,nodelist=None):
114
M=networkx.to_numpy_matrix(G,nodelist=nodelist)
115
(n,m)=M.shape # should be square
116
# add constant to dangling nodes' row
117
dangling=numpy.where(M.sum(axis=1)==0)
118
for d in dangling[0]:
122
# add "teleportation"
123
P=alpha*M+(1-alpha)*numpy.ones((n,n))/n
127
def pagerank_numpy(G,alpha=0.85,max_iter=100,tol=1.0e-6,nodelist=None):
128
"""Return a NumPy array of the PageRank of G.
132
M=networkx.google_matrix(G,alpha,nodelist)
133
(n,m)=M.shape # should be square
135
for i in range(max_iter):
138
# check convergence, l1 norm
139
err=numpy.abs(x-xlast).sum()
141
return numpy.asarray(x).flatten()
143
raise NetworkXError("pagerank: power iteration failed to converge in %d iterations."%(i+1))
147
def pagerank_scipy(G,alpha=0.85,max_iter=100,tol=1.0e-6,nodelist=None):
148
"""Return a SciPy sparse array of the PageRank of G.
153
M=networkx.to_scipy_sparse_matrix(G,nodelist=nodelist)
154
(n,m)=M.shape # should be square
155
S=scipy.array(M.sum(axis=1)).flatten()
156
index=scipy.where(S<>0)[0]
159
x=scipy.ones((n))/n # initial guess
160
dangle=scipy.array(scipy.where(M.sum(axis=1)==0,1.0/n,0)).flatten()
161
for i in range(max_iter):
163
x=alpha*(x*M+scipy.dot(dangle,xlast))+(1-alpha)*xlast.sum()/n
164
# check convergence, l1 norm
165
err=scipy.absolute(x-xlast).sum()
168
raise NetworkXError("pagerank_scipy: power iteration failed to converge in %d iterations."%(i+1))
added
removed
networkx/algorithms/pagerank.py
