2014 ExponentialRandomGraphEstimatio

• (Lu & Miklau, 2014) ⇒ Wentian Lu, and Gerome Miklau. (2014). “Exponential Random Graph Estimation under Differential Privacy.” In: Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2014) Journal. ISBN:978-1-4503-2956-9 doi:10.1145/2623330.2623683

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%222014%22+Exponential+Random+Graph+Estimation+under+Differential+Privacy
• http://dl.acm.org/citation.cfm?id=2623330.2623683&preflayout=flat#citedby

Quotes

Author Keywords

• Data mining; differential privacy; exponential random graph model; security, integrity, and protection

Abstract

The effective analysis of social networks and graph-structured data is often limited by the privacy concerns of individuals whose data make up these networks. Differential privacy offers individuals a rigorous and appealing guarantee of privacy. But while differentially private algorithms for computing basic graph properties have been proposed, most graph modeling tasks common in the data mining community cannot yet be carried out privately.

In this work we propose algorithms for privately estimating the parameters of exponential random graph models (ERGMs). We break the estimation problem into two steps: computing private sufficient statistics, then using them to estimate the model parameters. We consider specific alternating statistics that are in common use for ERGM models and describe a method for estimating them privately by adding noise proportional to a high-confidence bound on their local sensitivity. In addition, we propose an estimation algorithm that considers the noise distribution of the private statistics and offers better accuracy than performing standard parameter estimation using the private statistics.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2014 ExponentialRandomGraphEstimatio	Wentian Lu Gerome Miklau			Exponential Random Graph Estimation under Differential Privacy				10.1145/2623330.2623683		2014