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.

15 pages, 10 figures. Minor modifications, references added, final version to appear in the Special Issue "Complex Networks' Structure and Dynamics'' of the International Journal of Bifurcation and Chaos

References in corpus (2)

• Finding Scientific Gems with Google
• How to make the top ten: Approximating PageRank from in-degree

Cited by in corpus (13)

• Multiplex PageRank
• Spectral centrality measures in complex networks
• Understanding the development of interest and self-efficacy in active-learning undergraduate physics courses
• Beyond performance metrics: Examining a decrease in students' physics self-efficacy through a social network lens
• Determining factors behind the PageRank log-log plot
• Schroedinger-like PageRank equation and localization in the WWW
• Inter-arrival times of message propagation on directed networks
• Distribution of PageRank Mass Among Principle Components of the Web
• In-Degree and PageRank of Web pages: Why do they follow similar power laws?
• Recognition of Emerging Technology Trends. Class-selective study of citations in the U.S. Patent Citation Network
• Atos: A Task-Parallel GPU Dynamic Scheduling Framework for Dynamic Irregular Computations
• On the initial value of PageRank
• Analysis of women leadership in enterprise social networks