Link to the University of Pittsburgh Homepage
Link to the University Library System Homepage Link to the Contact Us Form
D-Scholarship @ Pitt Banner and Links to Homepage

CHALLENGES IN RANDOM GRAPH MODELS WITH DEGREE HETEROGENEITY: EXISTENCE, ENUMERATION AND ASYMPTOTICS OF THE SPECTRAL RADIUS

Burstein, David (2016) CHALLENGES IN RANDOM GRAPH MODELS WITH DEGREE HETEROGENEITY: EXISTENCE, ENUMERATION AND ASYMPTOTICS OF THE SPECTRAL RADIUS. Doctoral Dissertation, University of Pittsburgh. (Unpublished)

This is the latest version of this item.

[img]
Preview
 PDF
Download (2MB) | Preview

Abstract

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

Share

Citation/Export:
Social Networking:
Share |

Details

Item Type: University of Pittsburgh ETD
Status: Unpublished
Creators/Authors:
CreatorsEmailPitt UsernameORCID
Burstein, Daviddburste1@swarthmore.eduDAB176
ETD Committee:
TitleMemberEmail AddressPitt UsernameORCID
Committee ChairRubin, Jonathanjonrubin@pitt.edu
Committee MemberConstantine, Gregorygmc@pitt.edu
Committee MemberDoiron, Brentbdoiron@pitt.edu
Committee MemberIyengar, Satishssi@pitt.edu
Date: 30 September 2016
Date Type: Publication
Defense Date: 23 June 2016
Approval Date: 30 September 2016
Submission Date: 3 August 2016
Access Restriction: No restriction; Release the ETD for access worldwide immediately.
Number of Pages: 153
Institution: University of Pittsburgh
Schools and Programs: Dietrich School of Arts and Sciences > Mathematics
Degree: PhD - Doctor of Philosophy
Thesis Type: Doctoral Dissertation
Refereed: Yes
Uncontrolled Keywords: degree sequence, directed graph, Chung-Lu, random graphs, contingency table, digraph
Date Deposited: 30 Sep 2016 20:03
Last Modified: 15 Nov 2016 14:35
URI: http://d-scholarship.pitt.edu/id/eprint/29302

Available Versions of this Item

  • CHALLENGES IN RANDOM GRAPH MODELS WITH DEGREE HETEROGENEITY: EXISTENCE, ENUMERATION AND ASYMPTOTICS OF THE SPECTRAL RADIUS. (deposited 30 Sep 2016 20:03) [Currently Displayed]

Metrics

Monthly Views for the past 3 years

Plum Analytics

Actions (login required)

View Item View Item