Inference of Network Structure from Grouped Data

Arizona State University, Scottsdale AZ

Investigators

Abstract

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.