Random Graph Generation and Structural Analysis: Trees, Forests, and Asymmetric Digraphs
MSc Thesis Proposal by:
Akanksha Masih
Date: 29th May 2026
Time: 1 pm
Location: Essex Hall 122
Abstract:
Random graph generation is fundamental to network modelling, algorithmic testing, and graph-based machine learning. However, the current generators consider dense graphs without structural constraints, such as forests and asymmetric digraphs. For forests, Prüfer codes, Bell number partitions, and message-passing algorithms all represent separate fundamental concepts, although none of the prior work considers how these can be combined to form a forest generation pipeline, nor does prior work consider whether different methods of generation lead to differences in forest structure given the same input parameters. Fragmentation studies have considered the topic of network disintegration, but have not used fragmentation to generate graphs. With respect to directed graphs, the Chartrand-Lesniak-Roberts Theorem indicates that any collection of distinct positive integers is achievable as the outdegrees of some asymmetric digraph; yet no algorithm has been constructed, nor does there exist any way of generating different realizations of the same construction, while current algorithms to generate directed graphs, including Havel-Hakimi and Directed 2K, have no way of enforcing asymmetry or working solely based on outdegree sets. This thesis addresses both gaps. To start with, we generate two types of forests: partition-based and reduction through message passing, comparing their structures to see if the process of generating forests has any impact on their structure. Then, we propose the first algorithm for implementing the Chartrand-Lesniak-Roberts construction method and randomize the results via Markov chain Monte Carlo sampling
Thesis Committee:
Internal Reader: Dr. Jessica Chen
External Reader: Dr. Dillian Yang
Advisor: Dr. Asish Mukhopadhyay
