skip to main content
10.1145/1645953.1646056acmconferencesArticle/Chapter ViewAbstractPublication PagescikmConference Proceedingsconference-collections
research-article

Nonlinear static-rank computation

Published: 02 November 2009 Publication History

Abstract

Mainstream link-based static-rank algorithms (e.g. PageRank and its variants) express the importance of a page as the linear combination of its in-links and compute page importance scores by solving a linear system in an iterative way. Such linear algorithms, however, may give apparently unreasonable static-rank results for some link structures. In this paper, we examine the static-rank computation problem from the viewpoint of evidence combination and build a probabilistic model for it. Based on the model, we argue that a nonlinear formula should be adopted, due to the correlation or dependence between links. We focus on examining some simple formulas which only consider the correlation between links in the same domain. Experiments conducted on 100 million web pages (with multiple static-rank quality evaluation metrics) show that higher quality static-rank could be yielded by the new nonlinear algorithms. The convergence of the new algorithms is also proved in this paper by nonlinear functional analysis.

References

[1]
R. Baeza-Yates, E. Davis. Web Page Ranking using Link Attributes. In WWW 2004.
[2]
P. Berkhin. A Survey on PageRank Computing. Internet Mathematics, 2(1):73--120, 2005.
[3]
K. Bharat, B.-W. Chang, M. Henzinger and M. Ruhl. Who Links to Whom: Mining Linkage between Web Site. In ICDM 2001.
[4]
M. Bianchini, M. Gori and F. Scarselli. Inside PageRank. ACM Transactions on Internet Technology, 5(1):92--128, 2005.
[5]
P. Boldi, M. Santini and S. Vigna. PageRank as a Function of the Damping Factor. In WWW 2005.
[6]
Z. Gyongyi, H. Garcie-Molina and J. Pedersen. Combating Web Spam with TrustRank. In VLDB 2004.
[7]
T. H. Haveliwala. Topic-Sensitive PageRank. In WWW 2002.
[8]
K. Jarvelin and J. Kekalainen. IR evaluation Methods for Retrieving Highly Relevant Documents. In SIGIR 2000.
[9]
S. Kamvar, T. Haveliwala, C. Manning and G. Golub. Extrapolation Methods for Accelerating the Computation of PageRank. In WWW 2003.
[10]
S. Kamvar, T. Haveliwala, C. Manning and G. Golub. Exploiting the Block Structure of the Web for Computing PageRank. Technical Report, Stanford University, 2003.
[11]
M. G. Kendall. Rank Correlation Methods, 4th edition. Griffin, London, 1970.
[12]
J. M. Kleinberg. Authoritative Sources in a Hyperlinked Environment. In Proceedings of ACM-SLAM Symposium on Discrete Algorithms, 1998.
[13]
M.A. Krasnoselskii and P.P. Zabreiko. Geometric Methods in Nonlinear Analysis, Springer-Verlag, Berlin, 1984.
[14]
A. Y. Ng, A. X. Zheng and M. I. Jordan. Stable Algorithms for Link Analysis. In SIGIR 2001.
[15]
L. Page, S. Brin, R. Motwani and T. Winograd. The PageRank Citation Ranking: Bring Order to the Web. Technical report, Stanford University Database Group, 1998.
[16]
M. Richardson and P. Domingos. The Intelligent Surfer: Probabilistic Combination of Link and Content Information in PageRank. In NIPS 2002.
[17]
S. E. Robertson. Overview of Okapi Projects. Journal of Documentation, 53(1):3--7, 1997.
[18]
S. Shi, R. Song, and J.-R. Wen. Latent Additivity: Combining Homogeneous Evidence. Technical report, MSR-TR-2006-110, Microsoft Research, August 2006.
[19]
P. Tsaparas. Using Non-Linear Dynamical Systems for Web Searching and Ranking. PODS, 2004.
[20]
B. Wu and B. D. Davison. Identifying Link Farm Spam Pages. In WWW 2005.
[21]
G.-R. Xue, Q. Yang, H.-J. Zeng, Y. Yu and Z. Chen. Exploiting the Hierarchical Structure for Link Analysis. In SIGIR, 2005.
[22]
E. Yilmaz, J. Aslam and S. Robertson. A New Rank Correlation Coefficient for Information Retrieval. In Proc. of the 31st Annual International ACM SIGIR Conference. July 20--24, 2008, Singapore.
[23]
H. Zhang, M. Zhu, S. Shi, and J.-R. Wen. Employing Topic Models for Pattern-based Semantic Class Discovery. In Proc. of the Annual Meeting of the Association for Computational Linguistics (ACL'09), Singapore, August 2009.

Cited By

View all
  • (2017)An evolutionary non-linear ranking algorithm for ranking scientific collaborationsApplied Intelligence10.1007/s10489-017-0990-448:2(465-481)Online publication date: 17-Jul-2017
  • (2011)Nonlinear evidence fusion and propagation for hyponymy relation miningProceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies - Volume 110.5555/2002472.2002619(1159-1168)Online publication date: 19-Jun-2011

Index Terms

  1. Nonlinear static-rank computation

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    CIKM '09: Proceedings of the 18th ACM conference on Information and knowledge management
    November 2009
    2162 pages
    ISBN:9781605585123
    DOI:10.1145/1645953
    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: 02 November 2009

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. link aggregation
    2. nonlinear static rank
    3. probabilistic model

    Qualifiers

    • Research-article

    Conference

    CIKM '09
    Sponsor:

    Acceptance Rates

    Overall Acceptance Rate 1,861 of 8,427 submissions, 22%

    Upcoming Conference

    CIKM '25

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

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

    Other Metrics

    Citations

    Cited By

    View all
    • (2017)An evolutionary non-linear ranking algorithm for ranking scientific collaborationsApplied Intelligence10.1007/s10489-017-0990-448:2(465-481)Online publication date: 17-Jul-2017
    • (2011)Nonlinear evidence fusion and propagation for hyponymy relation miningProceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies - Volume 110.5555/2002472.2002619(1159-1168)Online publication date: 19-Jun-2011

    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