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

Authors Victor M. Preciado, Mohammad Amin Rahimian

Publication date 10 December 2015

Random graphs (graph-theoretic aspects) (05C80) Random matrices (probabilistic aspects) (60B20)

Abstract: 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

o v e r l i n e w_{n}^{^{T}} = (w_{1}^{(n)}, l d o t s, w_{n}^{(n)})

is prescribed on the ensemble. Let

m a t h b f a_{i, 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:

m a t h b f A_{n}

=

[m a t h b f a_{i, j} / s q r t n]_{i, j = 1}^{n}

. The empirical spectral distribution of

m a t h b f A_{n}

denoted by

m a t h b f F_{n} (m a t h o r d c d o t)

is the empirical measure putting a mass

1 / n

at each of the

n

real eigenvalues of the symmetric matrix

m a t h b f A_{n}

. Under some technical conditions on the expected degree sequence, we show that with probability one,

m a t h b f F_{n} (m a t h o r d c d o t)

converges weakly to a deterministic distribution

F (m a t h o r d c d o t)

. Furthermore, we fully characterize this distribution by providing explicit expressions for the moments of

F (m a t h o r d c d o t)

. 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.

This page was built for publication: Moment-Based Spectral Analysis of Random Graphs with Given Expected Degrees

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