Uniform Sampling of Directed and Undirected Graphs Conditional on Vertex Connectivity

• Published in: Electronic notes in discrete mathematics 2016-09, Vol.53, p.43-55
• Main Authors: Alyami, Salem A., Azad, A.K.M., Keith, Jonathan M.
• Format: Article
• Language: English
• Subjects: Bayesian networks; Markov chain Monte Carlo; Sampling graph space
• ISSN: 1571-0653; 1571-0653
• DOI: 10.1016/j.endm.2016.05.005

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.