Transitions in loopy random graphs with fixed degrees and arbitrary degree distributions

Generalised degrees provide a natural bridge between local and global topological properties of networks. We define the generalised degree to be the number of neighbours of a node within one and two steps respectively. Tailored random graph ensembles are used to quantify and compare topological properties of networks in a systematic and precise manner, using concepts from information theory. We calculate the Shannon entropy of random graph ensembles constrained with a specifi...

The unconstrained exponential family of random graphs assumes no prior knowledge of the graph before sampling, but it is natural to consider situations where partial information about the graph is known, for example the total number of edges. What does a typical random graph look like, if drawn from an exponential model subject to such constraints? Will there be a similar phase transition phenomenon (as one varies the parameters) as that which occurs in the unconstrained expo...

We develop a statistical mechanics approach for random networks with uncorrelated vertices. We construct equilibrium statistical ensembles of such networks and obtain their partition functions and main characteristics. We find simple dynamical construction procedures that produce equilibrium uncorrelated random graphs with an arbitrary degree distribution. In particular, we show that in equilibrium uncorrelated networks, fat-tailed degree distributions may exist only starting...

We show, through local estimates and simulation, that if one constrains simple graphs by their densities $\varepsilon$ of edges and $\tau$ of triangles, then asymptotically (in the number of vertices) for over $95\%$ of the possible range of those densities there is a well-defined typical graph, and it has a very simple structure: the vertices are decomposed into two subsets $V_1$ and $V_2$ of fixed relative size $c$ and $1-c$, and there are well-defined probabilities of edge...

The entropy of network ensembles characterizes the amount of information encoded in the network structure, and can be used to quantify network complexity, and the relevance of given structural properties observed in real network datasets with respect to a random hypothesis. In many real networks the degrees of individual nodes are not fixed but change in time, while their statistical properties, such as the degree distribution, are preserved. Here we characterize the distribu...

Network models with latent geometry have been used successfully in many applications in network science and other disciplines, yet it is usually impossible to tell if a given real network is geometric, meaning if it is a typical element in an ensemble of random geometric graphs. Here we identify structural properties of networks that guarantee that random graphs having these properties are geometric. Specifically we show that random graphs in which expected degree and cluster...

Our general subject is the emergence of phases, and phase transitions, in large networks subjected to a few variable constraints. Our main result is the analysis, in the model using edge and triangle subdensities for constraints, of a sharp transition between two phases with different symmetries, analogous to the transition between a fluid and a crystalline solid.

We study the relaxation dynamics of fully clustered networks (maximal number of triangles) to an unclustered state under two different edge dynamics---the double-edge swap, corresponding to degree-preserving randomization of the configuration model, and single edge replacement, corresponding to full randomization of the Erd\H{o}s--R\'enyi random graph. We derive expressions for the time evolution of the degree distribution, edge multiplicity distribution and clustering coeffi...

Clustering $\unicode{x2013}$ the tendency for neighbors of nodes to be connected $\unicode{x2013}$ quantifies the coupling of a complex network to its latent metric space. In random geometric graphs, clustering undergoes a continuous phase transition, separating a phase with finite clustering from a regime where clustering vanishes in the thermodynamic limit. We prove this geometric-to-nongeometric phase transition to be topological in nature, with anomalous features such as ...

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...