Resisting structural re-identification in anonymized social networks

By Michael Hay, Gerome Miklau, David D. Jensen, D. Towsley, Chao Li. The VLDB journal, 2008

691 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Sociology and Political Science

View Paper: https://www.semanticscholar.org/paper/d20c3467a957cb58af4689734f528065ae4b4290

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

In Sociology and Political Science

Citations in the corpus

Boosting the accuracy of differentially private histograms through consistency (2009, background): “Most techniques [7, 8, 13] publish transformed graphs designed to protect anonymity; we are not aware of any that satisfy differential privacy.”
Correlated network data publication via differential privacy (2013, methodology): “[17], but differs in more rigorous privacy protection in the presence of node attributes.”
Accurate Estimation of the Degree Distribution of Private Networks (2009, methodology): “Empirically, it appears that with increasing anonymity, the graph is rapidly distorted and some metrics are systematically biased [3], [7], [13], [22], [23].”
On Your Social Network De-anonymizablity: Quantification and Large Scale Evaluation with Seed Knowledge (2015, methodology): “Generally, the data anonymization techniques can be characterized into three classes: naive ID removal, k-anonymization (including randomly adding/deleting edges) [11][12], and differential privacy [13][14].”
K-isomorphism: privacy preserving network publication against structural attacks (2010, methodology): “In previous works such as [11, 19, 30, 33], it is recognized that the utility of graph data depends on the preservation of some graph properties and their empirical studies are based on such properties.”
Relationship privacy: output perturbation for queries with joins (2009, background): “Each publishes a transformed graph that provides anonymity by creating structurally similar groups [11, 22, 12, 3].”
To join or not to join: the illusion of privacy in social networks with mixed public and private user profiles (2009, positive): “If one anonymizes the data na¨ovely by removing personal attributes and replacing them with a random identifier, it still is possible to identify individuals based on their subgraph structure [3, 8 , 15].”
Link prediction by de-anonymization: How We Won the Kaggle Social Network Challenge (2011, background): “Several papers have claimed to provide k-anonymity, or variants thereof, for graphs [16], [20], [9], [30].”
Effective Pattern Discovery for Text Mining (2012, background): “In this paper, Michael Hay, Gerome Miklau, David Jensen, Don Towsley and Philip Weis (2008) [9], measured the privacy of every individuals in the graph.”
Preserving Link Privacy in Social Network Based Systems (2012, neutral): “, [11] and [37]).”
A Framework for Computing the Privacy Scores of Users in Online Social Networks (2009, background): “None of the previous work on privacy-preserving social-network analysis [Backstrom et al. 2007; Hay et al. 2008; Liu and Terzi 2008; Ying and Wu 2008; Zhou and Pei 2008] has addressed privacy concerns from this perspective.”
Large Scale Learning on Non-Homophilous Graphs: New Benchmarks and Strong Simple Methods (2021, background): “Furthermore, additional actors could make use of deanonymization attacks [30, 49, 50] to reveal user identities in supposedly anonymized datasets.”
A brief survey on anonymization techniques for privacy preserving publishing of social network data (2008, methodology): “Graph metrics can be used as background knowledge for the adversaries to breach the privacy of target individuals [12; 36].”
Data and Structural k-Anonymity in Social Networks (2009, background): “[9,10], but we assume a much richer data model than just the structural information associated to the social network.”
Differentially private anonymized histograms (2019, background): “However, some graphs may have unique degree distributions and releasing exact degree distributions is no more safer than naive anonymization, which can leave social network participants vulnerable to a variety of attacks [9, 10, 11].”