Abstract
We study the relation between PageRank and other parameters of information networks such as in-degree, out-degree, and the fraction of dangling nodes. We model this relation through a stochastic equation inspired by the original definition of PageRank. Further, we use the theory of regular variation to prove that PageRank and in-degree follow power laws with the same exponent. The difference between these two power laws is in a multiplicative constant, which depends mainly on the fraction of dangling nodes, average in-degree, the power law exponent, and the damping factor. The out-degree distribution has a minor effect, which we explicitly quantify. Finally, we propose a ranking scheme which does not depend on out-degrees.
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 | Berlin, Heidelberg |
Publisher | Springer |
Pages | 108-123 |
Number of pages | 16 |
ISBN (Electronic) | 978-3-540-77004-6 |
ISBN (Print) | 978-3-540-77003-9 |
DOIs | |
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
- EWI-11672
- MSC-60J80
- METIS-245912
- MSC-90B15
- IR-62095
- MSC-68P10