Controlled Markovian dynamics of graphs: unbiased generation of random graphs with prescribed topological properties
arXiv:1203.0877
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).
arXiv comment4 pages, 1 figure, contribution to the conference NOMA11 (Evora), to be published in Springer Proceedings in Mathematics and Statistics
References in corpus (5)
- Random graphs with arbitrary degree distributions and their applications
- Constrained Markovian dynamics of random graphs
- Bias in generation of random graphs
- Spin models on random graphs with controlled topologies beyond degree constraints
- A study of the edge-switching Markov-chain method for the generation of random graphs