Spectra of Adjacency and Laplacian Matrices of Inhomogeneous Erdős-Rényi Random Graphs

Abstract

Inhomogeneous Erdős-Rényi random graphs ${\mathbb{G}}_N$ on $N$ vertices in the non-dense regime are considered in this paper. The edge between the pair of vertices $\{i,j\}$ is retained with probability ${\epsilon }_{N}f(\frac{i}{N},\frac{j}{N})$, $1\le i\ne j\le N$, independently of other edges, where $f:[0,1]\times [0,1]\to [0,\infty )$ is a continuous function such that $f(x,y)=f(y,x)$ for all $x,y\in [0,1]$. We study the empirical distribution of both the adjacency matrix $A_N$ and the Laplacian matrix ${\Delta }_N$ associated with ${\mathbb{G}}_N$ in the limit as $N\to \infty$ when ${\lim }_{N\to \infty }{\epsilon }_N=0$ and ${\lim }_{N\to \infty }N{\epsilon }_N=\infty$. In particular, it is shown that the empirical spectral distributions of $A_N$ and ${\Delta }_N$, after appropriate scaling and centering, converge to deterministic limits weakly in probability. For the special case where $f(x,y)=r(x)r(y)$ with $r:[0,1]\to [0,\infty )$ a continuous function, we give an explicit characterization of the limiting distributions. Furthermore, applications of the results to constrained random graphs, Chung-Lu random graphs and social networks are shown.

Revised version. To appear in Random Matrices: theory and applications