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

DOI10.1007/978-1-4614-9161-3_4zbMATH Open1332.60111arXiv1203.0877OpenAlexW1489134469WikidataQ106951547 ScholiaQ106951547MaRDI QIDQ5259681FDOQ5259681

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)

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

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

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

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)

Cited In (3)

• Are We There Yet? When to Stop a Markov Chain while Generating Random Graphs
• Controlled Random Fields on an Oriented Graph
• Constrained Markovian dynamics of 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)