Rankings in directed configuration models with heavy tailed in-degrees

DOI10.1214/23-AAP1955MaRDI QIDQ6180388zbMATH OpenOpenAlexFDO

Authors Xing Shi Cai, Pietro Caputo, Guillem Perarnau, Matteo Quattropani

Publication date 19 January 2024

Published in The Annals of Applied Probability (Search for Journal in Brave)

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

zbMATH Keywords

random walksdirected configuration modelmixing timestationary distributionPageRankpower-law distributions

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Random walks on graphs (05C81)

Abstract: We consider the extremal values of the stationary distribution of sparse directed random graphs with given degree sequences and their relation to the extremal values of the in-degree sequence. The graphs are generated by the directed configuration model. Under the assumption of bounded $(2+eta)$-moments on the in-degrees and of bounded out-degrees, we obtain tight comparisons between the maximum value of the stationary distribution and the maximum in-degree. Under the further assumption that the order statistics of the in-degrees have a power-law behavior, we show that the extremal values of the stationary distribution also have a power-law behavior with the same index. In the same setting, we prove that these results extend to the PageRank scores of the random digraph, thus confirming a version of the so-called power-law hypothesis. Along the way, we establish several facts about the model, including the mixing time cutoff and the characterization of the typical values of the stationary distribution, which were previously obtained under the assumption of bounded in-degrees.

Recommendations

• Generalized PageRank on directed configuration networks
• PageRank on inhomogeneous random digraphs
• PageRank in Scale-Free Random Graphs
• Pagerank asymptotics on directed preferential attachment networks
• PageRank's behavior under degree correlations

Cites work

• scientific article; zbMATH DE number 1246230 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 953131 (Why is no real title available?)
• scientific article; zbMATH DE number 2089988 (Why is no real title available?)
• A fixed point theorem for distributions
• A survey of max-type recursive distributional equations
• Asymptotic analysis for personalized web search
• Asymptotic properties and absolute continuity of laws stable by random weighted mean.
• Characterizing optimal sampling of binary contingency tables via the configuration model
• Cutoff at the ``entropic time for sparse Markov chains
• Cutoff for nonbacktracking random walks on sparse random graphs
• Cutoff phenomena for random walks on random regular graphs
• Determining Factors Behind the PageRank Log-Log Plot
• Diameter and stationary distribution of random \(r\)-out digraphs
• Directed random graphs with given degree distributions
• Distances in random graphs with finite mean and infinite variance degrees
• Generalized PageRank on directed configuration networks
• Heavy-Tail Phenomena
• In-Degree and PageRank: why do they follow similar power laws?
• Local weak convergence for PageRank
• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Mixing time of PageRank surfers on sparse random digraphs
• Moments, continuity, and multifractal analysis of Mandelbrot martingales
• On generalized multiplicative cascades
• On tail probabilities for martingales
• Optimal Transport
• PageRank in Scale-Free Random Graphs
• PageRank of Scale-Free Growing Networks
• PageRank on inhomogeneous random digraphs
• PageRank's behavior under degree correlations
• Pagerank asymptotics on directed preferential attachment networks
• Probability. Theory and examples.
• Quick detection of top-\(k\) personalized PageRank lists
• Random walk on sparse random digraphs
• Random walks on the random graph
• Stationary distribution and cover time of random walks on random digraphs
• Stationary distribution and cover time of sparse directed configuration models
• Stein's method for concentration inequalities
• The Size of the Largest Strongly Connected Component of a Random Digraph with a Given Degree Sequence
• The diameter of the directed configuration model
• The evolution of the mixing rate of a simple random walk on the giant component of a random graph
• The giant component of the directed configuration model revisited
• The probability that a random multigraph is simple
• Typical distances in the directed configuration model

Cited in

(2)

• On the meeting of random walks on random DFA
• Meeting, coalescence and consensus time on random directed graphs

This page was built for publication: Rankings in directed configuration models with heavy tailed in-degrees

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