Next-generation random graph models

网络在现代世界中无处不在，社交网络和万维网就是众所周知的例子。了解网络的结构对于了解真实世界的现象、做出预测并帮助做出决策至关重要，例如，为破坏和瓦解恐怖分子网络、遏制传染病的传播和降低金融市场的系统性风险的战略提供参考。为了在面临不确定性的情况下帮助理解和预测这种现象，专业人员需要既复杂又可扩展的统计模型(即能够对广泛的网络特征进行建模并可应用于大型网络的模型)。现有的模型要么可伸缩但过于简单，要么复杂但不可伸缩。这项研究项目将开发出第一代既复杂又可扩展的模型。开发的模型和方法将在广泛的领域得到应用，包括国家安全(例如叛乱、恐怖主义)、公共卫生(例如传染病的传播)和金融(例如金融市场的系统性风险)。本研究项目将通过合并统计网络分析的两个最重要的流-随机区块模型和指数族随机图模型来开发既复杂又可扩展的下一代随机图模型，以期在保持两者优点的同时减少各自的缺点。随机区块模型是可扩展的，但过于简单，而指数族随机图模型是复杂的，但不可扩展。这里研究的下一代模型弥合了复杂性和可伸缩性之间的差距，并且既复杂又可伸缩。除了阐述下一代模型外，这项研究还将解决下一代模型提出的独特的计算和理论挑战。估计下一代模型的计算挑战将通过利用模型结构的优势，包括局部相关性和局部凸性，并通过利用大规模最小化-最大化方法来解决，该方法将高维优化问题分解为可以并行求解的低维优化问题。研究估计量性质的理论挑战将通过利用新的度量集中不等式来解决。度量不平等的集中将考虑到网络固有的依赖性以及估计器的不平稳性。

Networks are ubiquitous in the modern world, with social networks and the World Wide Web as well-known examples. Understanding the structure of networks is critical to understanding real-world phenomena, making predictions, and helping inform decisions on, for example, strategies to disrupt and dismantle terrorist networks, curb the spread of infectious diseases, and reduce systematic risk in financial markets. To help understand and predict such phenomena in the face of uncertainty, professionals need statistical models which are both complex and scalable (i.e., models which are capable of modeling a wide range of network characteristics and which can be applied to large networks). Existing models are either scalable but simplistic or complex but not scalable. This research project will develop the first generation of models which are both complex and scalable. The developed models and methods will have applications in a wide range of areas, including national security (e.g., insurgencies, terrorism), public health (e.g., the spread of infectious diseases), and finance (e.g., systematic risk in financial markets).This research project will develop the next generation of random graph models which are both complex and scalable by merging the two most important streams of statistical network analysis, stochastic block models and exponential-family random graph models, with a view to reducing the disadvantages of each while retaining the advantages of both. Stochastic block models are scalable but simplistic, whereas exponential-family random graph models are complex but not scalable. The next-generation models studied here bridge the gap between complexity and scalability and are both complex and scalable. In addition to elaborating next-generation models, this research will address the unique computational and theoretical challenges raised by next-generation models. The computational challenge of estimating next-generation models will be addressed by taking advantage of model structure, including local dependence and local convexity properties, and by exploiting massive-scale minorization-maximization methods which break down the high-dimensional optimization problem into low-dimensional ones that can solved in parallel. The theoretical challenge of studying the properties of estimators will be addressed by exploiting novel concentration of measure inequalities. The concentration of measure inequalities will take into account the dependence inherent in networks as well as the lack of smoothness of estimators.