Moment-Based Spectral Analysis of Random Graphs with Given Expected Degrees

In this paper, we analyze the limiting spectral distribution of the adjacency matrix of a random graph ensemble, proposed by Chung and Lu, in which a given expected degree sequence overlinewn^T = (w(n)1,ldots,w(n)n) is prescribed on the ensemble. Let ai,j =1 if there is an edge between the nodes i,j and zero otherwise, and consider the normalized random adjacency matrix of the graph ensemble: An = [ai,j/√n]i,j=1n. The empirical spectral distribution of An denoted by Fn(mathord·) is the empirical measure putting a mass 1/n at each of the n real eigenvalues of the symmetric matrix An. Under some technical conditions on the expected degree sequence, we show that with probability one, Fn(mathord·) converges weakly to a deterministic distribution F(mathord·). Furthermore, we fully characterize this distribution by providing explicit expressions for the moments of F(mathord·). We apply our results to well-known degree distributions, such as power-law and exponential. The asymptotic expressions of the spectral moments in each case provide significant insights about the bulk behavior of the eigenvalue spectrum.