Condensation of degrees emerging through a first-order phase transition in classical random graphs

We construct a compound Poisson process conditioned on its random summation that represents the sizes of the connected components in the sparse Erd\H{o}s-R\'enyi random graph $G(n,c/n)$. This new representation depicts a connection between the phase transition in the sparse random graph and the condensation transition in the zero-range model. Under this framework, we can derive moderate deviation principles for the maximun component, total number of connected components and e...

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

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

We propose a simple model of the evolution of a social network which involves local search and volatility (random decay of links). The model captures the crucial role the network plays for information diffusion. This is responsible for a feedback loop which results in a first-order phase transition between a very sparse network regime and a highly-connected phase. Phase coexistence and hysteresis take place for intermediate value of parameters. We derive a mean-field theory w...

It appeared recently that the classical random graph model used to represent real-world complex networks does not capture their main properties. Since then, various attempts have been made to provide accurate models. We study here a model which achieves the following challenges: it produces graphs which have the three main wanted properties (clustering, degree distribution, average distance), it is based on some real-world observations, and it is sufficiently simple to make i...

In analogy to superstatistics, which connects Boltzmann-Gibbs statistical mechanics to its generalizations through temperature fluctuations, complex networks are constructed from the fluctuating Erdos-Renyi random graphs. Here, using the quantum mechanical method, the exact analytic formula is presented for the hidden variable distribution, which describes the fluctuation and generates a generic degree distribution through the Poisson transformation. As an example, a static s...

We construct equilibrium networks by introducing an energy function depending on the degree of each node as well as the product of neighboring degrees. With this topological energy function, networks constitute a canonical ensemble, which follows the Boltzmann distribution for given temperature. It is observed that the system undergoes a topological phase transition from a random network to a star or a fully-connected network as the temperature is lowered. Both mean-field ana...

Zero-range processes, in which particles hop between sites on a lattice, are closely related to equilibrium networks, in which rewiring of links take place. Both systems exhibit a condensation transition for appropriate choices of the dynamical rules. The transition results in a macroscopically occupied site for zero-range processes and a macroscopically connected node for networks. Criticality, characterized by a scale-free distribution, is obtained only at the transition po...

Rare event statistics for random walks on complex networks are investigated using the large deviations formalism. Within this formalism, rare events are realized as typical events in a suitably deformed path-ensemble, and their statistics can be studied in terms of spectral properties of a deformed Markov transition matrix. We observe two different types of phase transition in such systems: (i) rare events which are singled out for sufficiently large values of the deformation...

The exponential family of random graphs represents an important and challenging class of network models. Despite their flexibility, conventionally used exponential random graphs have one shortcoming. They 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 generi...