Sampling of Random Graphs with Prescribed Degree Sequence

dc.contributor.advisorBassler, Kevin E.
dc.contributor.committeeMemberGunaratne, Gemunu H.
dc.contributor.committeeMemberWeglein, Arthur B.
dc.contributor.committeeMemberJosić, Krešimir
dc.creatorZhang, Weibin 1990-
dc.creator.orcid0000-0001-6161-0978
dc.date.accessioned2020-01-04T03:48:17Z
dc.date.createdMay 2019
dc.date.issued2019-05
dc.date.submittedMay 2019
dc.date.updated2020-01-04T03:48:17Z
dc.description.abstractRandom graph generation is the foundation of the statistical study of complex networks, which are commonly found in social, technological, and biological systems. In empirical studies, often only limited information about the topological structure of a network is available. In order to make the best use of this information, one must sample the ensemble of graphs that satisfy the constraint of the known structure, but are otherwise as random as possible. Similar to the microcanonical ensemble and canonical ensemble in statistical physics, there are two types of methods to generate an ensemble of graphs with prescribed topological constraints. A hard constraint method generates an ensemble of graphs in which each graph satisfies the constraints exactly. On the other hand, a soft constraint method generates an ensemble of graphs in which the constraints are satisfied only on average within the ensemble. In this dissertation, inspired by the idea of maximizing entropy, improvements in a hard constraint method called Sequential Importance Sampling (SIS) are developed for the case when the number of connections of each node, the degree sequence, is prescribed. Among the improvements is a more stable method of calculating ensemble averages that allows much larger networks to be sampled. With the improved methods, results from hard constraint methods are compared with those of soft constraint methods. It is found that soft constraint methods significantly overestimate the global clustering coefficient for both regular random graphs and scale-free graphs. This implies that problems exist with many network analyses and that care must be taken about the assumptions of network statistical analyses. A dynamical model to generate random graphs with prescribed degrees is also considered. The graphs resulting from this model are split graphs. We develop a linear complexity algorithm to decompose any graph into a series of split graphs, which can potentially be used to improve the efficiency of hard constraint sampling methods.
dc.description.departmentPhysics, Department of
dc.format.digitalOriginborn digital
dc.format.mimetypeapplication/pdf
dc.identifier.urihttps://hdl.handle.net/10657/5780
dc.language.isoeng
dc.rightsThe author of this work is the copyright owner. UH Libraries and the Texas Digital Library have their permission to store and provide access to this work. Further transmission, reproduction, or presentation of this work is prohibited except with permission of the author(s).
dc.subjectGraph sampling
dc.subjectSequential importance sampling
dc.subjectExponential random graph models
dc.titleSampling of Random Graphs with Prescribed Degree Sequence
dc.type.dcmiText
dc.type.genreThesis
local.embargo.lift2021-05-01
local.embargo.terms2021-05-01
thesis.degree.collegeCollege of Natural Sciences and Mathematics
thesis.degree.departmentPhysics, Department of
thesis.degree.disciplinePhysics
thesis.degree.grantorUniversity of Houston
thesis.degree.levelDoctoral
thesis.degree.nameDoctor of Philosophy

Files

Original bundle

Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
ZHANG-DISSERTATION-2019.pdf
Size:
1.99 MB
Format:
Adobe Portable Document Format

License bundle

Now showing 1 - 2 of 2
No Thumbnail Available
Name:
PROQUEST_LICENSE.txt
Size:
4.43 KB
Format:
Plain Text
Description:
No Thumbnail Available
Name:
LICENSE.txt
Size:
1.81 KB
Format:
Plain Text
Description: