Random Graph Generation and Structural Analysis: Trees, Forests, and Asymmetric Digraphs
MSc Thesis Defense by: Akanksha Masih
Date: Friday, September 18th, 2026
Time: 12:15 p.m. to 2:00 p.m.
Location: Essex Hall 122
Abstract:
This thesis studies methods for generating and analysing the structure of labelled trees, forests, and asymmetric digraphs. For labelled trees, Prüfer-sequence generation is compared with a recursive-counting method. The comparison shows that the Prüfer-based method is computationally more efficient. Forests are generated in two stages: vertex partitions are sampled according to Bell-number probabilities, and a uniform labelled tree is generated within each non-singleton component. A forest-count-weighted version of the method is also developed to generate labelled forests uniformly. The forests produced by these constructions are compared with those obtained by applying several pruning strategies to labelled trees.
The second part of the thesis presents explicit algorithms for constructing minimum-order asymmetric digraphs with prescribed outdegree sets. Beyond minimum order, degree-preserving transformations generate alternative realisations with the same outdegree sequence. These realisations provide degree-matched null-model reference ensembles for six real directed networks. The observed networks are compared with their corresponding ensembles using the largest strongly connected component, out–in assortativity, and reachability. This analysis helps determine which structural properties of the observed networks are not explained by the prescribed outdegree sequence alone.
Keywords: Random Graph Generation, Labelled Forests, Asymmetric Digraphs, Degree-Preserving Sampling, Network Null Models
Thesis Committee:
Internal Reader: Dr. Jessica Chen
External Reader: Dr. Dilian Yang
Advisor: Dr. Asish Mukhopadhyay
Chair: Dr. Andreas Maniatis
