Analytic solution of the two-star model with correlated degrees

Network scientists rely on random graphs to model the behaviour of complex networks observed in social, technological, and biological systems. One common approach to such network modelling starts by measuring an empirical set of observables, and then builds an ensemble of random graphs to match these features in an average sense. These models – so-called exponential random graph(ERG) models – reproduce a set of empirical patterns while keeping other network properties entirely random, and thereby offer benchmark models to distinguish between random and non-random traits in real-world networks.
Some ERG models exhibit phase transitions – abrupt changes in the macroscopic properties of the graph ensemble – which can provide obstacles to using the models productively. The simplest model with this feature, known as the two-star model, assumes that the graph ensemble is constrained by the average number of edges and the average number of “two-stars,” these being pair of edges sharing a single common node. In a new paper, LML External Fellows Fernando Metz and Isaac Pérez Castillo, working with a number of colleagues, build on previous work to derive results for the two-star model in the presence of degree-degree correlations, a typical property of real networks. This takes a significant step toward providing analytical results of relevance for real-world applications.
Focussing on degree-degree correlations between nearest neighbours and next nearest neighbours, and working in the sparse regime, the authors calculate the free energy exactly by introducing an upper cut-off in the degree sequence. They then show that the model’s phase diagram exhibits a first-order critical line, surrounded by a metastable region, in which the graph sampling process can get stuck in a local minimum of the free energy. This first-order transition separates a phase characterized by an approximate Poisson degree distribution from a different condensed phase where the degree distribution strongly depends on the degree correlations. The authors also go on to quantify the degree correlations through the degree assortativity corresponding to nearest neighbour nodes and to next nearest neighbour nodes at the end points of two-stars. Overall, the authors expect these new results will be useful in avoiding eventual pitfalls in the generation of null models of networks with degree-degree correlations.
The paper is available at

Leave a Reply

Your email address will not be published. Required fields are marked *