Analyzing Private Network Data

Wednesday November 17, 2010, 4:00 pm in MCS 135

Speaker: Gerome Miklau, University of Massachusetts, Amherst

Abstract: Social and communication networks are formed by entities (such as individuals or computer hosts) and their connections (which may be contacts, relationships, or flows of information).  Such networks are analyzed to understand the influence of individuals in organizations, the transmission of disease in communities, the operation of computer networks, among many other topics.  While network data can now be recorded at unprecedented scale, releasing it can result in unacceptable disclosures about participants and their relationships.  As a result, privacy concerns are severely constraining the dissemination of network data and disrupting the emerging field of network science.

In this talk I will give an overview of recent approaches to protecting network data, including both network anonymization and the application of differential privacy to networks.  To satisfy differential privacy, statistics about the topology of a sensitive network are perturbed before being released.  I will show that the degree distribution of a network can be very accurately estimated by a novel technique in which constraints are applied to the noisy output to improve utility.  Other network properties, such as motif analysis, appear to be fundamentally harder to estimate under the same privacy standards.  I will conclude by discussing the prospects for synthesizing accurate network data from privately-learned statistics.

Short Bio: Gerome Miklau is an Assistant Professor at the University of Massachusetts, Amherst.  His primary research interest is the secure management of large-scale data.  This includes evaluating threats to privacy in published data; devising techniques for the safe publication of social networks, network traces, and audit logs; designing database management systems to implement security policies; and theoretically analyzing information disclosure.  He received the 2006 ACM SIGMOD Dissertation Award, an NSF CAREER Award in 2007, and an ICDM Best Student Paper Award in 2009.  He received his Ph.D. in Computer Science from the University of Washington in 2005.

Host: Evimaria Terzi