Back to search
University of Waterloo
Uniform Generation of Graphical Realizations of Joint Degree Matrices
Abstract
dc:description.abstractIn this thesis, we introduce JDM_GEN, an algorithm designed to uniformly generate graphical realizations of a given joint degree matrix. Amanatidis and Kleer previously employed an MCMC-based method to address this problem. Their method fully resolved the case of two degree classes, and showed that their switch Markov chain is rapidly mixing. While our algorithm imposes certain restrictions on the maximum degrees, it is applicable to any bounded number of degree classes and has a runtime complexity linear in the number of edges.
Degree
thesis:*- Grantor dc:publisher
- University of Waterloo
- Year dc:date.issued
- 2023
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Zhou, Qianye
- Advisor dc:contributor.advisor
-
- Gao, Jane
Subjects
dc:subject × 3Rights
- Language dc:language.iso
- en
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- http://hdl.handle.net/10012/19901