Abstract
Many applications in graph analysis require a space of graphs or networks to be sampled uniformly at random. For example, one may need to efficiently draw a small representative sample of graphs from a particular large target space. We assume that a uniform distribution f(N,E)=1/|X| has been defined, where N is a set of nodes, E is a set of edges, (N, E) is a graph in the target space X and |X| is the (finite) total number of graphs in the target space. We propose a new approach to sample graphs at random from such a distribution. The new approach uses a Markov chain Monte Carlo method called the Neighbourhood Sampler. We validate the new sampling technique by simulating from feasible spaces of directed or undirected graphs, and compare its computational efficiency with the conventional Metropolis-Hastings Sampler. The simulation results indicate efficient uniform sampling of the target spaces, and more rapid rate of convergence than Metropolis-Hastings Sampler.
Original language | English |
---|---|
Title of host publication | International Conference on Graph Theory and its Applications |
Editors | Andreas Hinz, S. Arumugam, R. Balakrishnan, Francis Raj, T. Karthick, K. Somasundaram, Xuding Zhu |
Publisher | Elsevier |
Pages | 43-55 |
Number of pages | 13 |
DOIs | |
Publication status | Published - 1 Sep 2016 |
Event | International Conference on Graph Theory and its Applications 2015 - Amrita School of Engineering, Amrita Vishwa Vidyapeetham, Coimbatore, India Duration: 16 Dec 2015 → 19 Dec 2015 https://www.amrita.edu/site/icgta15/ |
Publication series
Name | Electronic Notes in Discrete Mathematics |
---|---|
Publisher | Elsevier |
Volume | 53 |
ISSN (Print) | 1571-0653 |
Conference
Conference | International Conference on Graph Theory and its Applications 2015 |
---|---|
Abbreviated title | ICGTA-15 |
Country | India |
City | Coimbatore |
Period | 16/12/15 → 19/12/15 |
Internet address |
Keywords
- Bayesian networks
- Markov chain Monte Carlo
- Sampling graph space