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

点击翻译按钮获取中文摘要

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.