Are We There Yet? When to Stop a Markov Chain while Generating Random Graphs
From MaRDI portal
Publication:2900593
DOI10.1007/978-3-642-30541-2_12zbMATH Open1342.05144arXiv1202.3473OpenAlexW2117863112MaRDI QIDQ2900593FDOQ2900593
Authors: Jaideep Ray, Ali Pinar, C. Seshadhri 
Publication date: 23 July 2012
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Abstract: Markov chains are a convenient means of generating realizations of networks, since they require little more than a procedure for rewiring edges. If a rewiring procedure exists for generating new graphs with specified statistical properties, then a Markov chain sampler can generate an ensemble of graphs with prescribed characteristics. However, successive graphs in a Markov chain cannot be used when one desires independent draws from the distribution of graphs; the realizations are correlated. Consequently, one runs a Markov chain for N iterations before accepting the realization as an independent sample. In this work, we devise two methods for calculating N. They are both based on the binary "time-series" denoting the occurrence/non-occurrence of edge (u, v) between vertices u and v in the Markov chain of graphs generated by the sampler. They differ in their underlying assumptions. We test them on the generation of graphs with a prescribed joint degree distribution. We find the N proportional |E|, where |E| is the number of edges in the graph. The two methods are compared by sampling on real, sparse graphs with 10^3 - 10^4 vertices.
Full work available at URL: https://arxiv.org/abs/1202.3473
Recommendations
- A stopping criterion for Markov chains when generating independent random graphs
- A Markov chain approach to randomly grown graphs
- How to Get a Perfectly Random Sample from a Generic Markov Chain and Generate a Random Spanning Tree of a Directed Graph
- Sampling graphs with a prescribed joint degree distribution using Markov chains
- Stopping Markov processes and first path on graphs
- Controlled Markovian dynamics of graphs: unbiased generation of random graphs with prescribed topological properties
- Constrained Markovian dynamics of random graphs
- Graph-combinatorial approach for large deviations of Markov chains
- A graph-algorithmic approach for the study of metastability in Markov chains
- Monte Carlo Markov chains constrained on graphs for a target with disconnected support
Random graphs (graph-theoretic aspects) (05C80) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10)
Cites Work
- Inference from iterative simulation using multiple sequences
- Discrete Multivariate Analysis Theory and Practice
- Emergence of Scaling in Random Networks
- Title not available (Why is that?)
- A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.
- Collective dynamics of `small-world' networks
- Fast uniform generation of regular graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Are We There Yet? When to Stop a Markov Chain while Generating Random Graphs
- Sampling graphs with a prescribed joint degree distribution using Markov chains
Cited In (7)
- Are We There Yet? When to Stop a Markov Chain while Generating Random Graphs
- I/O-efficient generation of massive graphs following the \textit{LFR} benchmark
- Constrained Markovian dynamics of random graphs
- A stopping criterion for Markov chains when generating independent random graphs
- Parallel and I/O-efficient randomisation of massive networks using global curveball trades
- Controlled Markovian dynamics of graphs: unbiased generation of random graphs with prescribed topological properties
- Fast sequential creation of random realizations of degree sequences
This page was built for publication: Are We There Yet? When to Stop a Markov Chain while Generating Random Graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2900593)
