Distribution of pagerank mass among principle components of the web

Konstantin Avrachenkov; Nelly Litvak; Kim Son Pham

doi:10.1007/978-3-540-77004-6_2

Distribution of pagerank mass among principle components of the web

Konstantin Avrachenkov
, Nelly Litvak
, Kim Son Pham

Stochastic Operations Research

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

21 Citations (Scopus)

1 Downloads (Pure)

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 language	English
Title of host publication	Algorithms and Models for the Web-Graph
Subtitle of host publication	5th International Workshop, WAW 2007, San Diego, CA, USA, December 11-12, 2007. Proceedings
Editors	Anthony Bonato, Fan R.K. Chung
Place of Publication	London
Publisher	Springer
Pages	16-28
Number of pages	13
ISBN (Electronic)	978-3-540-77004-6
ISBN (Print)	978-3-540-77003-9
DOIs	https://doi.org/10.1007/978-3-540-77004-6_2
Publication status	Published - 2007
Event	5th International Workshop on Algorithms and Models for the Web-Graph, WAW 2007 - San Diego, United States Duration: 11 Dec 2007 → 12 Dec 2007 Conference number: 5

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	4863
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Workshop

Workshop	5th International Workshop on Algorithms and Models for the Web-Graph, WAW 2007
Abbreviated title	WAW
Country/Territory	United States
City	San Diego
Period	11/12/07 → 12/12/07

Keywords

MSC-61J10
MSC-68P10

Access to Document

10.1007/978-3-540-77004-6_2

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). Springer. https://doi.org/10.1007/978-3-540-77004-6_2

Avrachenkov, Konstantin ; Litvak, Nelly ; Pham, Kim Son. / Distribution of pagerank mass among principle components of the web. Algorithms and Models for the Web-Graph: 5th International Workshop, WAW 2007, San Diego, CA, USA, December 11-12, 2007. Proceedings. editor / Anthony Bonato ; Fan R.K. Chung. London : Springer, 2007. pp. 16-28 (Lecture Notes in Computer Science).

@inproceedings{fa0bc921fe2143cf870607b5b2294d60,

title = "Distribution of pagerank mass among principle components of the web",

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.",

keywords = "MSC-61J10, MSC-68P10",

author = "Konstantin Avrachenkov and Nelly Litvak and Pham, \{Kim Son\}",

year = "2007",

doi = "10.1007/978-3-540-77004-6\_2",

language = "English",

isbn = "978-3-540-77003-9",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "16--28",

editor = "Anthony Bonato and Chung, \{Fan R.K.\}",

booktitle = "Algorithms and Models for the Web-Graph",

address = "Germany",

note = "5th International Workshop on Algorithms and Models for the Web-Graph, WAW 2007, WAW ; Conference date: 11-12-2007 Through 12-12-2007",

}

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

Distribution of pagerank mass among principle components of the web. / Avrachenkov, Konstantin; Litvak, Nelly; Pham, Kim Son.
Algorithms and Models for the Web-Graph: 5th International Workshop, WAW 2007, San Diego, CA, USA, December 11-12, 2007. Proceedings. ed. / Anthony Bonato; Fan R.K. Chung. London: Springer, 2007. p. 16-28 (Lecture Notes in Computer Science; Vol. 4863).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Distribution of pagerank mass among principle components of the web

AU - Avrachenkov, Konstantin

AU - Litvak, Nelly

AU - Pham, Kim Son

N1 - Conference code: 5

PY - 2007

Y1 - 2007

N2 - 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.

AB - 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.

KW - MSC-61J10

KW - MSC-68P10

U2 - 10.1007/978-3-540-77004-6_2

DO - 10.1007/978-3-540-77004-6_2

M3 - Conference contribution

SN - 978-3-540-77003-9

T3 - Lecture Notes in Computer Science

SP - 16

EP - 28

BT - Algorithms and Models for the Web-Graph

A2 - Bonato, Anthony

A2 - Chung, Fan R.K.

PB - Springer

CY - London

T2 - 5th International Workshop on Algorithms and Models for the Web-Graph, WAW 2007

Y2 - 11 December 2007 through 12 December 2007

ER -

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

Distribution of pagerank mass among principle components of the web

Abstract

Publication series

Workshop

Keywords

Access to Document

Fingerprint

Cite this