Sampling for Statistical Inference on Network Data

网络结构出现在各种科学和工程系统的建模中。网络模型中最重要的一类是随机图。本课题的目标是研究网络分析中的两个具有挑战性的问题：一个是对给定度序列的随机图进行采样，另一个是对网络中的结构进行检测。对于第一个问题，提出了一种新的顺序采样方法，该方法从近似均匀分布的网络中采样。这些样本可以用来估计任何测试统计量的分布，并计算具有给定顶点度的网络的数量。对于第二个问题，提出了新的蒙特卡罗算法来检测网络结构，包括高连通子图和网络基元。研究者开发了创新的蒙特卡罗技术来模拟随机图和检测网络结构。这些方法可用于分析社会互动模式、识别网络基序、提取紧密连接的分子模块等等。识别网络结构在科学上具有重要意义，因为它们可能对应于一组同时相互作用的蛋白质或在生物调节网络中起关键作用的功能单元。这项研究为具有广泛背景和兴趣的学生提供了一个理想的参与机会。本研究开发的算法将被纳入相关课程。

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.