Differentially private network data release via structural inference

Qian Xiao, Rui Chen, Kian Lee Tan

Research output: Chapter in book/report/conference proceedingConference proceedingpeer-review

136 Citations (Scopus)

Abstract

Information networks, such as social media and email networks, often contain sensitive information. Releasing such network data could seriously jeopardize individual privacy. Therefore, we need to sanitize network data before the release. In this paper, we present a novel data sanitization solution that infers a network's structure in a differentially private manner. We observe that, by estimating the connection probabilities between vertices instead of considering the observed edges directly, the noise scale enforced by differential privacy can be greatly reduced. Our proposed method infers the network structure by using a statistical hierarchical random graph (HRG) model. The guarantee of differential privacy is achieved by sampling possible HRG structures in the model space via Markov chain Monte Carlo (MCMC). We theoretically prove that the sensitivity of such inference is only O(log n), where n is the number of vertices in a network. This bound implies less noise to be injected than those of existing works. We experimentally evaluate our approach on four real-life network datasets and show that our solution effectively preserves essential network structural properties like degree distribution, shortest path length distribution and influential nodes.

Original languageEnglish
Title of host publicationKDD 2014 - Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
PublisherAssociation for Computing Machinery (ACM)
Pages911-920
Number of pages10
ISBN (Print)9781450329569
DOIs
Publication statusPublished - 2014
Externally publishedYes
Event20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2014 - New York, NY, United States
Duration: 24 Aug 201427 Aug 2014

Publication series

NameProceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

Conference

Conference20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2014
Country/TerritoryUnited States
CityNew York, NY
Period24/08/1427/08/14

Scopus Subject Areas

  • Software
  • Information Systems

User-Defined Keywords

  • differential privacy
  • network data
  • structural inference

Fingerprint

Dive into the research topics of 'Differentially private network data release via structural inference'. Together they form a unique fingerprint.

Cite this