Source-linked AI summary
Spectra of edge-independent random graphs
Linyuan Lu, Xing Peng
TL;DR
The paper studies spectral bounds for random graphs, whose adjacency and normalized Laplacian spectra can help infer graph structure. It uses edge independence in a closed-walk analysis and improves earlier Laplacian error bounds by removing an ln n factor under conditions.
Problem
Earlier work established results for random-graph Laplacians, and this paper seeks to improve their error bounds.
Source: §1 · p. 2Method
The spectral-bound analysis expands over closed walks and uses independence of the edges to rewrite the associated expression.
Source: §2 · p. 4Results
The paper removes an ln n factor from earlier Laplacian error bounds under some conditions.
Source: §1 · p. 2Takeaways & Limitations
Adjacency and normalized Laplacian spectra can be used to infer graph structure, including properties related to random-walk mixing and expansion.
Source: §1 · p. 1An intermediate bound is weaker than Theorem 1 because the uniform bounds on K and σ2 are too coarse.
Source: §2 · p. 4
Abstract
from arXiv · showhide
Let $G$ be a random graph on the vertex set $\{1,2,..., n\}$ such that edges in $G$ are determined by independent random indicator variables, while the probability $p_{ij}$ for $\{i,j\}$ being an edge in $G$ is not assumed to be equal. Spectra of the adjacency matrix and the normalized Laplacian matrix of $G$ are recently studied by Oliveira and Chung-Radcliffe. Let $A$ be the adjacency matrix of $G$, $\bar A=\E(A)$, and $\Delta$ be the maximum expected degree of $G$. Oliveira first proved that almost surely $\|A-\bar A\|=O(\sqrt{\Delta \ln n})$ provided $\Delta\geq C \ln n$ for some constant $C$. Chung-Radcliffe improved the hidden constant in the error term using a new Chernoff-type inequality for random matrices. Here we prove that almost surely $\|A-\bar A\|\leq (2+o(1))\sqrt{\Delta}$ with a slightly stronger condition $\Delta\gg \ln^4 n$. For the Laplacian $L$ of $G$, Oliveira and Chung-Radcliffe proved similar results $\|L-\bar L|=O(\sqrt{\ln n}/\sqrt{\delta})$ provided the minimum expected degree $\delta\gg \ln n$; we also improve their results by removing the $\sqrt{\ln n}$ multiplicative factor from the error term under some mild conditions. Our results naturally apply to the classic Erd\H{o}s-R\'enyi random graphs, random graphs with given expected degree sequences, and bond percolation of general graphs.
1 Introduction
The introduction studies adjacency and normalized-Laplacian spectra for edge-independent random graphs, where edge probabilities need not be equal. It presents improved spectral bounds and applications to expected-degree models and bond percolation.
1 Introduction
- Spectra provide information about graph structure, including chromatic and independence numbers for adjacency matrices and walk mixing and expansion for Laplacians.The introduction also lists diameters, the Cheeger constant, isoperimetric inequalities, expander graphs, and quasi-random graphs as Laplacian applications.Source: §1 · p. 1
- Edge probabilities p_ij may differ, and the paper studies adjacency and normalized-Laplacian spectra in this general edge-independent model.The expected adjacency matrix is denoted by ¯A, and Δ is the maximum expected degree.Source: §1 · p. 2
- Under Δ ≫ ln^4 n, the paper removes the ln n factor from the adjacency-matrix error term.Theorem 1 gives the result for edge-independent random graphs.Source: §1 · p. 2
- For the normalized Laplacian, the paper removes the √ln n error factor under conditions including δ ≫ max{k, ln^4 n}.Here k counts the eigenvalues of the expected Laplacian that do not satisfy the stated approximation condition.Source: §1 · p. 2
- For the expected-degree-sequence special case, the introduction notes that the expected Laplacian complement has rank one and all non-trivial expected-Laplacian eigenvalues equal 1.It obtains the corresponding result by applying Corollary 1.Source: §1 · pp. 2–3
- The normalized-Laplacian result also applies to bond percolation on a general host graph, with a minimum-degree condition and a condition on p.The introduction states Theorem 4 for percolated graphs whose Laplacian has all but k eigenvalues satisfying the stated approximation condition.Source: §1 · p. 3
2 Spectral bound of random symmetric matrices
This section develops spectral-norm bounds for random symmetric matrices using trace and closed-walk counting arguments. It applies those bounds to adjacency-matrix fluctuations and notes that a coarse uniform bound is weaker than the sharper graph-specific result.
Application to adjacency matrices
- Applying the general random-matrix bound to A − ¯A gives an upper bound weaker than Theorem 1 because uniform bounds on K and σ² are too coarse.The section identifies this loss as the reason for moving beyond the uniform bounds.Source: §2 · p. 4
General random-matrix bound
- The section introduces a theorem generalizing Vu’s result for random symmetric matrices, with constants C and C′.The theorem’s setup uses independent mean-zero entries with bounded absolute value and bounded variance.Source: §2 · p. 4
Proof setup
- The proof scales the matrix and sets diagonal entries to zero, noting that the resulting diagonal change affects the spectral norm by at most K.The argument treats this change as negligible relative to the stated upper bound.Source: §2 · p. 4
Trace method
- Wigner’s trace method expresses the norm estimate through expectations over closed walks, and independence eliminates walks containing an edge used only once.Thus only walks in which every edge appears at least twice need to be counted.Source: §2 · p. 4
Walk counting
- Vu’s improved bound on the number of canonical good walks supplies a counting estimate used in the matrix-bound proof.The walks are relabeled so vertices first appear in the order 1 through p.Source: §2 · p. 5
3 Lemmas for Laplacian eigenvalues
This section establishes lemmas used to control normalized-Laplacian eigenvalues. It relates the random and expected Laplacians through a four-matrix decomposition and uses concentration of vertex degrees around their expectations.
Expected Laplacian spectrum
- The expected Laplacian is ¯L = I − T^−1/2 ¯A T^−1/2, and its eigenvectors also diagonalize T^−1/2 ¯A T^−1/2 with eigenvalues 1 − μ_i.Here T is the diagonal matrix of expected degrees and μ_i are the eigenvalues of ¯L.Source: §3 · p. 8
Laplacian decomposition
- The difference L − ¯L is decomposed into four matrices, whose spectral norms are bounded separately.The decomposition is the stated route toward the Laplacian estimate.Source: §3 · p. 8
Auxiliary bounds
- The section sets up lemmas and corollaries to bound the terms in the four-matrix decomposition, including a Chernoff inequality for independent random variables.These results are presented as ingredients for proving Theorem 2.Source: §3 · p. 9
Degree concentration
- When every expected degree t_i is at least ln n, all degrees satisfy d_i = (1 + o(1))t_i with probability at least 1 − 1/n².The preceding lemma bounds |d_i − t_i| for all vertices under that condition.Source: §3 · p. 9
4 Proof of Theorem 2
The proof bounds the normalized Laplacian deviation by decomposing it into four terms and combining bounds on their norms. It then applies Weyl’s Theorem.
4 Proof of Theorem 2
- Under δ ≫ ln n, the degree-based variables Xi have E(Xi) ≤ 1, Var(Xi) ≤ 2 + o(1), and a stated covariance formula.The proof uses a second-moment argument and Chebychev’s inequality to control their weighted sum.Source: §4 · pp. 11–12
- Writing M as ΦQΦ′ reduces its norm estimate to controlling a normalization discrepancy represented by U.The proof defines U = (D−1/2T 1/2−I)ΦQ and estimates its norm.Source: §4 · p. 13
- The proof bounds ∥L −¯L∥ by the sum of the norms of four terms, then applies Weyl’s Theorem.The bound combines Lemma 2, Corollary 2, Corollary 3, and Lemma 9.Source: §4 · pp. 14–15