Generating Random Networks Without Short Cycles

• 成果类型: Article
• 署名作者: Bayati, Mohsen; Montanari, Andrea; Saberi, Amin
• 署名单位: Stanford University; Stanford University; Stanford University; Stanford University; Stanford University; Stanford University
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2018.1730
• 发表日期: 2018
• 页码: 1227-1246
• 关键词: parity-check codes; EVOLUTION; graphs

摘要

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. To advance state-of-the-art in this area, we focus on random graphs without short cycles as a stylized family of graphs, and we propose the RandGraph algorithm for randomly generating them. For any constant k, when m = O(n(1+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(n(2)m) 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 include 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.