Sparse and structured networks: Statistical theory and algorithms

该提案的重点是马尔可夫随机场和有向图形模型，统计模型的基础上的一个marriagebetween图论和概率论，并允许灵活的网络结构数据建模类。 该提案的核心包括多个研究方向，所有这些都围绕着开发实用算法和理论的目标，用于网络结构数据的统计估计。 一个研究重点关注与无向图模型（也称为吉布斯分布或马尔可夫随机场）中的模型选择相关的变量。 问题包括确定在高维（顶点的数量可能大于样本大小）中图形模型选择的信息理论限制，而不仅仅是i.i.d.。数据，但也依赖数据;开发跟踪随时间演变的网络序列的方法;以及开发隐藏变量数据的方法。 另一个研究重点是与有向无环图结构（DAG）相关的各种数学问题，包括在高维环境中估计DAG的等价类;通过设计干预估计因果关系;以及使用Lasso和相关方法进行DAG选择的有效计算方法。 总体而言，拟议的研究是跨学科的性质，从数理统计，凸优化，信息论，浓度的措施，和图论的技术借鉴。科学和工程丰富的不同类型的网络。例子包括社交网络，如Facebook和Twitter，基因和蛋白质在分子生物学网络，网络模型的经济和市场动态，神经网络在大脑成像，流行病学中的疾病传播网络和执法中的信息网络。 在现实世界中，底层网络的结构是未知的，而是观察网络行为的样本（例如，计算机网络中的数据包计数;给定时间内的感染实例;流行病实例;一组人之间发送的电子邮件或文本消息），目标是推断网络结构。 解决这种网络推理问题的方法有着广泛的应用。 例子包括在神经影像学研究中推断大脑连接和疾病病因，检测社交网络中的恐怖分子细胞，监控计算机网络中的入侵，以及理解系统生物学中基因-蛋白质相互作用的基础。

The proposal focuses on Markov random fields and directed graphicalmodels, classes of statistical models that are based on a marriagebetween graph theory and probability theory, and allow for flexiblemodeling of network-structured data. The core of the proposalconsists of multiple research thrusts, all centered around the goal ofdeveloping practical algorithms and theory for statistical estimationwith network-structured data. One research thrust concerns variousissues associated with model selection in undirected graphical models,also known as Gibbs distributions or Markov random fields. Problemsinclude determining the information-theoretic limitations of graphicalmodel selection in high dimensions (where the number of vertices maybe larger than the sample size), not only for i.i.d. data but alsodependent data; developing methods for tracking sequences of networksthat evolve over time; and developing methods for data with hiddenvariables. Another research thrust concerns various statisticalproblems associated with directed acyclic graphical structures (DAGs),including estimating equivalence classes of DAGs in thehigh-dimensional setting; estimating causal relationships via designedinterventions; and efficient computational methods for DAG selectionusing the Lasso and related methods. Overall, the proposed researchis inter-disciplinary in nature, drawing on techniques frommathematical statistics, convex optimization, information theory,concentration of measure, and graph theory.Science and engineering abounds with different types of networks.Examples include social networks such as FaceBook and Twitter,networks of genes and proteins in molecular biology, network modelsfor economic and market dynamics, neural networks in brain imaging,networks of disease transmission in epidemiology, and informationnetworks in law enforcement. In the real-world, the structure of theunderlying network is not known, but instead one observes samples ofthe network behavior (e.g., packet counts in a computer network;instances of infection at given time instances of an epidemic; emailsor text messages sent among a group of people), and the goal is toinfer the network structure. Methods for solving this networkinference problem have a broad range of applications. Examplesinclude inferring brain connectivity and disease etiology inneuroimaging studies, detecting terrorist cells in social networks,monitoring intrusions in computer networks, and understanding thebasis of gene-protein interactions in systems biology.