Privacy-Preserving Inference of Social Relationships from Location Data

Cyrus Shahabi

The following Great Innovative Idea is from Cyrus Shahabi, Liyue Fan, and Luciano Nocera from the University of Southern California, Li Xiong from Emory University, and Ming Li from University of Arizona. Their Privacy-Preserving Inference of Social Relationships from Location Data paper was one of the winners at the Computing Community Consortium (CCC) sponsored Blue Sky Ideas Track Competition at the ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems 2015 (SIGSPATIAL 2015) in Seattle, Washington.

The Innovative Idea

Social relationships between people, e.g., whether they are friends with each other, can be inferred by observing their behaviors in the real world. Thanks to the popularity of GPS-enabled mobile devices or online services, a large amount of high-resolution location data becomes available for such inference studies. However, due to the sensitivity of location data and user privacy concerns, those studies cannot be largely carried out on individually contributed data without privacy guarantees. Furthermore, we observe that the actual location may not be needed for social relationship studies, but rather the fact that two people met and some statistical properties about their meeting locations, which can be computed in a private manner.

Towards this end, we envision an extensible framework dubbed Privacy-Preserving Location Analytics and Computation Environment (Private-PLACE), which enables social relationship studies by analyzing individually generated location data. Private-PLACE utilizes an untrusted server and computes several building blocks to support various social relationship studies, without disclosing location information to the server and other untrusted parties. We proposed Private-PLACE with three example social relationship use cases, which utilize four privacy-preserving building blocks with encryption and differential privacy primitives.

Impact

The successful realization of Private-PLACE will facilitate private location data acquisition from individual devices, thanks to the strong privacy guarantees, and will enable a wide range of applications. Our use cases enable many applications such as Reachability in epidemiology to study the spread of diseases through human contacts, Social-Strength in criminology to identify the new or unknown members of a criminal gang or a terrorist cell, and Spatial-Influence in policy to induce local influence in electing a tribal representative.

Other Research

My research is in the general area of information management and databases. My most relevant research to this effort includes my work in the field of geospatial information management. Under this area, I have studied several subareas, notably: spatial indexing, geospatial information integration, transportation data management, location privacy, spatial crowdsourcing, and most recently geo-social networks. In the area of geo-social networks, I have studied the inference of three specific types of social relationships from location data: reachability, social relationship and social influence. These three studies are the basis of the three use cases that will be enabled by Private-PLACE. Moreover, my work in location privacy is relevant to the design and development of the privacy-preserving building blocks of Private-PLACE.

Researcher’s Background

I am a Professor of Computer Science and Electrical Engineering and the Director of the NSF’s Integrated Media Systems Center (IMSC) at the University of Southern California (USC). I am also the director of the Informatics Program at USC’s Viterbi School of Engineering. I received my B.S. in Computer Engineering from Sharif University in 1989 and then my M.S. and Ph.D. Degrees in Computer Science from USC in May 1993 and August 1996, respectively.

I am a fellow of IEEE, and a recipient of the ACM Distinguished Scientist award in 2009, the 2003 U.S. Presidential Early Career Awards for Scientists and Engineers (PECASE), and the NSF CAREER award in 2002.