Uniform sampling of directed and undirected graphs conditional on vertex connectivity

Salem A. Alyami, A. K. M. Azad, Jonathan M. Keith

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

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 languageEnglish
Title of host publicationInternational Conference on Graph Theory and its Applications
EditorsAndreas Hinz, S. Arumugam, R. Balakrishnan, Francis Raj, T. Karthick, K. Somasundaram, Xuding Zhu
PublisherElsevier
Pages43-55
Number of pages13
DOIs
Publication statusPublished - 1 Sep 2016
EventInternational Conference on Graph Theory and its Applications 2015 - Amrita School of Engineering, Amrita Vishwa Vidyapeetham, Coimbatore, India
Duration: 16 Dec 201519 Dec 2015
https://www.amrita.edu/site/icgta15/

Publication series

NameElectronic Notes in Discrete Mathematics
PublisherElsevier
Volume53
ISSN (Print)1571-0653

Conference

ConferenceInternational Conference on Graph Theory and its Applications 2015
Abbreviated titleICGTA-15
CountryIndia
CityCoimbatore
Period16/12/1519/12/15
Internet address

Keywords

  • Bayesian networks
  • Markov chain Monte Carlo
  • Sampling graph space

Cite this

Alyami, S. A., Azad, A. K. M., & Keith, J. M. (2016). Uniform sampling of directed and undirected graphs conditional on vertex connectivity. In A. Hinz, S. Arumugam, R. Balakrishnan, F. Raj, T. Karthick, K. Somasundaram, & X. Zhu (Eds.), International Conference on Graph Theory and its Applications (pp. 43-55). (Electronic Notes in Discrete Mathematics; Vol. 53). Elsevier. https://doi.org/10.1016/j.endm.2016.05.005