The two-star model: exact solution in the sparse regime and condensation transition

We study the asymptotics of large directed graphs, constrained to have certain densities of edges and/or outward $p$-stars. Our models are close cousins of exponential random graph models (ERGMs), in which edges and certain other subgraph densities are controlled by parameters. The idea of directly constraining edge and other subgraph densities comes from Radin and Sadun. Such modeling circumvents a phenomenon first made precise by Chatterjee and Diaconis: that in ERGMs it is...

Exponential random graph models, or ERGMs, are a flexible and general class of models for modeling dependent data. While the early literature has shown them to be powerful in capturing many network features of interest, recent work highlights difficulties related to the models' ill behavior, such as most of the probability mass being concentrated on a very small subset of the parameter space. This behavior limits both the applicability of an ERGM as a model for real data and ...

We study a model of network with clustering and desired node degree. The original purpose of the model was to describe optimal structures of scientific collaboration in the European Union. The model belongs to the family of exponential random graphs. We show by numerical simulations and analytical considerations how a very simple Hamiltonian can lead to surprisingly complicated and eventful phase diagram.

The exponential family of random graphs is one of the most promising class of network models. Dependence between the random edges is defined through certain finite subgraphs, analogous to the use of potential energy to provide dependence between particle states in a grand canonical ensemble of statistical physics. By adjusting the specific values of these subgraph densities, one can analyze the influence of various local features on the global structure of the network. Loosel...

We study the family of network models derived by requiring the expected properties of a graph ensemble to match a given set of measurements of a real-world network, while maximizing the entropy of the ensemble. Models of this type play the same role in the study of networks as is played by the Boltzmann distribution in classical statistical mechanics; they offer the best prediction of network properties subject to the constraints imposed by a given set of observations. We giv...

The random graph of Erdos and Renyi is one of the oldest and best studied models of a network, and possesses the considerable advantage of being exactly solvable for many of its average properties. However, as a model of real-world networks such as the Internet, social networks or biological networks it leaves a lot to be desired. In particular, it differs from real networks in two crucial ways: it lacks network clustering or transitivity, and it has an unrealistic Poissonian...

We analyze a model that interpolates between scale-free and Erdos-Renyi networks. The model introduced generates a one-parameter family of networks and allows to analyze the role of structural heterogeneity. Analytical calculations are compared with extensive numerical simulations in order to describe the transition between these two important classes of networks. Finally, an application of the proposed model to the study of the percolation transition is presented.

Conventionally used exponential random graphs cannot directly model weighted networks as the underlying probability space consists of simple graphs only. Since many substantively important networks are weighted, this limitation is especially problematic. We extend the existing exponential framework by proposing a generic common distribution for the edge weights. Minimal assumptions are placed on the distribution, that is, it is non-degenerate and supported on the unit interva...

We consider a large class of exponential random graph models and prove the existence of a region of parameter space corresponding to multipartite structure, separated by a phase transition from a region of disordered graphs.

We introduce and analyse ensembles of 2-regular random graphs with a tuneable distribution of short cycles. The phenomenology of these graphs depends critically on the scaling of the ensembles' control parameters relative to the number of nodes. A phase diagram is presented, showing a second order phase transition from a connected to a disconnected phase. We study both the canonical formulation, where the size is large but fixed, and the grand canonical formulation, where the...