Motivated by tensions between data privacy for individual citizens, and societal priorities such as counterterrorism, we introduce a computational model that distinguishes between parties for whom privacy is explicitly protected, and those for whom it is not (the “targeted” subpopulation). Within this framework, we provide provably privacy-preserving algorithms for targeted search in social networks. We validate the utility of our algorithms with extensive computational experiments on two large-scale social network datasets.

This is a joint work with Michael Kearns, Aaron Roth and Grigory Yaroslavtsev, which appeared in PNAS this year. (http://www.pnas.org/content/113/4/913.abstract)