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.