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.