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.
Complete list of metadatas

Cited literature [37 references]  Display  Hide  Download

https://hal.inria.fr/hal-01675378
Contributor : Konstantin Avrachenkov <>
Submitted on : Thursday, January 4, 2018 - 3:23:19 PM
Last modification on : Thursday, November 14, 2019 - 5:38:06 PM

Links full text

Identifiers

Collections

Citation

Konstantin Avrachenkov, Arun Kadavankandy, Liudmila Ostroumova, Andrei Raigorodskii. PageRank in undirected random graphs. Internet Mathematics, Taylor & Francis, 2017, ⟨10.24166/im.09.2017⟩. ⟨hal-01675378⟩

Share

Metrics

Record views

191