Computer Science – Cryptography and Security
Scientific paper
2012-03-15
Computer Science
Cryptography and Security
13 pages
Scientific paper
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 do this by combining the answers to Weighted PINQ queries with an incremental evaluator (Markov Chain Monte Carlo (MCMC)) that allows us 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 of synthetic graphs generated from the answers to these queries.
Goldberg Sharon
McSherry Frank
Proserpio Davide
No associations
LandOfFree
A Workflow for Differentially-Private Graph Synthesis does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A Workflow for Differentially-Private Graph Synthesis, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Workflow for Differentially-Private Graph Synthesis will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-32016