Differentially private graphical degree sequences and synthetic graphs

Vishesh Karwa; Aleksandra B. Slavković

doi:10.1007/978-3-642-33627-0_21

Differentially private graphical degree sequences and synthetic graphs

Vishesh Karwa, Aleksandra B. Slavković

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

43 Scopus citations

Abstract

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 language	English (US)
Title of host publication	Privacy in Statistical Databases - UNESCO Chair in Data Privacy, International Conference, PSD 2012, Proceedings
Publisher	Springer Verlag
Pages	273-285
Number of pages	13
ISBN (Print)	9783642336263
DOIs	https://doi.org/10.1007/978-3-642-33627-0_21
State	Published - 2012
Event	International Conference on Privacy in Statistical Databases, PSD 2012 - Palermo, Italy Duration: Sep 26 2012 → Sep 28 2012

Publication series

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

Other

Other	International Conference on Privacy in Statistical Databases, PSD 2012
Country/Territory	Italy
City	Palermo
Period	9/26/12 → 9/28/12

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-642-33627-0_21

Cite this

Karwa, V., & Slavković, A. B. (2012). Differentially private graphical degree sequences and synthetic graphs. In Privacy in Statistical Databases - UNESCO Chair in Data Privacy, International Conference, PSD 2012, Proceedings (pp. 273-285). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7556 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-642-33627-0_21

Karwa, Vishesh ; Slavković, Aleksandra B. / Differentially private graphical degree sequences and synthetic graphs. Privacy in Statistical Databases - UNESCO Chair in Data Privacy, International Conference, PSD 2012, Proceedings. Springer Verlag, 2012. pp. 273-285 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{80a23b338b754614921e10278650144d,

title = "Differentially private graphical degree sequences and synthetic graphs",

abstract = "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.",

author = "Vishesh Karwa and Slavkovi{\'c}, {Aleksandra B.}",

year = "2012",

doi = "10.1007/978-3-642-33627-0_21",

language = "English (US)",

isbn = "9783642336263",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "273--285",

booktitle = "Privacy in Statistical Databases - UNESCO Chair in Data Privacy, International Conference, PSD 2012, Proceedings",

address = "Germany",

}

Karwa, V & Slavković, AB 2012, Differentially private graphical degree sequences and synthetic graphs. in Privacy in Statistical Databases - UNESCO Chair in Data Privacy, International Conference, PSD 2012, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 7556 LNCS, Springer Verlag, pp. 273-285, International Conference on Privacy in Statistical Databases, PSD 2012, Palermo, Italy, 9/26/12. https://doi.org/10.1007/978-3-642-33627-0_21

Differentially private graphical degree sequences and synthetic graphs. / Karwa, Vishesh; Slavković, Aleksandra B.
Privacy in Statistical Databases - UNESCO Chair in Data Privacy, International Conference, PSD 2012, Proceedings. Springer Verlag, 2012. p. 273-285 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7556 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Differentially private graphical degree sequences and synthetic graphs

AU - Karwa, Vishesh

AU - Slavković, Aleksandra B.

PY - 2012

Y1 - 2012

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84867507326&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84867507326&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-33627-0_21

DO - 10.1007/978-3-642-33627-0_21

M3 - Conference contribution

AN - SCOPUS:84867507326

SN - 9783642336263

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 273

EP - 285

BT - Privacy in Statistical Databases - UNESCO Chair in Data Privacy, International Conference, PSD 2012, Proceedings

PB - Springer Verlag

T2 - International Conference on Privacy in Statistical Databases, PSD 2012

Y2 - 26 September 2012 through 28 September 2012

ER -

Karwa V, Slavković AB. Differentially private graphical degree sequences and synthetic graphs. In Privacy in Statistical Databases - UNESCO Chair in Data Privacy, International Conference, PSD 2012, Proceedings. Springer Verlag. 2012. p. 273-285. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-33627-0_21

Differentially private graphical degree sequences and synthetic graphs

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this