Skip to Main content Skip to Navigation
Reports

PageRank in undirected random graphs

Konstantin Avrachenkov 1 Arun Kadavankandy 1 Liudmila Ostroumova 2 Andrei Raigorodskii 2 
1 MAESTRO - Models for the performance analysis and the control of networks
CRISAM - Inria Sophia Antipolis - Méditerranée
2 Yandex [Moscou]
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 expansion property. The Chung-Lu random graph represents an example of such graphs. We show that in the limit, as the size of the graph goes to infinity, PageRank can be represented by a mixture of the restart distribution and the vertex degree distribution.
Keywords : undirected random graphs Chung-Lu random graphs expander graphs PageRank
Document type :
Reports
Complete list of metadata
https://hal.inria.fr/hal-01227383
Contributor : Arun Kadavankandy Connect in order to contact the contributor
Submitted on : Friday, November 25, 2016 - 4:45:21 PM
Last modification on : Saturday, June 25, 2022 - 7:43:59 PM

Files

Vignette du document
RR-8983v2.pdf
Files produced by the author(s)

Identifiers

Collections

INRIA | INRIA-RRRT | INSMI | INRIA2 | TDS-MACS | LARA | ANR

Citation

Konstantin Avrachenkov, Arun Kadavankandy, Liudmila Ostroumova, Andrei Raigorodskii. PageRank in undirected random graphs. [Research Report] RR-8983, Inria Sophia Antipolis. 2015, pp.26. ⟨hal-01227383v2⟩

Export

BibTeX TEI DC DCterms EndNote Datacite

Share

Metrics

Record views

240

Files downloads

1189

 

Contact                    Legal Notice                    Personal Data