TY - JOUR

T1 - Local weak convergence for pagerank

AU - Garavaglia, Alessandro

AU - van der Hofstad, Remco

AU - Litvak, Nelly

PY - 2020/2

Y1 - 2020/2

N2 - Page Rank is a well-known algorithm for measuring centrality in networks. It was originally proposed by Google for ranking pages in the World Wide Web. One of the intriguing empirical properties of PageRank is the socalled 'power-law hypothesis': in a scale-free network, the PageRank scores follow a power law with the same exponent as the (in-)degrees. To date, this hypothesis has been confirmed empirically and in several specific random graphs models. In contrast, this paper does not focus on one random graph model but investigates the existence of an asymptotic PageRank distribution, when the graph size goes to infinity, using local weak convergence. This may help to identify general network structures in which the power-law hypothesis holds. We start from the definition of local weak convergence for sequences of (random) undirected graphs, and extend this notion to directed graphs. To this end, we define an exploration process in the directed setting that keeps track of in- and out-degrees of vertices. Then we use this to prove the existence of an asymptotic PageRank distribution. As a result, the limiting distribution of PageRank can be computed directly as a function of the limiting object. We apply our results to the directed configuration model and continuous-time branching processes trees, as well as to preferential attachment models.

AB - Page Rank is a well-known algorithm for measuring centrality in networks. It was originally proposed by Google for ranking pages in the World Wide Web. One of the intriguing empirical properties of PageRank is the socalled 'power-law hypothesis': in a scale-free network, the PageRank scores follow a power law with the same exponent as the (in-)degrees. To date, this hypothesis has been confirmed empirically and in several specific random graphs models. In contrast, this paper does not focus on one random graph model but investigates the existence of an asymptotic PageRank distribution, when the graph size goes to infinity, using local weak convergence. This may help to identify general network structures in which the power-law hypothesis holds. We start from the definition of local weak convergence for sequences of (random) undirected graphs, and extend this notion to directed graphs. To this end, we define an exploration process in the directed setting that keeps track of in- and out-degrees of vertices. Then we use this to prove the existence of an asymptotic PageRank distribution. As a result, the limiting distribution of PageRank can be computed directly as a function of the limiting object. We apply our results to the directed configuration model and continuous-time branching processes trees, as well as to preferential attachment models.

KW - Directed random graphs

KW - Local weak convergence

KW - PageRank

UR - http://www.scopus.com/inward/record.url?scp=85087560416&partnerID=8YFLogxK

U2 - 10.1214/19-AAP1494

DO - 10.1214/19-AAP1494

M3 - Article

AN - SCOPUS:85087560416

VL - 30

SP - 40

EP - 79

JO - The Annals of Applied Probability

JF - The Annals of Applied Probability

SN - 1050-5164

IS - 1

ER -