Constrained Markovian dynamics of random graphs

Abstract

We introduce a statistical mechanics formalism for the study of constrained graph evolution as a Markovian stochastic process, in analogy with that available for spin systems, deriving its basic properties and highlighting the role of the `mobility' (the number of allowed moves for any given graph). As an application of the general theory we analyze the properties of degree-preserving Markov chains based on elementary edge switchings. We give an exact yet simple formula for the mobility in terms of the graph's adjacency matrix and its spectrum. This formula allows us to define acceptance probabilities for edge switchings, such that the Markov chains become controlled Glauber-type detailed balance processes, designed to evolve to any required invariant measure (representing the asymptotic frequencies with which the allowed graphs are visited during the process). As a corollary we also derive a condition in terms of simple degree statistics, sufficient to guarantee that, in the limit where the number of nodes diverges, even for state-independent acceptance probabilities of proposed moves the invariant measure of the process will be uniform. We test our theory on synthetic graphs and on realistic larger graphs as studied in cellular biology.

28 pages, 6 figures

References in corpus (11)

• Analysis of weighted networks
• Critical phenomena in complex networks
• Generation of uncorrelated random scale-free networks
• On the uniform generation of random graphs with prescribed degree sequences
• The entropy of network ensembles
• Generalized percolation in random directed networks
• Tuning clustering in random networks with arbitrary degree distributions
• Diffusion-annihilation processes in complex networks
• Entropies of complex networks with hierarchically constrained topologies
• Spin models on random graphs with controlled topologies beyond degree constraints
• Link and subgraph likelihoods in random undirected networks with fixed and partially fixed degree sequence

Cited by in corpus (30)

• The Statistical Physics of Real-World Networks
• The Physics of Financial Networks
• Quantifying randomness in real networks
• Entropy of stochastic blockmodel ensembles
• Unbiased sampling of network ensembles
• Fast and scalable likelihood maximization for Exponential Random Graph Models with local constraints
• Tailored graph ensembles as proxies or null models for real networks I: tools for quantifying structure
• Network community detection using modularity density measures
• Entropy distribution and condensation in random networks with a given degree distribution
• Reconstructing networks
• Linear stability analysis for large dynamical systems on directed random graphs
• Competing endogenous RNA crosstalk at system level
• Are crossing dependencies really scarce?
• Bias in generation of random graphs
• Duality between equilibrium and growing networks
• Percolation and the effective structure of complex networks
• Pattern detection in bipartite networks: a review of terminology, applications and methods
• Tailored graph ensembles as proxies or null models for real networks II: results on directed graphs
• Replica methods for loopy sparse random graphs
• The role of adjacency matrix degeneration in maximum entropy weighted network models
• Imaginary replica analysis of loopy regular random graphs
• Exactly Solvable Random Graph Ensemble with Extensively Many Short Cycles
• Entropy-based models to randomize real-world hypergraphs
• Generating random networks that consist of a single connected component with a given degree distribution
• Volume of the steady-state space of financial flows in a monetary stock-flow-consistent model
• Large deviation and anomalous fluctuations scaling in degree assortativity on configuration networks
• Randomisation Algorithms for Large Sparse Matrices
• Controlled Markovian dynamics of graphs: unbiased generation of random graphs with prescribed topological properties
• Generating constrained random graphs using multiple edge switches
• Entropy of random graph ensembles constrained with generalised degrees