Sparse random graphs: Eigenvalues and eigenvectors

Linh V. Tran, Van H. Vu, Ke WangRandom Struct. Algorithms 2013 · DOI

TL;DR

This paper investigates the spectral properties (eigenvalues and eigenvectors) of two fundamental random graph models: Erdős-Rényi graphs and random regular graphs. The authors prove that the distribution of eigenvalues for sparse random regular graphs converges to the semicircle law, a significant extension of previous results, and provide bounds on the "infinity norm" of eigenvectors, answering a long-standing question.

What Problem Does This Paper Address?

Understanding the structure of complex networks is a central theme in many scientific disciplines. Random graph models provide a simplified yet powerful framework to study this. The eigenvalues and eigenvectors of a graph's adjacency matrix encode crucial information about its connectivity and structure. While the behavior of these spectral quantities has been studied for dense random graphs (like Erdős-Rényi graphs with a constant edge probability), the case of sparse graphs (where the number of edges per vertex is small or grows slowly) is much less understood. Specifically, two key questions were open:

  1. Does the semicircle law, a fundamental result for dense random graphs, hold for sparse random regular graphs as the degree tends to infinity?
  2. How "spread out" are the eigenvectors of sparse random graphs? Can an eigenvector have a significant "mass" concentrated on a few vertices, or are they generally delocalized?

Methods

The paper employs a combination of techniques from random matrix theory and graph theory.

  • Semicircle Law for Sparse Regular Graphs: The authors extend the semicircle law to random regular graphs with a degree $d$ that tends to infinity with the number of vertices $n$. Their approach is distinct from prior work and relies on a comparison method and a powerful concentration lemma (Lemma 2.2) that bounds the deviation of the empirical spectral distribution from the semicircle law.
  • Infinity Norm of Eigenvectors: To bound the infinity norm of eigenvectors, the authors utilize a "small perturbation lemma" (Lemma 3.1). This lemma relates the eigenvectors of a random graph to those of a slightly perturbed matrix with Gaussian entries. They then leverage results from random matrix theory concerning the distribution of eigenvalues and eigenvector localization. The proofs involve intricate technical machinery, including the Stieltjes transform and concentration inequalities.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis of random graph models, not empirical datasets.

Key Insights and Ideas

  • Semicircle Law for Sparse Regular Graphs: The most significant result is establishing the semicircle law for random regular graphs as the degree $d \to \infty$. This unifies the spectral behavior of sparse and dense random graphs under a common limiting distribution, suggesting a deeper structural similarity.
  • Delocalization of Eigenvectors: The paper provides a positive answer to the question of whether eigenvectors are generally delocalized in sparse random graphs. They show that for a wide range of edge probabilities (or degrees), the infinity norm of any eigenvector is "small" (o(1)), meaning no single vertex dominates the eigenvector's contribution.
  • Quantitative Bounds: Beyond the qualitative "smallness" of the infinity norm, the paper provides quantitative bounds, especially for eigenvectors corresponding to eigenvalues away from the extreme values of the spectrum. These bounds are expressed in terms of the graph's sparsity parameters.
  • Technical Advancements: The paper introduces or adapts sophisticated techniques from random matrix theory, such as concentration theorems for the empirical spectral distribution and the use of auxiliary functions for bounding eigenvector norms, which may be of broader interest.

Key Results

  • Theorem 1.5: For random regular graphs $G_{n,d}$ with $d \to \infty$ as $n \to \infty$, the empirical spectral distribution of the normalized adjacency matrix converges to the standard semicircle distribution.
  • Theorem 1.16: For Erdős-Rényi graphs $G(n,p)$ with $p = \omega(\log n / n)$, there exists an orthonormal basis of eigenvectors $\{u_1, \dots, u_n\}$ such that for every $i$, $||u_i||_\infty = o(1)$ almost surely. This answers Question 1.8.
  • Theorem 1.17: Provides a quantitative bound for the infinity norm of eigenvectors corresponding to eigenvalues away from the spectrum's edge, showing $||u_i||_\infty = O((\log^{2.2} g(n) \log n / np)^{1/10})$ where $p = g(n) \log n / n$.

Limitations and Future Work

  • Random Regular Graphs (d fixed): While the paper addresses $d \to \infty$, the case of fixed $d$ for random regular graphs (McKay's law) is mentioned but not directly extended by the methods used here.
  • Eigenvectors at the Spectrum Edge: The quantitative bounds on eigenvector infinity norms are strongest for eigenvalues away from the spectrum's edge (i.e., near $\pm 2$). The behavior of eigenvectors corresponding to eigenvalues close to the edge is less precisely characterized, though some results are provided.
  • Generalization of Questions: The paper poses conjectures (1.14 and 1.15) that generalize the eigenvector delocalization questions to random unit vectors, suggesting future research directions.
  • Methodological Extension: The authors note that their method for proving the semicircle law for sparse regular graphs is different from previous approaches and might not directly extend to the case where $d$ grows very slowly (e.g., $d = n^{o(1)}$).

The paper opens avenues for further research into the spectral properties of sparse random graphs, particularly concerning the precise behavior of eigenvectors at the spectrum's edge and the extension of these results to more general graph models.

Summary updated

BibTeX
@article{tran2013sparse,
  author = {Linh V. Tran and Van H. Vu and Ke Wang},
  title = {{Sparse random graphs: Eigenvalues and eigenvectors}},
  journal = {Random Struct. Algorithms},
  year = {2013},
  doi = {10.1002/rsa.20406},
}
Figure