CERIAS - Center for Education and Research in Information Assurance and Security

Skip Navigation
Purdue University - Discovery Park
Center for Education and Research in Information Assurance and Security

Safely Analyzing Sensitive Network Data

Gerome Miklau - University of Massachusetts, Amherst

Nov 18, 2009

Size: 477.3MB

Download: Video Icon MP4 Video  
Watch in your Browser   Watch on Youtube Watch on YouTube


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.

Our recent work investigates the properties of a network that can be accurately studied without threatening the privacy of individuals and their connections. We adopt the rigorous condition of differential privacy, and develop algorithms for releasing randomly perturbed statistics about the topology of a sensitive network. This talk will focus on two basic analysis tasks: the estimation of the degree distribution of a network and the study of small structural patterns that occur in a network (sometimes called motif analysis). We 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. This technique is of general interest, and can be used to boost the accuracy of differentially private output in other tasks as well. We show that studying motifs is fundamentally harder, but can be done with acceptable accuracy if the privacy condition is relaxed.

About the Speaker

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 an NSF CAREER Award in 2007 and won the 2006 ACM SIGMOD Dissertation Award. He received his Ph.D. in Computer Science from the University of Washington in 2005. He earned Bachelor's degrees in Mathematics and in Rhetoric from the University of California, Berkeley, in 1995.

Unless otherwise noted, the security seminar is held on Wednesdays at 4:30P.M. STEW G52, West Lafayette Campus. More information...


The views, opinions and assumptions expressed in these videos are those of the presenter and do not necessarily reflect the official policy or position of CERIAS or Purdue University. All content included in these videos, are the property of Purdue University, the presenter and/or the presenter’s organization, and protected by U.S. and international copyright laws. The collection, arrangement and assembly of all content in these videos and on the hosting website exclusive property of Purdue University. You may not copy, reproduce, distribute, publish, display, perform, modify, create derivative works, transmit, or in any other way exploit any part of copyrighted material without permission from CERIAS, Purdue University.