Generating Random Graphs without Short Cycles - Submitted 2013

Random graph generation is an important tool for studying large complex networks and recently has been extensively used by biologists, computer scientists, economists, electrical engineers, and mathematical sociologists. Despite many remarkable models for random graphs, unfortunately, the problem of efficiently generating random networks with application-driven constraints is poorly understood. In order to advance state of the art in this area we focus at generating random graphs without short cycles. This is an important problem in designing high performance codes that can approach Shannon capacity for transmitting a message over a noisy transmission channel. We present a simple and efficient algorithm for randomly generating simple graphs without small cycles. For any constant k, α ≤ 1/[2k(k + 3)] and m = O(n 1+α), our algorithm generates an asymptotically uniform random graph with n vertices, m edges, and no cycle of length k or smaller. To the best of our knowledge, this is the first polynomial-time algorithm for the problem. Our algorithm generates the graph by sequentially adding m edges to an empty graph with n vertices. Recently, such sequential methods have been successful for several counting and random generation problems [SW99, KV07, CDHL05, BD06, Bla09, BKS09]. Our main contribution is developing a new methodology for characterizing an inherent bias in sequential algorithms and obtain tighter concentration bounds.