PageRank on inhomogeneous random digraphs

DOI10.1016/J.SPA.2019.07.002MaRDI QIDQ1986028zbMATH OpenOpenAlexWikidataFDO

Authors Jiung Lee, Mariana Olvera-Cravioto

Publication date 7 April 2020

Published in Stochastic Processes and their Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1707.02492

zbMATH Keywords

directed random graphsPageRankpower lawsranking algorithmsstochastic fixed-point equationsweighted branching processes

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Ergodic theorems, spectral theory, Markov operators (37A30) Asymptotic approximations, asymptotic expansions (steepest descent, etc.) (41A60) Convergence of probability measures (60B10) Branching processes (Galton-Watson, birth-and-death, etc.) (60J80) Information storage and retrieval of data (68P20) Graph theory (including graph drawing) in computer science (68R10)

Abstract: We study the typical behavior of a generalized version of Google's PageRank algorithm on a large family of inhomogeneous random digraphs. This family includes as special cases directed versions of classical models such as the Erd"os-R'enyi model, the Chung-Lu model, the Poissonian random graph and the generalized random graph, and is suitable for modeling scale-free directed complex networks where the number of neighbors a vertex has is related to its attributes. In particular, we show that the rank of a randomly chosen node in a graph from this family converges weakly to the attracting endogenous solution to the stochastic fixed-point equation ${\displaystyle }$mathcal{R} stackrel{mathcal{D}}{=} sum_{i=1}^{mathcal{N}} mathcal{C}_i mathcal{R}_i + mathcal{Q},${\displaystyle }$ where $(mathcalN,mathcalQ,{mathcal{C}_i}_{igeq1})$ is a real-valued vector with $mathcalNin0,1,2,\mathrm{...}$, the $mathcal{R}_i$ are i.i.d.~copies of $mathcalR$, independent of $(mathcalN,mathcalQ,{mathcal{C}_i}_{igeq1})$, with $mathcal{C}_i$ i.i.d.~and independent of $(mathcalN,mathcalQ)$; $stackrelmathcalD=$ denotes equality in distribution. This result can then be used to provide further evidence of the power-law behavior of PageRank on scale-free graphs.

Recommendations

• PageRank in Undirected Random Graphs
• PageRank in Scale-Free Random Graphs
• A note on the PageRank of undirected graphs
• \texttt{PageRank} and random walks on graphs
• PageRank for networks, graphs, and Markov chains
• Pagerank asymptotics on directed preferential attachment networks
• RANDOM WALKS ON DIRECTED NETWORKS: THE CASE OF PAGERANK
• Generalized PageRank on directed configuration networks

Cites work

• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Asymptotic analysis for personalized web search
• Complex graphs and networks
• Connected components in random graphs with given expected degree sequences
• Coupling on weighted branching trees
• Determining Factors Behind the PageRank Log-Log Plot
• Directed random graphs with given degree distributions
• Generalized PageRank on directed configuration networks
• Generating simple random graphs with prescribed degree distribution
• scientific article; zbMATH DE number 3150484 (Why is no real title available?)
• scientific article; zbMATH DE number 1257656 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 2089988 (Why is no real title available?)
• Implicit renewal theorem for trees with general weights
• Implicit renewal theory and power tails on trees
• In-Degree and PageRank: why do they follow similar power laws?
• Information ranking and power laws on trees
• Nonstandard regular variation of in-degree and out-degree in the preferential attachment model
• On a conditionally Poissonian graph process
• Optimal Transport
• PageRank of Scale-Free Growing Networks
• PageRank on inhomogeneous random digraphs
• Paths in graphs
• Random graph dynamics
• Random Graphs
• Random graphs and complex networks. Volume 1
• The average distances in random graphs with given expected degrees
• The Number of Components in Random Linear Graphs
• The phase transition in inhomogeneous random graphs
• The Volume of the Giant Component of a Random Graph with Given Expected Degrees
• Universality for the distance in finite variance random graphs

Cited in

(25)

• PageRank on inhomogeneous random digraphs
• Pagerank asymptotics on directed preferential attachment networks
• Local weak convergence for PageRank
• Maxima and sums of non-stationary random length sequences
• PageRank's behavior under degree correlations
• Coevolutionary systems and PageRank
• Convergence of the population dynamics algorithm in the Wasserstein metric
• PageRank regular digraphs with prime out-degrees
• Degree sequences of PageRank uniform graphs and digraphs with prime outdegrees
• PageRank in Scale-Free Random Graphs
• PageRank in Undirected Random Graphs
• RANDOM WALKS ON DIRECTED NETWORKS: THE CASE OF PAGERANK
• Probabilistic Relation between In-Degree and PageRank
• On the edges’ PageRank and line graphs
• PageRank for networks, graphs, and Markov chains
• Generalized PageRank on directed configuration networks
• The buck-passing game
• On Local Estimations of PageRank: A Mean Field Approach
• PageRank Nibble on the sparse directed stochastic block model
• Mixing time of PageRank surfers on sparse random digraphs
• Rankings in directed configuration models with heavy tailed in-degrees
• Stochastic recursions on directed random graphs
• Co-evolving dynamic networks
• Connectivity of random graphs after centrality-based vertex removal
• Power-law hypothesis for PageRank on undirected graphs

This page was built for publication: PageRank on inhomogeneous random digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1986028)