Show simple item record

dc.contributor.advisorBassler, Kevin E.
dc.creatorZhang, Weibin 1990-
dc.date.accessioned2020-01-04T03:48:17Z
dc.date.createdMay 2019
dc.date.issued2019-05
dc.date.submittedMay 2019
dc.identifier.urihttps://hdl.handle.net/10657/5780
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.format.mimetypeapplication/pdf
dc.language.isoen
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.date.updated2020-01-04T03:48:17Z
dc.type.genreThesis
thesis.degree.nameDoctor of Philosophy
thesis.degree.levelDoctoral
thesis.degree.disciplinePhysics
thesis.degree.grantorUniversity of Houston
thesis.degree.departmentPhysics, Department of
dc.contributor.committeeMemberGunaratne, Gemunu H.
dc.contributor.committeeMemberWeglein, Arthur B.
dc.contributor.committeeMemberJosić, Krešimir
dc.creator.orcid0000-0001-6161-0978
local.embargo.terms2021-05-01
local.embargo.lift2021-05-01
dcterms.accessRightsThe full text of this item is not available at this time because the student has placed this item under an embargo for a period of time. The Libraries are not authorized to provide a copy of this work during the embargo period.
dc.type.dcmiText
dc.format.digitalOriginborn digital
dc.description.departmentPhysics, Department of
thesis.degree.collegeCollege of Natural Sciences and Mathematics


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record