Inference using noisy degrees: differentially private -model and synthetic graphs
From MaRDI portal
Publication:5963517
DOI10.1214/15-AOS1358zbMATH Open1331.62114arXiv1205.4697OpenAlexW3105437875MaRDI QIDQ5963517FDOQ5963517
Vishesh Karwa, Aleksandra Slavković
Publication date: 22 February 2016
Published in: The Annals of Statistics (Search for Journal in Brave)
Abstract: The -model of random graphs is an exponential family model with the degree sequence as a sufficient statistic. In this paper, we contribute three key results. First, we characterize conditions that lead to a quadratic time algorithm to check for the existence of MLE of the -model, and show that the MLE never exists for the degree partition -model. Second, motivated by privacy problems with network data, we derive a differentially private estimator of the parameters of -model, and show it is consistent and asymptotically normally distributed - it achieves the same rate of convergence as the nonprivate estimator. We present an efficient algorithm for the private estimator that can be used to release synthetic graphs. Our techniques can also be used to release degree distributions and degree partitions accurately and privately, and to perform inference from noisy degrees arising from contexts other than privacy. We evaluate the proposed estimator on real graphs and compare it with a current algorithm for releasing degree distributions and find that it does significantly better. Finally, our paper addresses shortcomings of current approaches to a fundamental problem of how to perform valid statistical inference from data released by privacy mechanisms, and lays a foundational groundwork on how to achieve optimal and private statistical inference in a principled manner by modeling the privacy mechanism; these principles should be applicable to a class of models beyond the -model.
Full work available at URL: https://arxiv.org/abs/1205.4697
Asymptotic properties of parametric estimators (62F12) Parametric inference under constraints (62F30) Social networks; opinion dynamics (91D30)
Cites Work
- Title not available (Why is that?)
- Measurement Error in Nonlinear Models
- MM algorithms for generalized Bradley-Terry models.
- Goodness of Fit of Social Network Models
- An Exponential Family of Probability Distributions for Directed Graphs
- Modeling social networks from sampled data
- On the geometry of discrete exponential families with application to exponential random graph models
- Maximum likelihood estimation in the \(\beta\)-model
- Theory of Cryptography
- Random graphs with a given degree sequence
- Threshold graphs and related topics
- Title not available (Why is that?)
- Our Data, Ourselves: Privacy Via Distributed Noise Generation
- On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph. I
- A remark on the existence of finite graphs
- A central limit theorem in the -model for undirected random graphs with a diverging number of vertices
- A sequential importance sampling algorithm for generating random graphs with prescribed degrees
- Asymptotic normality in the maximum entropy models on graphs with an increasing number of parameters
- Graver basis for an undirected graph and its application to testing the beta model of random graphs
- The polytope of degree partitions
- Statistical disclosure control in practice
- Title not available (Why is that?)
- A Statistical Framework for Differential Privacy
- Sampling for Conditional Inference on Network Data
- Analyzing Graphs with Node Differential Privacy
- Inference using noisy degrees: differentially private \(\beta\)-model and synthetic graphs
- How likely is an LLD degree sequence to be graphical?
- Universally utility-maximizing privacy mechanisms
- Polytopes from Subgraph Statistics
Cited In (25)
- Inference using noisy degrees: differentially private \(\beta\)-model and synthetic graphs
- A note on asymptotic distributions in a directed network model with degree heterogeneity and homophily
- Exponential-family models of random graphs: inference in finite, super and infinite population scenarios
- Finite Sample Differentially Private Confidence Intervals
- Asymptotic in the ordered networks with a noisy degree sequence
- Providing access to confidential research data through synthesis and verification: an application to data on employees of the U.S. federal government
- Affiliation weighted networks with a differentially private degree sequence
- Confidentiality and differential privacy in the dissemination of frequency tables
- Distribution-invariant differential privacy
- Differentially private estimation in a class of bipartite graph models
- Non-asymptotic model selection for models of network data with parameter vectors of increasing dimension
- Minimax Optimal Procedures for Locally Private Estimation
- A semiparametric Bayesian approach to epidemics, with application to the spread of the coronavirus MERS in South Korea in 2015
- Detection thresholds for the \(\beta\)-model on sparse graphs
- On the efficacy of higher-order spectral clustering under weighted stochastic block models
- Asymptotic in undirected random graph models with a noisy degree sequence
- A survey of discrete methods in (algebraic) statistics for networks
- Nonparametric density estimation for intentionally corrupted functional data
- Asymptotics in theβ-model for networks with a differentially private degree sequence
- Structure and Sensitivity in Differential Privacy: Comparing K-Norm Mechanisms
- Directed Networks with a Differentially Private Bi-degree Sequence
- Statistical Inference in a Directed Network Model With Covariates
- Edge differentially private estimation in the \(\beta\)-model via jittering and method of moments
- Bivariate gamma model
- Weighted directed networks with a differentially private bi-degree sequence
This page was built for publication: Inference using noisy degrees: differentially private \(\beta\)-model and synthetic graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5963517)
