N-Body Algorithms for Mobile and Social Data

Description

Today’s fast-growing mobile device and online social media infrastructure is producing an unprecedented volume of data on communication, system and device-level interaction, and user behavior. Examples include cellphone data (including voice calls, SMS and Internet data, cellular signal strength) and activity on online social media (itself often sent from mobile devices). This presents both opportunities and challenges. On one hand, the increasing availability, high quality, and relatively easy collection of such data provides a way to better understand online human activity, infer activity patterns, and design new services in urban environments. On the other hand, the combination of big data and powerful inferential techniques pose both computational challenges and privacy concerns. In both cases, there is a need for efficient algorithmic techniques that can support learning from mobile and social data sets, and that enable principled creation of synthetic data at similar scale for modeling, testing and anonymization purposes.

Our project is based on the core insight that many problems in the above space can be framed in terms of pairwise interactions among spatially embedded entities, traditionally the domain of N-body problems in the physical sciences. As a consequence, revisiting and adapting N-body algorithms specifically to mobile and social data analysis and learning can increase our capacity to (i) work with such data at scale and (ii) do so in a privacy-preserving way. We investigate novel N-body and parallel algorithms, specifically designed for processing hierarchical, and geospatially embedded, mobile and social data, where the size or access to datasets is prohibitive. In addition to the algorithmic design, we develop software modules (e.g., special purpose compilers, crowdsourcing tools and generators of synthetic datasets) that implement these methods.

Application domains include: cellular network monitoring, mobile data privacy, social network modeling, statistical network analysis, web analysis, scalability and performance analysis of mobile devices.

Team

PI: Athina Markopoulou, EECS Dept.
Co-PI: Carter T. Butts, Dept. of Sociology
Co-PI: Aparna Chandramowlishwaran, EECS Dept
Behnam Pourghassemi, PhD student in EECS
Zixiao Zong, PhD student in Networked Systems

Past Members

Emmanouil Alimpertis, PhD in Networked Systems, June 2020; currently with Apple, Cupertino, CA.
Justin Ley, undergraduate student; currently with Google.
Loring Tomas, PhD student in Sociology.

Publications

E. Alimpertis, A. Markopoulou, C.T. Butts, E.Bakopoulou, K. Psounis, “A Unified Prediction Framework for Signal Maps”, to appear in IEEE Transactions on Mobile Computing, Oct. 2022; earlier version on arxiv.org/abs/2202.03679, Feb 2022
Zixiao Zong, Mengwei Yang, Justin Ley, Carter T. Butts, Athina Markopoulou, “Privacy by Projection: Federated Population Density Estimation by Projecting on Random Features“, to appear in Proceedings on Privacy Enhancing Technologies (PoPETs), 2023(1); and to be presented in PETS 2023 in Lausanne, Switzerland.
Loring J. Thomas; Peng Huang; Fan Yin; Xiaoshuang Iris Luo,; Zack W. Almquist; John R. Hipp; Carter T. Butts, “Spatial heterogeneity can lead to substantial local variations in COVID-19 timing and severity“, in the Proc. of National Academy of Sciences (PNAS), September 29, 2020, Vol. 117 (39), 24180-24187. [simulation code]
Pourghassemi, Behnam; Bonecutter, Jordan; Li, Zhou; and Chandramowlishwaran, Aparna “adPerf: Characterizing the Performance of Tihrd-party Ads”, in the Proceedings of the ACM on Measurement and Analysis of Computing Systems, Vol. 5, No. 1, Article 3, March 2021 [open-source software]
Butts, Carter T. (2020). “A dynamic process reference model for sparse networks with reciprocity”, in Journal of Mathematical Sociology. 1 to 27. 10.1080/0022250X.2020.1795652.
Pourghassemi, Behnam, Ardalan Amiri Sani, and Aparna Chandramowlishwaran, “Only Relative Speed Matters: Virtual Causal Profiling“, ACM SIGMETRICS Performance Evaluation Review, Vol. 48 (3), December 2020, pp. 113–119.
Thomas, Loring J.; Huang, Peng; Yin, Fan; Iris Luo Xiaoshuang; Almquist, Zack W.; Hipp, John R.; and Butts, Carter T. “Spatial Heterogeneity Can Lead to Substantial Local Variations in COVID-19 Timing and Severity”. arXiv:2005.09850, May 2020
Alimpertis, Emmanouil, “Mobile Coverage Map Prediction“, PhD Thesis, UC Irvine, May 2020.

Software & DataSets

Acknowledgements: This material is based upon work supported by the National Science Foundation under Grant No. 1939237: EAGER: N-Body Algorithms for Mobile and Social Data, Sept.1, 2019-Aug. 31, 2021 (or extended to Aug. 2022).

Disclaimer: Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.

Point of Contact: please contact the PI, A. Markopoulou.

Last Updated: Aug. 12th, 2021