Concentration of the Stationary Distribution on General Random Directed Graphs

2013/09/18 by Franklin Kenter, Kenter, Franklin H. J.
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Probability (math.PR) #Random Matrices and Applications #Stochastic processes and statistical mechanics

paper · pdf · doi:10.48550/arxiv.1309.4811

openalex publication_date 2013/09/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We consider a random model for directed graphs whereby an arc is placed from one vertex to another with a prescribed probability which may vary from arc to arc. Using perturbation bounds as well as Chernoff inequalities, we show that the stationary distribution of a Markov process on a random graph is concentrated near that of the "expected" process under mild conditions. These conditions involve the ratio between the minimum and maximum in- and out-degrees, the ratio of the minimum and maximum entry in the stationary distribution, and the smallest singu- lar value of the transition matrix. Lastly, we give examples of applications of our results to well-known models such as PageRank and G(n, p).

Citations

• Concentration of the adjacency matrix and of the Laplacian in random graphs with independent edges
• Comparison of perturbation bounds for the stationary distribution of a Markov chain
• Random matrices: Universality of local eigenvalue statistics
• Authoritative sources in a hyperlinked environment

Related

• Minimum stationary values of sparse random directed graphs
• Concentration of measure and mixing for Markov chains
• Concentration and mean field approximation results for Markov processes on large networks
• Concentration of the adjacency matrix and of the Laplacian in random graphs with independent edges
• A Random-Walk Concentration Principle for Occupancy Processes on Finite Graphs