Spectra of adjacency and Laplacian matrices of inhomogeneous Erdős–Rényi random graphs

Abstract

This paper considers inhomogeneous Erdős–Rényi random graphs GN on N vertices in the non-sparse non-dense regime. The edge between the pair of vertices {i,j} is retained with probability εNf(iN,jN), 1≤i≠j≤N, independently of other edges, where f:[0,1]×[0,1]→[0,∞) is a continuous function such that f(x,y)=f(y,x) for all x,y∈[0,1]. We study the empirical distribution of both the adjacency matrix AN and the Laplacian matrix ΔN associated with GN, in the limit as N→∞ when limN→∞εN=0 and limN→∞NεN=∞. In particular, we show that the empirical spectral distributions of AN and Δ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]→[0,∞) a continuous function, we give an explicit characterization of the limiting distributions. Furthermore, we apply our results to constrained random graphs, Chung–Lu random graphs and social networks.