Sun, TL; Deng, KY; Deng, JW Novel numerical methods for rapid computation of PageRank 2008 PROCEEDINGS OF INFORMATION TECHNOLOGY AND ENVIRONMENTAL SYSTEM SCIENCES: ITESS 2008, VOL 2 532-537, 2008

[Eugene Garfield]

Author(s): Sun, TL (Sun, T. L.); Deng, KY (Deng, K. Y.); Deng, JW (Deng, 
J. W.) 

Title: Novel numerical methods for rapid computation of PageRank 

Editor(s): Li, G; Jia, Z; Fu, Z 

Source: 2008 PROCEEDINGS OF INFORMATION TECHNOLOGY AND ENVIRONMENTAL 
SYSTEM SCIENCES: ITESS 2008, VOL 2 532-537, 2008 

Language: English 

Document Type: Article 

Conference Title: International Conference on Informational Technology and 
Environmental System Science 

Conference Date: MAY 15-17, 2008 

Conference Location: Jiaozuo, PEOPLES R CHINA 

Conference Host: Henan Polytechn Univ 

Author Keywords: PageRank; power method; dominant eigenvector; Google 
matrix 

KeyWords Plus: WORLD-WIDE-WEB 

Abstract: PageRank, a part of the search engine Google, is one of the most 
important ranking algorithms used by search engines. Google is one of the 
most successful search engines in the world. Although many factors 
determine Google's overall ranking of search engine results, Google 
maintains that the heart of its search engine software is PageRank. 
PageRank computation is a key component of modem Web search ranking 
systems. The computation of the PageRank vector consists in computing the 
dominant eigenvector of a stochastic matrix whose size is now of some 
billions. Brin and Page originally suggested computing this pair by using 
the well-known power method and they also gave a nice interpretation of 
PageRank in term of Markov Chains. The power iteration method used to 
compute the PageRank by Google can take much computing time and many 
resources. For these reasons, it seems urgent to make much more efforts 
for reducing the computation cost spent in Web ranking algorithms. This 
paper works on accelerating the PageRank computation. At first, the model 
of PageRank and the power method are briefly introduced. Based on the 
existing research on the computation of PageRank, we further derive the 
general formula for acceleration of PageRank computations and at the same 
time present two novel algorithms for accelerating the PageRank 
convergence: General Extrapolation and Acceleration Method. Then we give 
the results of numerical experiments performed on four datasets. The 
numerical results confirm the effectiveness of our theoretical analysis 
and numerical algorithms. 

Addresses: NE Normal Univ, Sch Comp Sci, Changchun, 130117 Peoples R 
China. 

Reprint Address: Deng, KY, NE Normal Univ, Sch Comp Sci, Changchun, 130117 
Peoples R China. 

Cited Reference Count: 28 

Publisher Name: PUBLISHING HOUSE ELECTRONICS INDUSTRY 

Publisher Address: PO BOX 173 WANSHOU ROAD, BEIJING 100036, PEOPLES R 
CHINA 

ISBN: 978-7-121-06303-9 

Source Item Page Count: 6 

ISI Document Delivery No.: BHW36 

ARASU A
P 11 INT WORLD WID W : 2001 

AVRACHENKOV K
Title Not Available
STOCH MODELS 22 : 319 2006 

AVRAECHENKOV KE
P 5 WORKSH ALG MOD W : 2007 

BARABASI AL
Scale-free characteristics of random networks: the topology of the World-
Wide Web 
PHYSICA A 281 : 69 2000 

BHARAT K
Title Not Available
ACM T INFORM SYST 20 : 47 2002

BIANCHINI M
INSIDE PAGERANK : 2003 

BRIN S
The anatomy of a large-scale hypertextual Web search engine 
COMPUTER NETWORKS AND ISDN SYSTEMS 30 : 107 1998 

DING CHQ
Title Not Available
SIAM REV 46 : 256 2004 

GARFIELD E
CITATION INDEXES SCI : 108 1955 

GOLUB GH
MATRIX COMPUTATIONS : 1996 

HAVELIWALA TH
2 WIGENVALUE GOOGLE 2003 

HAVELIWALA TH
EFFICIENT COMPUTATIO : 1999 

JEH G
P 12 INT WORLD WID W : 2003 

KAMVAR S
Adaptive methods for the computation of PageRank 
LINEAR ALGEBRA AND ITS APPLICATIONS 386 : 51 2004 

KAMVAR SD
P 12 INT WORLD WID W : 2003 

KIM SJ
P 24 BCS IRSG EUR C : 73 2002 

KOHLSCHUTTER C
P 28 EUR C INF RETR : 2006 

LANGVILLE AN
Title Not Available
SIAM J MATRIX ANAL A 27 : 968 2006 

LANGVILLE AN
Title Not Available
SIAM J SCI COMPUT 27 : 2112 2006 

LANGVILLE AN
Title Not Available
SIAM REV 47 : 135 2005 

LEE CP
FAST 2 STAGE ALGORIT : 2003 

MCSHERRY F
P 14 INT C WORLD WID : 575 2005 

MOLER C
WORLDS LARGEST MATRI : 12 2002 

PAGE L
PAGERANK CITATION RA : 1998 

RICHARDSON M
INTELLIGENT SURFER P 14 : 2002 

SERRACAPIZZANO S
Title Not Available
SIAM J MATRIX ANAL A 27 : 305 2005 

SUN H
Title Not Available
APPL MATH COMPUT 179 : 799 2006 

ZHANG JP
THESIS E CHINA U SCI : 24 2007