PageRank in undirected random graphs - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Internet Mathematics Année : 2017

PageRank in undirected random graphs

Résumé

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.
Fichier principal
Vignette du fichier
1703.08057.pdf (305.62 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-01675378 , version 1 (04-01-2018)

Identifiants

Citer

Konstantin Avrachenkov, Arun Kadavankandy, Liudmila Ostroumova, Andrei Raigorodskii. PageRank in undirected random graphs. Internet Mathematics, 2017, ⟨10.24166/im.09.2017⟩. ⟨hal-01675378⟩
104 Consultations
18 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More