April 24, 2015
The $2$-star model is the simplest exponential random graph model that displays complex behavior, such as degeneracy and phase transition. Despite its importance, this model has been solved only in the regime of dense connectivity. In this work we solve the model in the finite connectivity regime, far more prevalent in real world networks. We show that the model undergoes a condensation transition from a liquid to a condensate phase along the critical line corresponding, in the ensemble parameters space, to the Erd\"os-R\'enyi graphs. In the fluid phase the model can produce graphs with a narrow degree statistics, ranging from regular to Erd\"os-R\'enyi graphs, while in the condensed phase, the "excess" degree heterogeneity condenses on a single site with degree $\sim\sqrt{N}$. This shows the unsuitability of the two-star model, in its standard definition, to produce arbitrary finitely connected graphs with degree heterogeneity higher than Erd\"os-R\'enyi graphs and suggests that non-pathological variants of this model may be attained by softening the global constraint on the two-stars, while keeping the number of links hardly constrained.
Similar papers 1
February 18, 2021
Exponential random graphs are important to model the structure of real-world complex networks. Here we solve the two-star model with degree-degree correlations in the sparse regime. The model constraints the average correlation between the degrees of adjacent nodes (nearest neighbors) and between the degrees at the end-points of two-stars (next nearest neighbors). We compute exactly the network free energy and show that this model undergoes a first-order transition to a conde...
May 19, 2004
The p-star model or exponential random graph is among the oldest and best-known of network models. Here we give an analytic solution for the particular case of the 2-star model, which is one of the most fundamental of exponential random graphs. We derive expressions for a number of quantities of interest in the model and show that the degenerate region of the parameter space observed in computer simulations is a spontaneously symmetry broken phase separated from the normal ph...
October 15, 2013
This paper gives a way to simulate from the two star probability distribution on the space of simple graphs via auxiliary variables. Using this simulation scheme, the model is explored for various domains of the parameter values, and the phase transition boundaries are identified, and shown to be similar as that of the Curie-Weiss model of statistical physics. Concentration results are obtained for all the degrees, which further validate the phase transition predictions.
October 16, 2013
In this paper, we explore the two-star Exponential Random Graph Model, which is a two parameter exponential family on the space of simple labeled graphs. We introduce auxiliary variables to express the two-star model as a mixture of the $\beta$ model on networks. Using this representation, we study asymptotic distribution of the number of edges, and the sampling variance of the degrees. In particular, the limiting distribution for the number of edges has similar phase transit...
December 21, 2015
The exponential family of random graphs has been a topic of continued research interest. Despite the relative simplicity, these models capture a variety of interesting features displayed by large-scale networks and allow us to better understand how phases transition between one another as tuning parameters vary. As the parameters cross certain lines, the model asymptotically transitions from a very sparse graph to a very dense graph, completely skipping all intermediate struc...
August 7, 2014
In this paper, we study exponential random graph models subject to certain constraints. We obtain some general results about the asymptotic structure of the model. We show that there exists non-trivial regions in the phase plane where the asymptotic structure is uniform and there also exists non-trivial regions in the phase plane where the asymptotic structure is non-uniform. We will get more refined results for the star model and in particular the two-star model for which a ...
April 20, 2019
Due to their conceptual and mathematical simplicity, Erd\"os-R\'enyi or classical random graphs remain as a fundamental paradigm to model complex interacting systems in several areas. Although condensation phenomena have been widely considered in complex network theory, the condensation of degrees has hitherto eluded a careful study. Here we show that the degree statistics of the classical random graph model undergoes a first-order phase transition between a Poisson-like dist...
April 25, 2014
We consider a family of directed exponential random graph models parametrized by edges and outward stars. Much of the important statistical content of such models is given by the normalization constant of the models, and in particular, an appropriately scaled limit of the normalization, which is called the free energy. We derive precise asymptotics for the normalization constant for finite graphs. We use this to derive a formula for the free energy. The limit is analytic ever...
November 18, 2014
We study the asymptotics for sparse exponential random graph models where the parameters may depend on the number of vertices of the graph. We obtain exact estimates for the mean and variance of the limiting probability distribution and the limiting log partition function of the edge-(single)-star model. They are in sharp contrast to the corresponding asymptotics in dense exponential random graph models. Similar analysis is done for directed sparse exponential random graph mo...
August 2, 2011
We derive the full phase diagram for a large family of two-parameter exponential random graph models, each containing a first order transition curve ending in a critical point.