Extreme values of the stationary distribution of random walks on directed graphs

DOI10.1016/J.AAM.2016.06.012zbMATH Open1352.05074arXiv1602.01162OpenAlexW2963771335MaRDI QIDQ730638FDOQ730638

Authors: Xing Peng, Sinan Aksoy, Fan Chung 

Publication date: 28 December 2016

Published in: Advances in Applied Mathematics (Search for Journal in Brave)

Abstract: We examine the stationary distribution of random walks on directed graphs. In particular, we focus on the {em principal ratio}, which is the ratio of maximum to minimum values of vertices in the stationary distribution. We give an upper bound for this ratio over all strongly connected graphs on $n$ vertices. We characterize all graphs achieving the upper bound and we give explicit constructions for these extremal graphs. Additionally, we show that under certain conditions, the principal ratio is tightly bounded. We also provide counterexamples to show the principal ratio cannot be tightly bounded under weaker conditions.

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

Recommendations

• Diameter and stationary distribution of random \(r\)-out digraphs
• Stationary distribution and cover time of random walks on random digraphs
• Oriented spanning trees and stationary distribution of digraphs
• The simple random walk and max-degree walk on a directed graph
• Principal eigenvectors of irregular graphs

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Directed graphs (digraphs), tournaments (05C20) Eigenvalues, singular values, and eigenvectors (15A18)

Cites Work

• Laplacians and the Cheeger inequality for directed graphs
• On maximal entries in the principal eigenvector of graphs
• Principal eigenvectors of irregular graphs
• On the bounds of maximal entries in the principal eigenvector of symmetric nonnegative matrix
• Eigenvectors and eigenvalues of non-regular graphs
• Bounds for the Greatest Latent Root of a Positive Matrix
• On the Maximal Eigenvector of a Positive Matrix
• Bounds for Perron eigenvectors and subdominant eigenvalues of positive matrices
• Local partitioning for directed graphs using pagerank
• A Remark on Minc’s Maximal Eigenvector Bound for Positive Matrices

Cited In (4)

• Forest formulas of discrete Green's functions
• Automorphisms and isogeny graphs of abelian varieties, with applications to the superspecial Richelot isogeny graph
• Extreme value statistics of positive recurrent centrally biased random walks
• Oriented spanning trees and stationary distribution of digraphs

This page was built for publication: Extreme values of the stationary distribution of random walks on directed graphs

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