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


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
Number of pages13
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

Publication series

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


ConferenceInternational Conference on Graph Theory and Its Applications 2015
Abbreviated titleICGTA 2015
Internet address


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

Cite this