Article

TotalRank: ranking without damping

Author:

Paolo BoldiAuthors Info & Claims

WWW '05: Special interest tracks and posters of the 14th international conference on World Wide Web

Pages 898 - 899

https://doi.org/10.1145/1062745.1062787

Published: 10 May 2005 Publication History

Get Access

Abstract

PageRank is defined as the stationary state of a Markov chain obtained by perturbing the transition matrix of a web graph with a damping factor α that spreads part of the rank. The choice of α is eminently empirical, but most applications use α = 0.85; nonetheless, the selection of α is critical, and some believe that link farms may use this choice adversarially. Recent results [1] prove that the PageRank of a page is a rational function of α, and that this function can be approximated quite efficiently: this fact can be used to define a new form of ranking, TotalRank, that averages PageRanks over all possible α's. We show how this rank can be computed efficiently, and provide some preliminary experimental results on its quality and comparisons with PageRank.

References

[1]

Paolo Boldi, Massimo Santini, and Sebastiano Vigna.PageRank as a function of the damping factor. In Proceedings of the Fourteenth International World--Wide Web Conference, 2005. To appear.

Digital Library

Google Scholar

[2]

Paolo Boldi and Sebastiano Vigna. The WebGraph framework I: Compression techniques. In Proc. of the Thirteenth International World Wide Web Conference, pages 595--601, Manhattan, USA, 2004. ACM Press.

Digital Library

Google Scholar

[3]

Ronald Fagin, Ravi Kumar, and D. Sivakumar. Comparing top k lists. In Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, pages 28--36. Society for Industrial and Applied Mathematics, 2003.

Digital Library

Google Scholar

[4]

Maurice G. Kendall. Rank Correlation Methods. Hafner Publishing Co., New York, 1955.

Google Scholar

[5]

Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. The PageRank citation ranking: Bringing order to the web. Technical report, Stanford Digital Library Technologies Project, Stanford University, Stanford, CA, USA, 1998.

Google Scholar

[6]

Hui Zhang, Ashish Goel, Ramesh Govindan, Kahn Mason, and Benjamin Van Roy. Making eigenvector-based reputation systems robust to collision. In Stefano Leonardi, editor, Proceedings WAW 2004, number 3243 in LNCS, pages 92--104. Springer-Verlag, 2004.

Google Scholar

Cited By

View all

Henni KMezghani NMitiche A(2020)Cluster Density Properties Define a Graph for Effective Pattern Feature SelectionIEEE Access10.1109/ACCESS.2020.29812658(62841-62854)Online publication date: 2020
https://doi.org/10.1109/ACCESS.2020.2981265
Peel LDelvenne JLambiotte R(2018)Multiscale mixing patterns in networksProceedings of the National Academy of Sciences10.1073/pnas.1713019115115:16(4057-4062)Online publication date: 2-Apr-2018
https://doi.org/10.1073/pnas.1713019115
Liao CXiong YKong XZhu YZhao SLi S(2018)Functional-Oriented Relationship Strength Estimation: From Online Events to Offline InteractionsDatabase Systems for Advanced Applications10.1007/978-3-319-91452-7_29(442-459)Online publication date: 13-May-2018
https://doi.org/10.1007/978-3-319-91452-7_29
Show More Cited By

Index Terms

TotalRank: ranking without damping
1. Mathematics of computing
  1. Discrete mathematics
  2. Probability and statistics

Recommendations

Content and link-structure perspective of ranking webpages: A review
Abstract
The delivery of ranked relevant results is probably the most important factor in making a web search engine acceptable to its users. This inspiration has led the search engine engineers and researchers to conceive ranking algorithms ...
Hits on the web: how does it compare?
SIGIR '07: Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval

This paper describes a large-scale evaluation of the effectiveness of HITS in comparison with other link-based ranking algorithms, when used in combination with a state-of-the-art text retrieval algorithm exploiting anchor text. We quantified their ...
A Googol of Information about Google

Timothy P. Chartier reviews Google's PageRank and Beyond: The Science of Search Engine Rankings by Amy Langville and Carl Meyer.

Comments

Information & Contributors

Information

Published In

WWW '05: Special interest tracks and posters of the 14th international conference on World Wide Web

May 2005

454 pages

ISBN:1595930515

DOI:10.1145/1062745

Conference Chairs:
Allan Ellis
Southern Cross University, Australia
,
Tatsuya Hagino
Keio University, Japan
,
Program Chairs:
Fred Douglis
IBM Research
,
Prabhakar Raghavan
Verity, Inc.

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 10 May 2005

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 1,899 of 8,196 submissions, 23%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

15
Total Citations
View Citations
367
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)0

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Henni KMezghani NMitiche A(2020)Cluster Density Properties Define a Graph for Effective Pattern Feature SelectionIEEE Access10.1109/ACCESS.2020.29812658(62841-62854)Online publication date: 2020
https://doi.org/10.1109/ACCESS.2020.2981265
Peel LDelvenne JLambiotte R(2018)Multiscale mixing patterns in networksProceedings of the National Academy of Sciences10.1073/pnas.1713019115115:16(4057-4062)Online publication date: 2-Apr-2018
https://doi.org/10.1073/pnas.1713019115
Liao CXiong YKong XZhu YZhao SLi S(2018)Functional-Oriented Relationship Strength Estimation: From Online Events to Offline InteractionsDatabase Systems for Advanced Applications10.1007/978-3-319-91452-7_29(442-459)Online publication date: 13-May-2018
https://doi.org/10.1007/978-3-319-91452-7_29
Ferdman SMinkov EBekkerman RGefen D(2017)Quantifying the web browser ecosystemPLOS ONE10.1371/journal.pone.017928112:6(e0179281)Online publication date: 23-Jun-2017
https://doi.org/10.1371/journal.pone.0179281
Hsu CLai YChen WFeng MLin Sde Rijke MShokouhi MTomkins AZhang M(2017)Unsupervised Ranking using Graph Structures and Node AttributesProceedings of the Tenth ACM International Conference on Web Search and Data Mining10.1145/3018661.3018668(771-779)Online publication date: 2-Feb-2017
https://dl.acm.org/doi/10.1145/3018661.3018668
Nikolakopoulos AGarofalakis J(2015)Random Surfing Without TeleportationAlgorithms, Probability, Networks, and Games10.1007/978-3-319-24024-4_19(344-357)Online publication date: 22-Nov-2015
https://doi.org/10.1007/978-3-319-24024-4_19
Zhang XWang YMou NLiang W(2014)Propagating Both Trust and Distrust with Target Differentiation for Combating Link-Based Web SpamACM Transactions on the Web10.1145/26284408:3(1-33)Online publication date: 8-Jul-2014
https://dl.acm.org/doi/10.1145/2628440
Kang CPugliese AGrant JSubrahmanian V(2014)STUN: querying spatio-temporal uncertain (social) networksSocial Network Analysis and Mining10.1007/s13278-014-0156-x4:1Online publication date: 5-Feb-2014
https://doi.org/10.1007/s13278-014-0156-x
Avrachenkov Kvan der Hofstad RSokol M(2014)Personalized PageRank with Node-Dependent RestartAlgorithms and Models for the Web Graph10.1007/978-3-319-13123-8_3(23-33)Online publication date: 13-Nov-2014
https://doi.org/10.1007/978-3-319-13123-8_3
Nikolakopoulos AGarofalakis JLeonardi SPanconesi AFerragina PGionis A(2013)NCDawareRankProceedings of the sixth ACM international conference on Web search and data mining10.1145/2433396.2433415(143-152)Online publication date: 4-Feb-2013
https://dl.acm.org/doi/10.1145/2433396.2433415
Show More Cited By

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.

PDF

eReader

View online with eReader.

eReader

Abstract

References

Cited By

Index Terms

Recommendations

Content and link-structure perspective of ranking webpages: A review

Hits on the web: how does it compare?

A Googol of Information about Google

Comments

Information

Published In

Sponsors

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Acceptance Rates

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

Login options

Full Access

View options

PDF

eReader

Share

Share this Publication link

Share on social media

Affiliations