Resolvent of large random graphs

Charles Bordenave, Marc LelargeRandom Struct. Algorithms 2010 · OpenReview

TL;DR

This paper connects the spectral properties of large random graphs to their local structure, specifically when they resemble trees. The authors develop a unified framework to prove that the empirical spectral distribution of these graphs converges to a limit spectral measure, providing a new formula for its Stieltjes transform. This work offers a powerful tool for analyzing the behavior of large, sparse random networks.

What Problem Does This Paper Address?

The spectral analysis of large random graphs is a challenging problem, especially for "dilute" or sparse graphs where the number of edges grows linearly with the number of vertices. Unlike dense graphs, where spectral convergence is well-understood, sparse graphs exhibit unique phenomena. Existing methods often struggle to capture the intricate local structure of these graphs, which can be approximated by infinite trees. This paper aims to bridge this gap by providing a rigorous mathematical treatment that links the local weak convergence of graphs to the convergence of their spectral measures. This is crucial for understanding the behavior of many real-world networks, such as social networks, biological networks, and the internet, which are often sparse and exhibit tree-like properties locally.

Methods

The core of the paper lies in establishing a connection between the local weak convergence of a sequence of graphs and the convergence of their spectral measures. The authors introduce two main theorems:

  • Theorem 1: This theorem states that if a sequence of graphs converges locally weakly to a limit graph (which can be an infinite tree), then the empirical spectral distribution of the adjacency or Laplacian matrices of these graphs converges to a limiting spectral measure. This convergence is proven under two assumptions: one for deterministic graphs (D) and another for random graphs (R), both requiring uniform integrability of the root's degree.
  • Theorem 2: This theorem characterizes the limit spectral measure using the Stieltjes transform. It shows that for graphs whose local weak limit is a Galton-Watson Tree (GWT), the Stieltjes transform of the limit spectral measure satisfies a recursive distributional equation (RDE). This RDE is derived by analyzing the resolvent of the graph's adjacency or Laplacian matrix.

The proofs utilize tools from random matrix theory, particularly the concept of the resolvent of a matrix and its Stieltjes transform. The authors also leverage the theory of graph limits and the Skorokhod Representation Theorem to handle the convergence of random graphs. For specific cases, like regular graphs and Erdös-Rényi graphs, they derive explicit formulas for the spectral density.

Datasets

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

Key Insights and Ideas

  • Local Structure Dictates Global Spectrum: The most significant insight is that the local structure of a large random graph (specifically, its convergence to a tree-like structure) fundamentally determines the convergence of its global spectral properties. This is a powerful unifying principle.
  • Unified Treatment for Sparse Graphs: The paper provides a unified framework for analyzing the spectra of various classes of sparse random graphs, including regular graphs, Erdös-Rényi graphs, and graphs with a given degree sequence.
  • Recursive Distributional Equations (RDEs) for Spectra: The characterization of the limit spectral measure via RDEs is a novel and powerful approach. These equations elegantly capture the self-similar nature of tree-like structures and their spectral properties.
  • Resolvent as a Key Tool: The use of the resolvent of the adjacency/Laplacian matrix and its Stieltjes transform proves to be a highly effective tool for analyzing spectral convergence in this context.

Key Results

  • Theorem 1: Establishes the convergence of the empirical spectral distribution for large random graphs that converge locally to a tree.
  • Theorem 2: Provides a characterization of the limit spectral measure for such graphs via a recursive distributional equation for its Stieltjes transform.
  • Explicit Formulas: For specific examples like uniform k-regular graphs and Erdös-Rényi graphs, the paper derives explicit formulas for the density of the spectral measure. For k-regular graphs, the spectral density is shown to be related to the semi-circular law.

Limitations and Future Work

  • Assumption (A'): The proof of Theorem 2 relies on a stronger assumption (A') that the second moment of the degree distribution is finite. The authors note that they do not know if this convergence holds in general without this assumption.
  • Weighted Graphs (α=1): The paper mentions that the case α=1 for weighted graphs is more complicated due to the dependence introduced by the diagonal term T(Gn), which breaks the nice recursive structure of the RDE. This suggests a direction for future research.
  • Generalization to Other Graph Limits: While the paper focuses on convergence to trees, the authors hint at extensions to other graph limits and applications in bipartite graphs and uniform random trees, which are explored in later sections.
  • Computational Aspects: The paper is theoretical. Future work could explore efficient numerical methods for computing these spectral measures for large graphs.

Summary updated

Abstract

We analyze the convergence of the spectrum of large random graphs to the spectrum of a limit infinite graph. We apply these results to graphs converging locally to trees and derive a new formula for ...
BibTeX
@inproceedings{bordenave2010resolvent,
  author = {Charles Bordenave and Marc Lelarge},
  title = {{Resolvent of large random graphs}},
  booktitle = {Random Struct. Algorithms},
  year = {2010},
  url = {https://openreview.net/forum?id=RlB3WEmMYiY},
}
Figure