Paper Info
Title
A workflow for differentially-private graph synthesis
Abstract
We present a new workflow for differentially-private publication of graph topologies. First, we produce differentially-private measurements of interesting graph statistics using our new version of the PINQ programming language, Weighted PINQ, which is based on a generalization of differential privacy to weighted sets. Next, we show how to generate graphs that fit any set of measured graph statistics, even if they are inconsistent (due to noise), or if they are only indirectly related to actual statistics that we want our synthetic graph to preserve. We combine the answers to Weighted PINQ queries with an incremental evaluator (Markov Chain Monte Carlo (MCMC)) to synthesize graphs where the statistic of interest aligns with that of the protected graph. This paper presents our preliminary results; we show how to cast a few graph statistics (degree distribution, edge multiplicity, joint degree distribution) as queries in Weighted PINQ, and then present experimental results synthesizing graphs generated from answers to these queries.
Year
DOI
Venue
2012
10.1145/2342549.2342553
Proceedings of the 2012 ACM workshop on Workshop on online social networks
Keywords
DocType
Volume
measured graph statistic,degree distribution,pinq programming language,protected graph,differentially-private graph synthesis,weighted pinq,interesting graph statistic,graph statistic,weighted pinq query,synthetic graph,graph topology,graphs,markov chain monte carlo,security,privacy,social networks,social network,programming language,algorithms,differential privacy
Conference
abs/1203.3453
Citations 
PageRank 
References 
14
0.64
11
Authors
3
Name
Order
Citations
PageRank
Davide Proserpio11118.77
Sharon Goldberg239328.23
Frank McSherry34289288.94