Spectra of edge-independent random graphs

MaRDI QIDQ396954zbMATH OpenFDO

Authors Linyuan Lu, Xing Peng

Publication date 14 August 2014

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1204.6207, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v20i4p27

zbMATH Keywords

edge-independent random grapheigenvaluesLaplacianrandom matrix

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Random graphs (graph-theoretic aspects) (05C80) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40) Eigenvalues, singular values, and eigenvectors (15A18)

Abstract: Let $G$ be a random graph on the vertex set $1,2,\mathrm{...},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$, $$, and $Delta$ be the maximum expected degree of $G$. Oliveira first proved that almost surely $$ provided $DeltageqClnn$ 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 $$ with a slightly stronger condition $Deltaggl{n}^{4}n$. For the Laplacian $L$ of $G$, Oliveira and Chung-Radcliffe proved similar results $$ provided the minimum expected degree $deltagglnn$; we also improve their results by removing the $sqrtlnn$ multiplicative factor from the error term under some mild conditions. Our results naturally apply to the classic ErdH{o}s-R'enyi random graphs, random graphs with given expected degree sequences, and bond percolation of general graphs.

Review text

Summary: Let \(G\) be a random graph on the vertex set \(\{1,2,\ldots, n\}\) such that edges in \(G\) are determined by independent random indicator variables, while the probabilities \(p_{ij}\) for \(\{i,j\}\) being an edge in \(G\) are not assumed to be equal. Spectra of the adjacency matrix and the normalized Laplacian matrix of \(G\) are recently studied by \textit{R. Oliveira} [``Concentration of the adjacency matrix and of the Laplacian in random graphs with independent edges, Preprint, \url{arXiv:0911.0600}] and \textit{F. Chung} and \textit{M. Radcliffe} [Electron. J. Comb. 18, No. 1, Research Paper P215, 14 p. (2011; Zbl 1229.05248)]. Let \(A\) be the adjacency matrix of \(G, \bar A=\text{ E}(A)\), and \(\Delta\) be the maximum expected degree of \(G\). Oliveira [loc. cit.] first proved that asymptotically almost surely \(\|A-\bar A\|=O(\sqrt{\Delta \ln n})\) provided \(\Delta\geq C \ln n\) for some constant \(C\). Chung-Radcliffe [loc. cit.] improved the hidden constant in the error term using a new Chernoff-type inequality for random matrices. Here we prove that asymptotically almost surely \(\|A-\bar A\|\leq (2+o(1))\sqrt{\Delta}\) with a slightly stronger condition \(\Delta\gg \ln^4 n\). For the Laplacian matrix \(L\) of \(G\), Oliveira [loc. cit.] and Chung-Radcliffe [loc. cit.] proved similar results \(\|L-\bar L\|=O(\sqrt{\ln n}/\sqrt{\delta})\) provided the minimum expected degree \(\delta\geq C' \ln n\) for some constant \(C'\); 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 classical Erdős-Rényi random graphs, random graphs with given expected degree sequences, and bond percolation of general graphs.

Recommendations

• On the spectra of general random graphs
• A remark on the spectra of random graphs with given expected degrees
• Spectral distributions of adjacency and Laplacian matrices of random graphs
• The spectral gap of random graphs with given expected degrees
• The Spectra of Random Graphs with Given Expected Degrees

Cites work

• A note on an inequality involving the normal distribution
• A proof of Alon’s second eigenvalue conjecture and related problems
• Eigenvalues of random power law graphs
• scientific article; zbMATH DE number 3717357 (Why is no real title available?)
• scientific article; zbMATH DE number 3278338 (Why is no real title available?)
• scientific article; zbMATH DE number 964896 (Why is no real title available?)
• On the concentration of eigenvalues of random symmetric matrices
• On the distribution of the roots of certain symmetric matrices
• On the Laplacian Eigenvalues of G_n,p
• On the second eigenvalue and random walks in random d-regular graphs
• On the spectra of general random graphs
• Spectra of random graphs with given expected degrees
• Spectral distributions of adjacency and Laplacian matrices of random graphs
• Spectral norm of random matrices
• Spectral techniques applied to sparse random graphs
• The eigenvalues of random symmetric matrices
• The Largest Eigenvalue of Sparse Random Graphs
• The spectral gap of random graphs with given expected degrees
• User-friendly tail bounds for sums of random matrices

Cited in

(26)

• Two-sample hypothesis testing for inhomogeneous random graphs
• Testing goodness of fit of random graph models
• Limit theorems for eigenvectors of the normalized Laplacian for random graphs
• Concentration of the spectral norm of Erdős-Rényi random graphs
• Spectral statistics of sparse Erdős-Rényi graph Laplacians
• Designs for estimating the treatment effect in networks with interference
• On the spectra of general random mixed graphs
• Clustering coefficients of large networks
• The two-to-infinity norm and singular subspace geometry with applications to high-dimensional statistics
• Consistency of spectral clustering in stochastic block models
• Capacity of an associative memory model on random graph architectures
• The spectra of random mixed graphs
• Non-backtracking spectra of weighted inhomogeneous random graphs
• Statistical inference on random dot product graphs: a survey
• scientific article; zbMATH DE number 6902684 (Why is no real title available?)
• The Spectra of Random Graphs with Given Expected Degrees
• Spectra of random graphs with given expected degrees
• Robust Recommendation via Social Network Enhanced Matrix Completion
• Estrada index of dynamic random graphs
• On the spectra of general random graphs
• The spectral barycentre of a set of graphs with community structure
• Bootstrapping networks with latent space structure
• An overview of asymptotic normality in stochastic blockmodels: cluster analysis and inference
• Concentration of the adjacency matrix and of the normalized Laplacian matrix in general random signed graphs
• An omnibus embedding of multiple random graphs and implications for multiscale network inference
• The spectrum estimates for random graphs with given expected degrees

This page was built for publication: Spectra of edge-independent random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q396954)