Controlled Markovian dynamics of graphs: unbiased generation of random graphs with prescribed topological properties

DOI10.1007/978-1-4614-9161-3_4MaRDI QIDQ5259681zbMATH OpenOpenAlexWikidataFDO

Authors Eric S. Roberts, A. Annibale, A. C. C. Coolen

Publication date 29 June 2015

Published in Springer Proceedings in Mathematics & Statistics (Search for Journal in Brave)

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

zbMATH Keywords

adjacency matrixrandom graphsdegree-preserving Markov chains

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10)

Abstract: We analyze the properties of degree-preserving Markov chains based on elementary edge switchings in undirected and directed graphs. We give exact yet simple formulas for the mobility of a graph (the number of possible moves) in terms of its adjacency matrix. 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).

Recommendations

• Constrained Markovian dynamics of random graphs
• Are We There Yet? When to Stop a Markov Chain while Generating Random Graphs
• Random graph generation using multiple switches of edges
• The switch Markov chain for sampling irregular graphs and digraphs
• Efficient and simple generation of random simple connected graphs with prescribed degree sequence

Cited in

(6)

• Are We There Yet? When to Stop a Markov Chain while Generating Random Graphs
• Random graph generation using multiple switches of edges
• Generating constrained random graphs using multiple edge switches
• Controlled Random Fields on an Oriented Graph
• Constrained Markovian dynamics of random graphs
• A stopping criterion for Markov chains when generating independent random graphs

This page was built for publication: Controlled Markovian dynamics of graphs: unbiased generation of random graphs with prescribed topological properties

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