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.

[img]
Preview
PDF
Submitted Version

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

Abstract

© 2017 IEEE. 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.


Share

Citation/Export:
Social Networking:
Share |

Details

Item Type: Article
Status: Published
Creators/Authors:
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: 07 Sep 2020 16:55
URI: http://d-scholarship.pitt.edu/id/eprint/39623

Metrics

Monthly Views for the past 3 years

Plum Analytics

Altmetric.com


Actions (login required)

View Item View Item