Ensembles with hard constraints

This chapter introduces random graph ensembles involving hard constraints such as setting a fixed total number of links or fixed degree sequence, including properties of the partition function. It continues on from the previous chapter’s investigation of ensembles with soft-constrained numbers of two-stars (two-step paths) and soft-constrained total number of triangles, but now combined with a hard constraint on the total number of links. This illustrates phase transitions in a mixed-constrained ensemble – which in this case is shown to be a condensation transition, where the network becomes clumped. This is investigated in detail using techniques from statistical mechanics and also looking at the averaged eigenvalue spectrum of the ensemble. These phase transition phenomena have important implications for the design of graph generation algorithms. Although hard constraints can (by force) impose required values of observables, difficult-to-reconcile constraints can lead to graphs being generated with unexpected and unphysical overall topologies.