Rejection sampling of bipartite graphs with given degree sequence

Acta Universitatis Sapientiae. Matematica

K. K. Kayibi¹ 

关键词: degree sequence;    contraction of a degree sequence;    degree se-;    quence bipartition;    contraction of a graph;    deletion of a graph;    ecological occurrence matrix;   

DOI  :  10.2478/ausm-2018-0020

学科分类：社会科学、人文和艺术（综合）

来源: Editura Scientia / Scientia Publishing House

【 摘 要 】

Let A = (a1 ; a2 ; :::; an) be a degree sequence of a simplebipartite graph. We present an algorithm that takes A as input, andoutputs a simple bipartite realization of A, without stalling. The runningtime of the algorithm is (n1n2 ), where ni is the number of vertices inthe part i of the bipartite graph. Then we couple the generation algorithmwith a rejection sampling scheme to generate a simple realization of Auniformly at random. The best algorithm we know is the implicit one dueto Bayati, Kim and Saberi (2010) that has a running time of O(mamax),where m = 12Pni=1ai and amax is the maximum of the degrees, but doesnot sample uniformly. Similarly, the algorithm presented by Chen et al.(2005) does not sample uniformly, but nearly uniformly. The realizationof A output by our algorithm may be a start point for the edge-swappingMarkov Chains pioneered by Brualdi (1980) and Kannan et al.(1999).

【 授权许可】

Unknown