Dissertation/Thesis Abstract

Challenges in random graph models with degree heterogeneity: existence, enumeration and asymptotics of the spectral radius
by Burstein, David E., Ph.D., University of Pittsburgh, 2016, 163; 10298731
Abstract (Summary)

In order to understand how the network structure impacts the underlying dynamics, we seek an assortment of methods for efficiently constructing graphs of interest that resemble their empirically observed counterparts. Since many real world networks obey degree heterogeneity, where different nodes have varying numbers of connections, we consider some challenges in constructing random graphs that emulate the property. Initially we focus on the Uniform Model, where we would like to uniformly sample from all graphs that realize a given bi-degree sequence. We provide easy to implement, sufficient criteria to guarantee that a bi-degree sequence corresponds to a graph. Consequently, we construct novel results regarding asymptotics of the number of graphs that realize a given degree sequence, where knowledge of the aforementioned enumeration result will assist us in constructing realizations from the Uniform Model. Finally, we consider another random directed graph model that exhibits degree heterogeneity, the Chung-Lu random graph model and prove concentration results regarding the dominating eigenvalue of the corresponding adjacency matrix. We extend our analysis to a more generalized model that allows for intricate community structure and demonstrate the impact of the community structure in networks with Kuramoto and SIS epidemiological dynamics.

Indexing (document details)
Advisor: Rubin, Jonathan
School: University of Pittsburgh
School Location: United States -- Pennsylvania
Source: DAI-B 78/05(E), Dissertation Abstracts International
Subjects: Applied Mathematics
Keywords: Contingency tables, Degree sequence, Digraphs, Random graphs
Publication Number: 10298731
ISBN: 9781369417463
Copyright © 2019 ProQuest LLC. All rights reserved. Terms and Conditions Privacy Policy Cookie Policy