Sampling methods for randon simple and bipartite graphs with prescribed degree sequences

Abstract

Complex networks have attracted considerable attention in recent years with the increase in the studies of real systems modeled by graphs such as biological and social networks. One problem in this domain is the generation of typical instances from a collection of graphs admitting certain properties, such as the degree sequence or the clustering coe cient. In this thesis, the sampling problem is addressed for simple and bipartite graphs with a given xed degree sequence. A natural Markov chain method relying on the edge switching steps is introduced for simple graphs. Due to the di culties of directly obtaining samples from the uniform distribution over the set of possible realizations of a given degree sequence, algorithms using importance sampling and sequential importance sampling techniques are investigated for simple and bipartite graphs. Here, we focus on algorithms proposed by Blitzstein and Diaconis [1] and Chen et al. [2]. A new uniform sampling and exact counting algorithm is proposed for simple graphs by adapting, and transforming the method suggested by Miller and Harrison [3] for bipartite graphs. Lastly, applications of the algorithms are illustrated in several examples such as hypothesis testing, network analysis and graph enumeration.