PageRank in Undirected Random Graphs

Authors Konstantin Avrachenkov, Arun Kadavankandy, Liudmila Ostroumova Prokhorenkova, Andrei M. Raigorodskii

Publication date 23 March 2017

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.

This page was built for publication: PageRank in Undirected Random Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6284727)