Accurate Estimation of the Degree Distribution of Private Networks

By Michael Hay, Chao Li, Gerome Miklau, David D. Jensen. 2009

459 citations recorded by the source corpus.

We describe an efficient algorithm for releasing a provably private estimate of the degree distribution of a network. The algorithm satisfies a rigorous property of differential privacy, and is also extremely efficient, running on networks of 100 million nodes in a few seconds. Theoretical analysis shows that the error scales linearly with the number of unique degrees, whereas the error of conventional techniques scales linearly with the number of nodes. We complement the theoretical analysis with a thorough empirical analysis on real and synthetic graphs, showing that the algorithm's variance and bias is low, that the error diminishes as the size of the input graph increases, and that common analyses like fitting a power-law can be carried out very accurately.

Subfields: Artificial Intelligence

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

Citations in the corpus

Privacy for the Protected (Only) (2015, background): “Definition 1 (Vertex Differential Privacy [5, 10]).”
Differentially Private Password Frequency Lists (2016, background): “[18] for releasing degree distributions in a social network.”
The Johnson-Lindenstrauss Transform Itself Preserves Differential Privacy (2012, background): “The task of preserving diﬀerential privacy when the given database is a graph or a social network was studied by Hay et al [HLMJ09] who presented a privacy preserving algorithm for publishing the degree distribution in a graph.”
Protecting privacy when mining and sharing user data (2012, background): “Di↵erentially private algorithms have been proposed for problems such as: • contingency table releases [21] • obtaining synthetic databases that are useful for all queries of a particular class (such as predicate queries computing fractional counts) [28] • computation of count queries satisfying fix”
Towards Practical Differential Privacy for SQL Queries (2017, background): “A number of less-general mechanisms for performing specific graph analysis tasks have been proposed [31, 34, 35, 49].”
Private analysis of graph structure (2011, methodology): “The number of k -stars in a graph can be expressed as a function of the degree distribution, and so the algorithm of [5] implies an algorithm for releasing the number of k -stars.”
Near-Optimal Algorithms for Differentially-Private Principal Components (2012, background): “, Barak et al., 2007, Machanavajjhala et al., 2008, McSherry and Mironov, 2009, Chaudhuri et al., 2011, Nissim et al., 2007, Blum et al., 2008, McSherry and Talwar, 2007, Friedman and Schuster, 2010, Hay et al., 2009, Williams and McSherry, 2010, Roy et al., 2010]. Differential privacy has been show”
A Guide to Differential Privacy Theory in Social Network Analysis (2012, methodology): “With a sufficiently large graph, this is a negligable amount of noise, and the utility of this technique has been successfully demonstrated [6].”
Differentially private anonymized histograms (2019, background): “Previous results: The problem of releasing anonymized histograms was first studied by [12, 4] in the context of degree distributions of graphs.”
Boosting the accuracy of differentially private histograms through consistency (2009, methodology): “The technique for unattributed histograms has been applied to accurately and efficiently estimate the degree sequences of large social networks [11].”
Differentially private data analysis of social networks via restricted sensitivity (2012, background): “[14] shows how to privately approximate the degree distribution in the edge adjacency model.”
PrivateSQL: A Differentially Private SQL Query Engine (2019, methodology): “, triangle counting, degree distribution) [10, 12, 21, 25, 26], and monotone queries (e.”
A workflow for differentially-private graph synthesis (2012, methodology): “observed that a significant amount of noise can be “cleaned up” in the degree sequence by using isotonic regression (because the degree sequence is known to be non-increasing) [3, 6].”
Regression Model Fitting under Differential Privacy and Model Inversion Attack (2015, background): “…[McSherry, 2009], synthetic graph , 2013; Mir and Wright, 2009; Sala et al. , 2011 ] , computing graph properties such as degree distributions [ Hay et al. , 2009 ] and clustering coefﬁcient [ Rastogi et al. , 2009; Wang et al. , 2012 ] , and spectral graph analysis [ Wang et al. , 2013 ] in…”
Resisting structural re-identification in anonymized social networks (2008, methodology): “Under edge-differential privacy, which prevents the disclosure of individual edges, the degree distribution [ 18 ,21] and other network analyses have low sensitivity and can be answered accurately [13].”
Practical Differential Privacy for SQL Queries Using Elastic Sensitivity (2017, background): “A number of less-general mechanisms for performing specific graph analysis tasks have been proposed [22, 25, 26, 35].”