Title: PageRank in Undirected Random Graphs,
Abstract: PageRank has numerous applications in information retrieval, reputation
systems, machine learning, and graph partitioning. In this paper, we study
PageRank in undirected random graphs with an expansion property. The Chung-Lu
random graph is an example of such a graph. We show that in the limit, as the
size of the graph goes to infinity, PageR- ank can be approximated by a mixture
of the restart distribution and the vertex degree distribution. We also extend
the result to Stochastic Block Model (SBM) graphs, where we show that there is
a correction term that depends on the community partitioning.