TIME: 1:30-2:20 pm, May 30, 2006 PLACE: CSE 403 TITLE: Sequential Algorithm for Generating Random Graphs SPEAKER: Mohsen Bayati Stanford University ABSTRACT: Random generation of graphs has been a well-known theoretical problem in computer science for more than two decades. Recently it has also attracted a lot of attention for modeling real world networks such as World Wide Web, biological networks, peer-to-peer and social networks. In particular, random graph generation is an important tool for detecting certain motifs in biological networks and for simulating Internet topology. Unfortunately, there is a big gap between theory and practice for this problem. When the degree sequence is non-regular, there is no efficient algorithms known for random graph generation. The MCMC-based algorithms have a very large running time, which makes them very difficult to use for real-world applications. On the other hand, there is no rigorous analysis of the simple heuristics used in practice. In fact, it is known that some of these heuristics are incorrect. We give the first practical algorithm for sampling uniformly from the set of all simple graphs with given degrees $d_1,...,d_n$. Suppose $\sum_{i=1}^n d_i = 2m$. We will show that when the maximum degree $d$ is of $o(m^{1/4})$ our algorithm finds an asymptotically uniform sample with a running time of $O(md)$. Joint work with Amin Saberi.