More Web Proxy on the site http://driver.im/

research-article

Incremental iteration method for fast PageRank computation

Authors:

Yong Suk ChoiAuthors Info & Claims

IMCOM '15: Proceedings of the 9th International Conference on Ubiquitous Information Management and Communication

Article No.: 80, Pages 1 - 5

https://doi.org/10.1145/2701126.2701165

Published: 08 January 2015 Publication History

Abstract

As the search services have been widely available on the web, page-ranking algorithm gained great attention in the recent decade. PageRank is the most popular ranking scheme that is currently well-known even to the public. PageRank uses a hyperlink matrix which represents the whole web structure and the size of the web is incredibly large in general so that a fast calculation method is needed to efficiently compute an enormous number of page ranks on the web. In this paper, we propose a new PageRank computation method, incremental iteration method in order to considerably reduce total computational cost. Our method makes good use of faster convergence procedure of power iteration than conventional one. Additionally, our method can be effectively combined with other conventional methods for more reduction of computational cost. In experiment, we demonstrate efficiency and effectiveness of our proposed method.

References

[1]

Basharin, Gely P., Langville, Amy N., and Vaumov, Valeriy A. 2004. The life and work of A. A. Markov. Linear Algebra and Its Applications, 386, 3--26.

[2]

Page, L., Brin, S., Motwani, R., and Winograd, T. 1998. The PageRank Citation Ranking: Bringing Order to the web. Stanford Digital Library Technologies.

[3]

Desikan, P. and Srivastava, J. 2004, Mining Temporally Evolving Graphs. webKDD Workshop, Seattle.

[4]

Haveliwala, T. 1999. Efficient Computation of PageRank, Stanford University Technical Report (September 1999).

[5]

Desikan, P., Srivastava, J., Kumar, V., and Tan, P. N. 2002. Hyperlink Analysis - Techniques & Applications. Army High Performance Computing Center Technical Report (2002).

[6]

Kleinberg, Jon. 1999. Authoritative sources in a hyperlinked environment. Journal of the ACM, 46.

Digital Library

[7]

Bicardo, B. Y. and Berthier, R. N. 1999. Modern Information Retrieval. ACM Press, New York.

Digital Library

[8]

Lempel, R. and Moran, S. 2000. The stochastic approach for link-structure analysis (SALSA) and the TKC effect. In The Ninth International World Wide web Conference, New York, ACM Press.

Digital Library

[9]

Hunter, Jeffrey J. 1986. Stationary distributions of perturbed Markov chains. Linear Algebra and Its Application, 82, 201--214.

[10]

Parlett, Beresford N. 1998. The Symmetric Eigenvalue Problem. SIAM.

Digital Library

[11]

Thorson, K. 2004. Modeling the web and the computation of PageRank. Undergraduate thesis, Hollins University.

[12]

Desikab, P., Pathak, N., Srivastava, J., and Kumar, V. 2005. Incremental Page Rank Computation on evolving graphs. In International World Wide web Conference (2005).

Digital Library

[13]

Langville, Amy N. and Meyer, Carl D. 2006. Google's PageRank and Beyond: The Science of Search Engine Rankings. Princeton University Press, New Jersey.

Digital Library

[14]

Pierre, B., Paolo, F., and Padhraic, S. 2003. Modeling the Internet and the web: Probabilistic methods and algorithms (2003), Wiley.

[15]

Arasu, A., Novak, J., Tomkins, A., and Tomlin, J. 2002. Pagerank computation and the structure of the web: Experiments and algorithms. International World Wide web Conference (2002), poster.

[16]

Kamvar, S. D., Haveliwala, T. H., Manning, C. D., and Golub, G. H. 2003. Extrapolation methods for accelerating PageRank computations. International World Wide Web Conference (2003).

Digital Library

Cited By

Sahu SKothapalli KEedi HPeri S(2024)Lock-free Computation of PageRank in Dynamic Graphs2024 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW)10.1109/IPDPSW63119.2024.00148(825-834)Online publication date: 27-May-2024
https://doi.org/10.1109/IPDPSW63119.2024.00148
Sahu SKothapalli KEedi HPeri S(2024)DF* PageRank: Incrementally Expanding Approaches for Updating PageRank on Dynamic GraphsEuro-Par 2024: Parallel Processing10.1007/978-3-031-69583-4_22(312-326)Online publication date: 26-Aug-2024
https://doi.org/10.1007/978-3-031-69583-4_22
Sun ZZeng GDing C(2022)Towards PageRank Update in a Streaming Graph by Incremental Random WalkIEEE Access10.1109/ACCESS.2022.314929610(15805-15817)Online publication date: 2022
https://doi.org/10.1109/ACCESS.2022.3149296
Show More Cited By

Index Terms

Incremental iteration method for fast PageRank computation
1. Information systems
  1. Information retrieval
    1. Retrieval models and ranking
    2. Retrieval tasks and goals

Recommendations

Monte Carlo Methods in PageRank Computation: When One Iteration is Sufficient

PageRank is one of the principle criteria according to which Google ranks Web pages. PageRank can be interpreted as a frequency of visiting a Web page by a random surfer, and thus it reflects the popularity of a Web page. Google computes the PageRank ...
Lumping Method with Acceleration for the PageRank Computation
ICCSA '14: Proceedings of the 2014 14th International Conference on Computational Science and Its Applications

Web information retrieval is extremely challenging due to the huge number of web pages. The success of a search engine relies on its capacity to deploy fast, accurately and in order, a set of results satisfying a particular query. To determine the order ...
Associated pagerank: improved pagerank measured by frequent term sets
VECIMS'09: Proceedings of the 2009 IEEE international conference on Virtual Environments, Human-Computer Interfaces and Measurement Systems

Web search engines encounter many new challenges while the amount of information on the web increases rapidly. Web documents have been a main resource for various purposes, and people rely on search engines to retrieve the desired documents. This paper ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

IMCOM '15: Proceedings of the 9th International Conference on Ubiquitous Information Management and Communication

January 2015

674 pages

ISBN:9781450333771

DOI:10.1145/2701126

Conference Chairs:
Dongsoo S. Kim
Indiana University
,
Sang-wook Kim
Hanyang University, Korea
,
General Chairs:
Suk-Han Lee
Sungkyunkwan Univerisity, Korea
,
Lajos Hanzo
University of Southampton, UK
,
Roslan Ismail
Universiti Kuala Lumpur, Malaysia

Copyright © 2015 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGAPP: ACM Special Interest Group on Applied Computing

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 January 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Korea government (MSIP)

Conference

IMCOM '15

Sponsor:

SIGAPP

IMCOM '15: The 9th International Conference on Ubiquitous Information Management and Communication

January 8 - 10, 2015

Bali, Indonesia

Acceptance Rates

Overall Acceptance Rate 213 of 621 submissions, 34%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
231
Total Downloads

Downloads (Last 12 months)7
Downloads (Last 6 weeks)2

Reflects downloads up to 03 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Sahu SKothapalli KEedi HPeri S(2024)Lock-free Computation of PageRank in Dynamic Graphs2024 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW)10.1109/IPDPSW63119.2024.00148(825-834)Online publication date: 27-May-2024
https://doi.org/10.1109/IPDPSW63119.2024.00148
Sahu SKothapalli KEedi HPeri S(2024)DF* PageRank: Incrementally Expanding Approaches for Updating PageRank on Dynamic GraphsEuro-Par 2024: Parallel Processing10.1007/978-3-031-69583-4_22(312-326)Online publication date: 26-Aug-2024
https://doi.org/10.1007/978-3-031-69583-4_22
Sun ZZeng GDing C(2022)Towards PageRank Update in a Streaming Graph by Incremental Random WalkIEEE Access10.1109/ACCESS.2022.314929610(15805-15817)Online publication date: 2022
https://doi.org/10.1109/ACCESS.2022.3149296
Cordeiro MSarmento RBrazdil PKimura MGama J(2019)Identifying, Ranking and Tracking Community Leaders in Evolving Social NetworksComplex Networks and Their Applications VIII10.1007/978-3-030-36687-2_17(198-210)Online publication date: 26-Nov-2019
https://doi.org/10.1007/978-3-030-36687-2_17
Cordeiro MSarmento RBrazdil PGama J(2018)Evolving Networks and Social Network Analysis Methods and TechniquesSocial Media and Journalism - Trends, Connections, Implications10.5772/intechopen.79041Online publication date: 31-Oct-2018
https://doi.org/10.5772/intechopen.79041
Ghasemian FZamanifar KGhasem-Aghaee N(2018)An evolutionary non-linear ranking algorithm for ranking scientific collaborationsApplied Intelligence10.1007/s10489-017-0990-448:2(465-481)Online publication date: 1-Feb-2018
https://dl.acm.org/doi/10.1007/s10489-017-0990-4
Liu MRicha A(2017)Interest- and Content-Based Data Dissemination in Mobile Social NetworksGLOBECOM 2017 - 2017 IEEE Global Communications Conference10.1109/GLOCOM.2017.8255085(1-6)Online publication date: Dec-2017
https://doi.org/10.1109/GLOCOM.2017.8255085
Liu CZheng J(2017)A QoE-Aware Resource Allocation Algorithm for D2D Communication Underlaying Cellular NetworksGLOBECOM 2017 - 2017 IEEE Global Communications Conference10.1109/GLOCOM.2017.8254743(1-6)Online publication date: Dec-2017
https://doi.org/10.1109/GLOCOM.2017.8254743
Gupta UFegaras L(2016)Distributed Incremental Graph Analysis2016 IEEE International Congress on Big Data (BigData Congress)10.1109/BigDataCongress.2016.18(75-82)Online publication date: Jun-2016
https://doi.org/10.1109/BigDataCongress.2016.18
Rozenshtein PGionis A(2016)Temporal PageRankMachine Learning and Knowledge Discovery in Databases10.1007/978-3-319-46227-1_42(674-689)Online publication date: 4-Sep-2016
https://doi.org/10.1007/978-3-319-46227-1_42

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents