Spectrum of Markov Generators on Sparse Random Graphs

By Charles Bordenave, Pietro Caputo, Djalil CHAFAÏ. 2012

51 citations recorded by the source corpus.

We investigate the spectrum of the infinitesimal generator of the continuoustime random walk on a randomly weighted oriented graph. This is the non‐Hermitian random n × n matrix L defined by Ljk = Xjk if k ≠ j and Ljj = – Σk ≠ j Ljk, where (Xjk)j ≠ k are i.i.d. random weights. Under mild assumptions on the law of the weights, we establish convergence as n → ∞ of the empirical spectral distribution of L after centering and rescaling. In particular, our assumptions include sparse random graphs such as the oriented Erdős‐Rényi graph where each edge is present independently with probability p(n) → 0 as long as np(n) ≫ (log(n))6. The limiting distribution is characterized as an additive Gaussian deformation of the standard circular law. In free probability terms, this coincides with the Brown measure of the free sum of the circular element and a normal operator with Gaussian spectral measure. The density of the limiting distribution is analyzed using a subordination formula. Furthermore, we study the convergence of the invariant measure of L to the uniform distribution and establish estimates on the extremal eigenvalues of L.© 2014 Wiley Periodicals, Inc.

Subfields: Mathematical Physics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/52033a3269ef9272435a27973d5897da3f1b72f9

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Mathematical Physics

In Statistics and Probability

Citations in the corpus

Outlier Eigenvalues for Deformed I.I.D. Random Matrices (2014, result): “It is shown in [16] that β admits a density on C with respect to Lebesgue measure given by”
ALGEBRAIC CONNECTIVITY OF ERDÖS-RÉNYI GRAPHS NEAR THE CONNECTIVITY THRESHOLD (2014, background): “Bordenave, Caputo, and Chafäı [7] studied the spectrum of oriented Erdös-Rényi-type graph Laplacians, which are the infinitesimal generator of a continuous time random walk on the graph.”