Link to the University of Pittsburgh Homepage
Link to the University Library System Homepage Link to the Contact Us Form

Moment-based spectral analysis of random graphs with given expected degrees

Preciado, VM and Rahimian, MA (2017) Moment-based spectral analysis of random graphs with given expected degrees. IEEE Transactions on Network Science and Engineering, 4 (4). 215 - 228.

Submitted Version

Download (2MB) | Preview
[img] Plain Text (licence)
Download (1kB)


We analyze the eigenvalues of a random graph ensemble, proposed by Chung and Lu, in which a given sequence of expected degrees, denoted by wn = (w(n) 1 ; . . .; w(n) n ), is prescribed on the n nodes of a random graph. We focus on the eigenvalues of the normalized (random) adjacency matrix of the graph ensemble, defined as An = nrn p a(n) i;j n i;j=1, where rn = 1= Pn i=1 w(n) i and a(n) i;j = 1 if there is an edge between the nodes fi; jg, 0 otherwise. The empirical spectral distribution of An, denoted by Fn, 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 converges weakly to a deterministic distribution F as n→∞. Furthermore, we fully characterize this deterministic distribution by providing explicit closed-form expressions for the moments of F((.). We illustrate our results with two well-known degree distributions, namely, the power-law and the exponential degree distributions. Based on our results, we provide significant insights about the bulk behavior of the eigenvalue spectrum; in particular, we analyze the quasi-triangular spectral distribution of power-law networks.


Social Networking:
Share |


Item Type: Article
Status: Published
CreatorsEmailPitt UsernameORCID
Preciado, VM
Rahimian, MARAHIMIAN@pitt.eduRAHIMIAN0000-0001-9384-1041
Date: 1 October 2017
Date Type: Publication
Journal or Publication Title: IEEE Transactions on Network Science and Engineering
Volume: 4
Number: 4
Page Range: 215 - 228
DOI or Unique Handle: 10.1109/tnse.2017.2712064
Schools and Programs: Swanson School of Engineering > Industrial Engineering
Refereed: Yes
Date Deposited: 17 Aug 2020 17:08
Last Modified: 09 Apr 2021 00:55


Monthly Views for the past 3 years

Plum Analytics

Actions (login required)

View Item View Item