Distribution of pagerank mass among principle components of the web

Konstantin Avrachenkov, Nelly Litvak, Kim Son Pham

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

19 Citations (Scopus)

Abstract

We study the PageRank mass of principal components in a bow-tie Web Graph, as a function of the damping factor c. Using a singular perturbation approach, we show that the PageRank share of IN and SCC components remains high even for very large values of the damping factor, in spite of the fact that it drops to zero when c→1. However, a detailed study of the OUT component reveals the presence of "dead-ends" (small groups of pages linking only to each other) that receive an unfairly high ranking when c is close to one. We argue that this problem can be mitigated by choosing c as small as 1/2.
Original languageEnglish
Title of host publicationAlgorithms and Models for the Web-Graph
Subtitle of host publication5th International Workshop, WAW 2007, San Diego, CA, USA, December 11-12, 2007. Proceedings
EditorsAnthony Bonato, Fan R.K. Chung
Place of PublicationLondon
PublisherSpringer
Pages16-28
Number of pages13
ISBN (Electronic)978-3-540-77004-6
ISBN (Print)978-3-540-77003-9
DOIs
Publication statusPublished - 2007
Event5th International Workshop on Algorithms and Models for the Web-Graph, WAW 2007 - San Diego, United States
Duration: 11 Dec 200712 Dec 2007
Conference number: 5

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume4863
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Workshop

Workshop5th International Workshop on Algorithms and Models for the Web-Graph, WAW 2007
Abbreviated titleWAW
CountryUnited States
CitySan Diego
Period11/12/0712/12/07

Keywords

  • MSC-61J10
  • MSC-68P10

Fingerprint Dive into the research topics of 'Distribution of pagerank mass among principle components of the web'. Together they form a unique fingerprint.

  • Cite this

    Avrachenkov, K., Litvak, N., & Pham, K. S. (2007). Distribution of pagerank mass among principle components of the web. In A. Bonato, & F. R. K. Chung (Eds.), Algorithms and Models for the Web-Graph: 5th International Workshop, WAW 2007, San Diego, CA, USA, December 11-12, 2007. Proceedings (pp. 16-28). (Lecture Notes in Computer Science; Vol. 4863). London: Springer. https://doi.org/10.1007/978-3-540-77004-6_2