2008/11/18 by Mohsen Bayati, Andrea Montanari, Bayati, Mohsen +3
Computer Science · Mathematics · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Information Theory (cs.IT) #cs.DS #cs.IT #math.IT
paper · pdf · doi:10.48550/arxiv.0811.2853
36 pages, 1 figure, accepted to Operations Research
arxiv created 2017/12/29 · arxiv updated 2018/01/01
Random graph generation is an important tool for studying large complex networks. Despite abundance of random graph models, constructing models with application-driven constraints is poorly understood. In order to advance state-of-the-art in this area, we focus on random graphs without short cycles as a stylized family of graphs, and propose the RandGraph algorithm for randomly generating them. For any constant k, when m=O(n1+1/[2k(k+3)]), RandGraph generates an asymptotically uniform random graph with n vertices, m edges, and no cycle of length at most k using O(n2m) operations. We also characterize the approximation error for finite values of n. To the best of our knowledge, this is the first polynomial-time algorithm for the problem. RandGraph works by sequentially adding m edges to an empty graph with n vertices. Recently, such sequential algorithms have been successful for random sampling problems. Our main contributions to this line of research includes introducing a new approach for sequentially approximating edge-specific probabilities at each step of the algorithm, and providing a new method for analyzing such algorithms.