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 : Chung-Lu random graphs undirected random graphs PageRank expander graphs
Document type :
Reports
Complete list of metadata
https://hal.inria.fr/hal-01227383
Contributor : Arun Kadavankandy <>
Submitted on : Friday, November 25, 2016 - 4:45:21 PM
Last modification on : Monday, March 29, 2021 - 2:47:23 PM

Files

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

Identifiers

Collections

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

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

Share

Metrics

Record views

393

Files downloads

1637

 

Contact                    Legal Notice                    Personal Data