Developments on the Configuration Model

The configuration model is a model of random graphs where we first choose the distribution of the degrees of the nodes and then attach them together until no more connection remains available. This model is very useful for creating graphs with any given degree distribution and has interesting tree-like local properties. I currently work on characterizing two structures constructed on the configuration model.

The first structure is the minimum spanning tree of the configuration model, when endowed with random uniform edge weights. Building on a previous work studying the outcome of Prim’s algorithm on an infinite configuration model, we hope to extend their method to prove that the minimum spanning tree on the configuration model has a similar local structure.

The second structure is the giant component in an almost critical configuration model. The configuration model is known to reach criticality when its size-biased parameter reaches 1 and further shows star-like behavior when the say parameter is strictly below 1. Here we want to investigate the regime where this parameter converges to 1 from below and hope to show that different regimes exist, depending on the speed of convergence towards 1.

These two projects would give interesting insights on the configuration model, a common random graph model, and would further highlight the duality between the global graph and its local tree-like structure.