Inference of Network Structure from Grouped Data

网络可以被看作是由链路(边)连接的节点(顶点)组成的数据结构，在各种科学和工程领域引起了广泛的关注。这些应用包括社会科学中的友谊和合作网络、生物学中的食物网和基因调控网络、经济学中的网络游戏、计算机科学中的互联网和万维网，以及许多其他应用。传统的统计网络分析侧重于对显式网络结构进行建模。对于物理网络，如电网，节点之间的链路定义良好，通常可以直接观察到。相比之下，在其他领域，特别是在社会科学和生物学领域，可能不会观察到明显的网络结构。在这些领域中，可用的原始数据通常是节点的行为，这通常被认为是潜在的网络结构的结果。本项目将研究从一种特殊的数据结构--分组数据中重建隐式网络的问题。这种数据的每一次观察都是一组个体，它们被观察到一起出现。该项目由三个部分组成，都涉及从分组数据进行网络推理的严格统计方法。第一部分主要研究具有连续边权的网络。PI考虑了星模型的两个有趣的性质--自稀疏性和可辨识性(最近由PI和他的博士生介绍)，并提出了L1正则化和低阶矩阵因式分解以降低该模型的复杂性。在第二部分中，考虑了具有二进制链的网络。PI建议研究两种不同的网络结构估计方法，包括基于Erdos-Renyi过程的全局模型和基于子图密度的非参数准则。在第三部分中，PI考虑了群体之间的依赖结构。这里假设马尔科夫性质，即在任何时间点产生的群只依赖于前一个时间点的群结构和潜在网络。PI在马尔可夫假设下提出了一个直观的进出模型。这个项目的贡献是双重的。首先，隐式网络的概念和分组数据网络推理的研究将改变统计网络分析的一些基本观点。其次，本项目中提出的严格的统计方法带来了新的具有挑战性的理论和计算问题，这将极大地促进该领域的理论理解和计算技术。

Networks, which can be viewed as data structures consisting of nodes (vertices) connected by links (edges), have drawn wide attention in a variety of scientific and engineering areas. The applications include friendship and collaboration networks in social sciences, food webs and gene regulatory networks in biology, network games in economics, the Internet and World Wide Web in computer science, as well as many others. Traditionally, statistical network analysis focuses on modeling explicit network structure. For physical networks, like power grids, links between nodes are well defined and can usually be directly observed. By contrast, explicit network structure may not be observable in other fields, especially in social sciences and biology. In these areas, the raw data available is usually behavior of nodes, which is generally presumed to be the result of latent network structure. This project will study the problem of reconstructing implicit networks from a special data structure--grouped data. Each observation of such data is a group of individuals which are observed to appear together. The project is composed of three parts, all concerning rigorous statistical methods for network inference from grouped data. The first part focuses on networks with continuous edge weights. The PI considers two intriguing properties -- self-sparsity and identifiability of Star Model (recently introduced by the PI and his PhD student), and proposes L1 regularization and low-rank matrix factorization in order to reduce the complexity of this model. In the second part, networks with binary links are considered. The PI proposes to study two different methods to estimate the network structures, including a global model based on Erdos-Renyi process and a non-parametric criterion based on subgraph densities. In the third part, the PI considers dependency structure among groups. The Markov property is assumed here, that is, a group generated at any time point only depends on the group structure at the previous time point and the latent network. The PI proposes an intuitive In-and-Out Model under the Markov assumption. The contribution of this project is twofold. Firstly, it is expected that the concept of implicit networks and the study of network inference from grouped data will change some fundamental viewpoints of statistical network analysis. Secondly, the rigorous statistical methods proposed in this project bring new challenging theoretical and computational questions, which will significantly advance the theoretical understanding and computational techniques in this area.