Network structures arise in modeling a wide variety of systems in sciences and engineering. One of the most important classes of network models is random graphs. The goal of this project is to study two challenging problems in network analysis: one is on sampling random graphs with a given degree sequence, and the other is on detecting structures in networks. For the first problem, a new sequential sampling method is proposed which samples the networks from an approximate uniform distribution. These samples can be used to estimate the distribution of any test statistic and count the number of networks with given vertex degrees. For the second problem, new Monte Carlo algorithms are proposed to detect network structures, including highly connected subgraphs and network motifs.
The investigator develops innovative Monte Carlo techniques for simulating random graphs and detecting network structures. These methods can be used to analyze social interaction patterns, identify network motifs, extract densely connected molecular modules, and much more. Identifying network structures are scientifically important because they may correspond to a group of proteins that interact with each other at the same time or a functional unit that plays a key role in biological regulation networks. The research provides an ideal opportunity for involvement of students with a broad range of background and interests. The algorithms developed from this research will be incorporated into relevant courses.
