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

DOI10.1016/J.AAM.2016.06.012MaRDI QIDQ730638zbMATH OpenOpenAlexFDO

Authors Xing Peng, Sinan Aksoy, Fan Chung

Publication date 28 December 2016

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

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

Mathematics Subject Classification ID

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

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.

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

Cites work

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

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)