Differentially private graphical degree sequences and synthetic graphs

Research output: Chapter in Book/Report/Conference proceedingConference contribution

41 Scopus citations


We present an algorithm for releasing graphical degree sequences of simple undirected graphs under the framework of differential privacy. The algorithm is designed to provide utility for statistical inference in random graph models whose sufficient statistics are functions of degree sequences. Specifically, we focus on the tasks of existence of maximum likelihood estimates, parameter estimation and goodness-of-fit testing for the beta model of random graphs. We show the usefulness of our algorithm by evaluating it empirically on simulated and real-life datasets. As the released degree sequence is graphical, our algorithm can also be used to release synthetic graphs under the beta model.

Original languageEnglish (US)
Title of host publicationPrivacy in Statistical Databases - UNESCO Chair in Data Privacy, International Conference, PSD 2012, Proceedings
PublisherSpringer Verlag
Number of pages13
ISBN (Print)9783642336263
StatePublished - 2012
EventInternational Conference on Privacy in Statistical Databases, PSD 2012 - Palermo, Italy
Duration: Sep 26 2012Sep 28 2012

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7556 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


OtherInternational Conference on Privacy in Statistical Databases, PSD 2012

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Differentially private graphical degree sequences and synthetic graphs'. Together they form a unique fingerprint.

Cite this