Constrained Markovian dynamics of random graphs

We investigate equilibrium properties of small world networks, in which both connectivity and spin variables are dynamic, using replicated transfer matrices within the replica symmetric approximation. Population dynamics techniques allow us to examine order parameters of our system at total equilibrium, probing both spin- and graph-statistics. Of these, interestingly, the degree distribution is found to acquire a Poisson-like form (both within and outside the ordered phase). ...

Random graphs with prescribed degree sequences have been widely used as a model of complex networks. Comparing an observed network to an ensemble of such graphs allows one to detect deviations from randomness in network properties. Here we briefly review two existing methods for the generation of random graphs with arbitrary degree sequences, which we call the ``switching'' and ``matching'' methods, and present a new method based on the ``go with the winners'' Monte Carlo met...

Large ensembles of stochastically evolving interacting particles describe phenomena in diverse fields including statistical physics, neuroscience, biology, and engineering. In such systems, the infinitesimal evolution of each particle depends only on its own state (or history) and the states (or histories) of neighboring particles with respect to an underlying, possibly random, interaction graph. While these high-dimensional processes are typically too complex to be amenable ...

Real-world networks evolve over time via additions or removals of vertices and edges. In current network evolution models, vertex degree varies or grows arbitrarily. A recently introduced degree-preserving network growth (DPG) family of models preserves vertex degree, resulting in structures significantly different from and more diverse than previous models ([Nature Physics 2021, DOI: 10.1038/s41567-021-01417-7]). Despite its degree preserving property, the DPG model is able ...

The uniform sampling of simple graphs matching a prescribed degree sequence is an important tool in network science, e.g. to construct graph generators or null-models. Here, the Edge Switching Markov Chain (ES-MC) is a common choice. Given an arbitrary simple graph with the required degree sequence, ES-MC carries out a large number of small changes, called edge switches, to eventually obtain a uniform sample. In practice, reasonably short runs efficiently yield approximate un...

For random systems subject to a constraint, the microcanonical ensemble requires the constraint to be met by every realisation ("hard constraint"), while the canonical ensemble requires the constraint to be met only on average ("soft constraint"). It is known that for random graphs subject to topological constraints breaking of ensemble equivalence may occur when the size of the graph tends to infinity, signalled by a non-vanishing specific relative entropy of the two ensembl...

Markov chains are a class of probabilistic models that have achieved widespread application in the quantitative sciences. This is in part due to their versatility, but is compounded by the ease with which they can be probed analytically. This tutorial provides an in-depth introduction to Markov chains, and explores their connection to graphs and random walks. We utilize tools from linear algebra and graph theory to describe the transition matrices of different types of Markov...

In this paper we investigate the continuum limits of a class of Markov chains. The investigation of such limits is motivated by the desire to model very large networks. We show that under some conditions, a sequence of Markov chains converges in some sense to the solution of a partial differential equation. Based on such convergence we approximate Markov chains modeling networks with a large number of components by partial differential equations. While traditional Monte Carlo...

This paper describes a formalization of agent-based models (ABMs) as random walks on regular graphs and relates the symmetry group of those graphs to a coarse-graining of the ABM that is still Markovian. An ABM in which $N$ agents can be in $\delta$ different states leads to a Markov chain with $\delta^N$ states. In ABMs with a sequential update scheme by which one agent is chosen to update its state at a time, transitions are only allowed between system configurations that d...

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