skip to main content
10.1145/1390334.1390545acmconferencesArticle/Chapter ViewAbstractPublication PagesirConference Proceedingsconference-collections
poster

Local approximation of PageRank and reverse PageRank

Published: 20 July 2008 Publication History

Abstract

We consider the problem of approximating the PageRank of a target node using only local information provided by a link server. We prove that local approximation of PageRank is feasible if and only if the graph has low in-degree and admits fast PageRank convergence. While natural graphs, such as the web graph, are abundant with high in-degree nodes, making local PageRank approximation too costly, we show that reverse natural graphs tend to have low indegree while maintaining fast PageRank convergence. It follows that calculating Reverse PageRank locally is frequently more feasible than computing PageRank locally. Finally, we demonstrate the usefulness of Reverse PageRank in five different applications.

References

[1]
Y. Chen, Q. Gan, and T. Suel. Local methods for estimating PageRank values. In CIKM, pages 381--389, 2004.
[2]
D. Fogaras. Where to start browsing the Web? In IICS, pages 65--79, 2003.
[3]
Z. Gyöngyi, H. Garcia-Molina, and J. Pedersen. Combating Web Spam with TrustRank. In VLDB, pages 576--587, 2004.
[4]
T. H. Haveliwala and S. D. Kamvar. The second eigenvalue of the Google matrix. Technical report, Stanford University, 2003.
[5]
A. Java, P. Kolari, T. Finin, and T. Oates. Modeling the spread of influence on the Blogosphere. Technical report, University of Maryland, Baltimore County, 2006.
[6]
L. Page, S. Brin, R. Motwani, and T. Winograd. The PageRank citation ranking: Bringing order to the Web. Technical report, Stanford Digital Library Technologies Project, 1998.

Cited By

View all
  • (2021)A Review of Graph-Based Models for Entity-Oriented SearchSN Computer Science10.1007/s42979-021-00828-w2:6Online publication date: 30-Aug-2021
  • (2018)A survey of state management in big data processing systemsThe VLDB Journal — The International Journal on Very Large Data Bases10.1007/s00778-018-0514-927:6(847-872)Online publication date: 1-Dec-2018
  • (2017)Parallel computations of local PageRank problem based on Graphics Processing UnitConcurrency and Computation: Practice and Experience10.1002/cpe.424529:24Online publication date: 24-Aug-2017
  • Show More Cited By

Index Terms

  1. Local approximation of PageRank and reverse PageRank

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    SIGIR '08: Proceedings of the 31st annual international ACM SIGIR conference on Research and development in information retrieval
    July 2008
    934 pages
    ISBN:9781605581644
    DOI:10.1145/1390334
    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

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 20 July 2008

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. PageRank
    2. local approximation
    3. lower bounds
    4. reverse PageRank

    Qualifiers

    • Poster

    Conference

    SIGIR '08
    Sponsor:

    Acceptance Rates

    Overall Acceptance Rate 792 of 3,983 submissions, 20%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)2
    • Downloads (Last 6 weeks)0
    Reflects downloads up to 14 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2021)A Review of Graph-Based Models for Entity-Oriented SearchSN Computer Science10.1007/s42979-021-00828-w2:6Online publication date: 30-Aug-2021
    • (2018)A survey of state management in big data processing systemsThe VLDB Journal — The International Journal on Very Large Data Bases10.1007/s00778-018-0514-927:6(847-872)Online publication date: 1-Dec-2018
    • (2017)Parallel computations of local PageRank problem based on Graphics Processing UnitConcurrency and Computation: Practice and Experience10.1002/cpe.424529:24Online publication date: 24-Aug-2017
    • (2013)The power of local information in PageRankProceedings of the 22nd International Conference on World Wide Web10.1145/2487788.2487878(179-180)Online publication date: 13-May-2013
    • (2012)Reducing the history in decentralized interaction-based reputation systemsProceedings of the 11th international IFIP TC 6 conference on Networking - Volume Part II10.1007/978-3-642-30054-7_19(238-251)Online publication date: 21-May-2012

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media