Random graph ensembles with many short loops

In this article we give an in depth overview of the recent advances in the field of equilibrium networks. After outlining this topic, we provide a novel way of defining equilibrium graph (network) ensembles. We illustrate this concept on the classical random graph model and then survey a large variety of recently studied network models. Next, we analyze the structural properties of the graphs in these ensembles in terms of both local and global characteristics, such as degree...

In the last 15 years, statistical physics has been a very successful framework to model complex networks. On the theoretical side, this approach has brought novel insights into a variety of physical phenomena, such as self-organisation, scale invariance, emergence of mixed distributions and ensemble non-equivalence, that display unconventional features on heterogeneous networks. At the same time, thanks to their deep connection with information theory, statistical physics and...

In recent years there has been much progress in graph theory on questions of the following type. What is the threshold for a certain large substructure to appear in a random graph? When does a random graph contain all structures from a given family? And when does it contain them so robustly that even an adversary who is allowed to perturb the graph cannot destroy all of them? I will survey this progress, and highlight the vital role played by some newly developed methods, suc...

We discuss various ensembles of homogeneous complex networks and a Monte-Carlo method of generating graphs from these ensembles. The method is quite general and can be applied to simulate micro-canonical, canonical or grand-canonical ensembles for systems with various statistical weights. It can be used to construct homogeneous networks with desired properties, or to construct a non-trivial scoring function for problems of advanced motif searching.

We apply in this article (non rigorous) statistical mechanics methods to the problem of counting long circuits in graphs. The outcomes of this approach have two complementary flavours. On the algorithmic side, we propose an approximate counting procedure, valid in principle for a large class of graphs. On a more theoretical side, we study the typical number of long circuits in random graph ensembles, reproducing rigorously known results and stating new conjectures.

We introduce network $L$-cloning, a technique for creating ensembles of random networks from any given real-world or artificial network. Each member of the ensemble is an $L$-cloned network constructed from $L$ copies of the original network. The degree distribution of an $L$-cloned network and, more importantly, the degree-degree correlation between and beyond nearest neighbors are identical to those of the original network. The density of triangles in an \LC network, and he...

Clustering is the propensity of nodes that share a common neighbour to be connected. It is ubiquitous in many networks but poses many modelling challenges. Clustering typically manifests itself by a higher than expected frequency of triangles, and this has led to the principle of constructing networks from such building blocks. This approach has been generalised to networks being constructed from a set of more exotic subgraphs. As long as these are fully connected, it is then...

Infectious disease remains, despite centuries of work to control and mitigate its effects, a major problem facing humanity. This paper reviews the mathematical modelling of infectious disease epidemics on networks, starting from the simplest Erdos-Renyi random graphs, and building up structure in the form of correlations, heterogeneity and preference, paying particular attention to the links between random graph theory, percolation and dynamical systems representing transmiss...

We study the tailoring of structured random graph ensembles to real networks, with the objective of generating precise and practical mathematical tools for quantifying and comparing network topologies macroscopically, beyond the level of degree statistics. Our family of ensembles can produce graphs with any prescribed degree distribution and any degree-degree correlation function, its control parameters can be calculated fully analytically, and as a result we can calculate (a...

Real-world social and economic networks typically display a number of particular topological properties, such as a giant connected component, a broad degree distribution, the small-world property and the presence of communities of densely interconnected nodes. Several models, including ensembles of networks also known in social science as Exponential Random Graphs, have been proposed with the aim of reproducing each of these properties in isolation. Here we define a generaliz...