AitF: Spectral Methods in the Field: New Tools for Discovering Latent Structure in Societal-Scale Data

移动电话、社交媒体和数字传感器的使用迅速增加，为观察和了解世界各地迅速变化的人口结构创造了机会。特别是，在这些人口规模的数字网络上捕获的数据可以为与政策相关的问题提供信息，这些问题涉及世界各地社会的演变性质。例如，政策制定者想知道特殊的暴力如何影响当地社区的复原力，外国军队的存在如何改变当地的互动模式，以及大风和自然灾害如何影响国家团结的感觉。不幸的是，不存在适当的模型和算法来理解不断演变的社会规模的数据。该项目将开发可扩展的算法，以帮助理解现实世界中联网的传感器数据，并有可能在日益互联的全球社会产生重大影响。该项目的技术重点是使理论计算机科学和机器学习文献中的最新算法进步适应现实世界、社会规模的网络数据。这种方法将利用光谱方法的最新进展，这些方法提供了被证明有效的算法来估计数据中的隐藏结构，并在三个重要方面改进了最新技术。第一个目标是将当前的光谱模型调整和扩展到具有数百万个相互关联的参与者的真实世界数据集，这些参与者具有具有重尾度分布的加权和定向边。第二个目标是将现有方法转化为动态机制，以解决真实世界数据的非平稳性质。第三个目标是描述这些模型所能达到的计算和统计极限。通过这项研究开发的算法和工具将通过GitHub和BitBucket等开放源码库提供给更广泛的学术界。

The rapid rise in the use of mobile phones, social media, and digital sensors has created opportunities to observe and understand the rapidly changing structure of populations around the world. In particular, the data captured on these population-scale digital networks can inform policy-relevant questions about the evolving nature of societies around the world. For example, policymakers would like to know how idiosyncratic violence impacts the resilience of local communities, how the presence of foreign troops changes local patterns of interaction, and how draughts and natural disasters affect feelings of national solidarity. Unfortunately, appropriate models and algorithms do not exist to make sense of evolving, societal-scale data. This project will develop scalable algorithms to help make sense of real-world networked sensor data, with the potential for significant impact in the increasingly connected global society. The technical focus of this project is on adapting recent algorithmic advances in the theoretical computer science and machine learning literatures to real-world, societal-scale network data. This approach will leverage recent advances in spectral methods, which provide provably efficient algorithms for estimating hidden structure in data and improve upon the state of the art in three important ways. The first objective is to adapt and scale current spectral models to real-world datasets with millions of interconnected actors, which have weighted and directed edges with heavy-tailed degree distributions. The second goal is to translate existing methods to dynamic regime, to address the non-stationary nature of real-world data. The third goal is to characterize the computational and statistical limits of what can be achieved with these models. The algorithms and tools developed through this research will be made available to the broader academic community via open source code repositories such as GitHub and BitBucket.