Constrained Markovian dynamics of random graphs

DOI10.1007/S10955-009-9821-2MaRDI QIDQ1040719zbMATH OpenOpenAlexWikidataFDO

Authors J. Blot

Publication date 25 November 2009

Published in Journal of Statistical Physics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0905.4155

zbMATH Keywords

graph theorystochastic processesedge switching

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Random walks, random surfaces, lattice animals, etc. in equilibrium statistical mechanics (82B41) Continuous-time Markov processes on discrete state spaces (60J27) Stochastic methods applied to problems in equilibrium statistical mechanics (82B31)

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.

Recommendations

• Controlled Markovian dynamics of graphs: unbiased generation of random graphs with prescribed topological properties
• Are We There Yet? When to Stop a Markov Chain while Generating Random Graphs
• New classes of degree sequences with fast mixing swap Markov chain sampling
• Generating constrained random graphs using multiple edge switches
• A Markov chain approach to randomly grown graphs

Cites work

• scientific article; zbMATH DE number 3806623 (Why is no real title available?)
• scientific article; zbMATH DE number 1866312 (Why is no real title available?)
• A critical point for random graphs with a given degree sequence
• An efficient MCMC algorithm to sample binary matrices with fixed marginals
• Computing and Combinatorics
• Sequential Monte Carlo Methods for Statistical Analysis of Tables
• Spin models on random graphs with controlled topologies beyond degree constraints
• Statistical mechanics of complex networks
• The Structure and Function of Complex Networks
• The asymptotic number of labeled graphs with given degree sequences
• The average distances in random graphs with given expected degrees
• The rise and fall of a networked society: A formal model

Cited in

(21)

• Exactly solvable random graph ensemble with extensively many short cycles
• Are We There Yet? When to Stop a Markov Chain while Generating Random Graphs
• Constrained minimum passage time in random geometric graphs
• Large deviation and anomalous fluctuations scaling in degree assortativity on configuration networks
• Controlled Markovian dynamics of graphs: unbiased generation of random graphs with prescribed topological properties
• Generating constrained random graphs using multiple edge switches
• Volume of the steady-state space of financial flows in a monetary stock-flow-consistent model
• scientific article; zbMATH DE number 2019625 (Why is no real title available?)
• A Markov chain approach to randomly grown graphs
• Network community detection using modularity density measures
• Evolution of random graph processes with degree constraints
• scientific article; zbMATH DE number 5631492 (Why is no real title available?)
• Unbiased sampling of network ensembles
• A graph-algorithmic approach for the study of metastability in Markov chains
• Tracking a Markov-Modulated Stationary Degree Distribution of a Dynamic Random Graph
• Conformal graph directed Markov systems: beyond finite irreducibility
• Imaginary replica analysis of loopy regular random graphs
• Are crossing dependencies really scarce?
• scientific article; zbMATH DE number 2151251 (Why is no real title available?)
• scientific article; zbMATH DE number 5485245 (Why is no real title available?)
• Monte Carlo Markov chains constrained on graphs for a target with disconnected support

This page was built for publication: Constrained Markovian dynamics of random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1040719)