[NRG] Davide Proserpio NRG talk on Monday 11am

Sharon Goldberg goldbe at cs.bu.edu
Wed Feb 22 17:08:37 EST 2012


Davide and I are looking forward to getting your feedback on our
work-in-progress at the NRG meeting on Monday 11am.  Resending
abstract below :)

See you there,


Title: "Differential Private measurement on graph topologies"
Authors: Davide Proserpio, Sharon Goldberg and Frank McSherry

We study the problem of differentially-private publication of graph
topologies. Our investigation proceeds through several interesting
intermediate results. We first generalize differential privacy to
computations run on weighted sets. This leads us to generalize the
PINQ programming language, enriching the space of
differentially-private analyses that can be easily described. This
generalized language admits analogues of many graph computations (such
as joint degree distribution) that previously suffered from poor
differentially private implementations.  Combining the weighted
measurements with an incremental evaluator (Markov Chain Monte Carlo
-MCMC) we are able to synthesize graphs where the statistic of
interest (e.g. assortativity) aligns with those of the protected
input, despite our inability to measure the properties directly.

In the talk I will focus on the process of synthetic graph generation.
I show how the generalized PINQ language can be used to produce
differentially-private measures of properties like degree
complementary cumulative distribution function (CCDF), and degree
sequence, and show how to combine these measurements with MCMC to
create a synthetic graph.

Sharon Goldberg
Computer Science, Boston University

More information about the NRG-L mailing list