Sequential algorithms for generating random graphs

Large-scale complex networks have been the objects of study for the past two decades, and one central problem have been constructing or designing realistic models for such networks. This problem appears in a variety of applications including coding theory and systems biology. Unfortunately, the existing algorithms for this problem have large running times, making them impractical to use for networks with millions of links. We will present a technique to design an almost linear time algorithm for generating random graphs with given degree sequences for a range of degrees. Next, we extend the analysis to design an algorithm for efficiently generating random graphs without short cycles. These algorithms can be used for constructing high performance low-density parity-check codes (LDPC codes). Based on joint works with Jeong Han Kim, Andrea Montanari, and Amin Saberi.