RANDOM WALKS ON DIRECTED NETWORKS: THE CASE OF PAGERANK
Abstract
PageRank, the prestige measure for Web pages used by Google, is the stationary probability of a peculiar random walk on directed graphs, which interpolates between a pure random walk and a process where all nodes have the same probability of being visited. We give some exact results on the distribution of PageRank in the cases in which the damping factor q approaches the two limit values 0 and 1. When q → 0 and for several classes of graphs the distribution is a power law with exponent 2, regardless of the in-degree distribution. When q → 1 it can always be derived from the in-degree distribution of the underlying graph, if the out-degree is the same for all nodes.
References
- Nature 406, 378 (2000), DOI: 10.1038/35019019. Crossref, ISI, Google Scholar
- Rev. Mod. Phys. 74, 47 (2002), DOI: 10.1103/RevModPhys.74.47. Crossref, ISI, Google Scholar
- Science 286, 509 (1999). Crossref, ISI, Google Scholar
- Phys. Rep. 424, 175 (2006), DOI: 10.1016/j.physrep.2005.10.009. Crossref, ISI, Google Scholar
P. Boldi , M. Santini and S. Vigna , PageRank as a function of the damping factor, Proc. Fourteenth Int. World Wide Web Conf. (ACM Press, Chiba, Japan, 2005) pp. 557–566. Google Scholar- Comput. Networks 30, 107 (1998). ISI, Google Scholar
- Chen, P., Xie, H., Maslov, S. & Redner, S. [2006] "Finding scientific gems with Google," Technical Report, physics/0604130 at www.arXiv.org . Google Scholar
- Phys. Rev. Lett. 85, 4633 (2000), DOI: 10.1103/PhysRevLett.85.4633. Crossref, ISI, Google Scholar
- Adv. Phys. 51, 1079 (2002), DOI: 10.1080/00018730110112519. Crossref, ISI, Google Scholar
- Publ. Math. Debrecen 6, 290 (1959). Google Scholar
- Fortunato, S., Boguñá, M., Flammini, A. & Menczer, F. [2005] "How to make the top ten: Approximating PageRank from in-degree," Technical Report, cs.IR/0511016 at www.arXiv.org . Google Scholar
- Hall, B. H., Jaffe, A. B. & Tratjenberg, M. [2001] "The NBER patent citation data file: Lessons, insights and methodological tools.," NBER Working Paper 8498 . Google Scholar
-
B. D. Hughes , Random Walks and Random Environments, Random Walks 1 ( Oxford University Press , NY , 1995 ) . Google Scholar - LNCS 1627, 1 (1999). Google Scholar
- Phys. Rev. E 63, 066123 (2001), DOI: 10.1103/PhysRevE.63.066123. Crossref, ISI, Google Scholar
- SIAM Rev. 45, 167 (2003), DOI: 10.1137/S003614450342480. Crossref, ISI, Google Scholar
G. Pandurangan , P. Raghavan and E. Upfal , Using pagerank to characterize Web structure, Proc. 8th Ann. Int. Conf. Combinatorics and Computing (COCOON) (Springer-Verlag, Singapore, 2002) pp. 330–339. Google ScholarR. Pastor-Satorras and A. Vespignani , Evolution and Structure of the Internet (Cambridge University Press, Cambridge, UK, 2004) pp. 148–156. Crossref, Google Scholar- Nature 72, 294 (1905), DOI: 10.1038/072294b0. Crossref, Google Scholar
| Remember to check out the Most Cited Articles! |
|---|
|
Check out our Bifurcation & Chaos |


