Anonymizing Social Networks

By Michael Hay, Gerome Miklau, David D. Jensen, Philipp Weis, Siddharth Srivastava. 2007

1,071 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Sociology and Political Science

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

Dependence Makes You Vulnberable: Differential Privacy Under Dependent Tuples (2016, methodology): “Social and behavioral dependence have also been used to perform de-anonymization attacks on released datasets [22], [32], [33], [37].”
Preserving Link Privacy in Social Network Based Systems (2012, methodology): “[12] propose a perturbation algorithm which applies a sequence of k edge deletions followed by k random edge insertions.”
“But the data is already public”: on the ethics of research in Facebook (2010, background): “Stutzman’s concern over the ability to exploit the uniqueness of one’s social graph to identify an individual within a large dataset has proven true in numerous cases (see, for example, Narayanan and Shmatikov 2008, 2009).”
Accurate Estimation of the Degree Distribution of Private Networks (2009, background): “It is now well-known that removing identifiers from a social network and releasing a “naively anonymized” isomorphic network can leave participants open to a range of attacks [1], [7], [17].”
K-Automorphism: A General Framework For Privacy Preserving Network Publication (2009, background): “Therefore, the problem that we want to solve in this paper is deﬁned as follows: Given an original network G , ﬁnd a network G ∗ , where We require that G is a sub-graph of G ∗ .”
A Guide to Differential Privacy Theory in Social Network Analysis (2012, background): “However, even a noisy graph structure with no node parameters whatsoever can be subject to deanonymization, particularly if an attacker has background knowledge of the network data [3].”
Resisting structural re-identification in anonymized social networks (2008, methodology): “In the same report, we proposed the first anonymization technique for graphs, a technique based on random edge deletions and insertions, which resisted attacks of an H1 adversary, but at a significant cost in graph utility [14].”
Preserving Privacy in Social Networks Against Neighborhood Attacks (2008, background): “[15] presented a framework for assessing the privacy risk of sharing anonymized network data.”
Security issues in cloud environments: a survey (2014, background): “Narayanan and Shmatikov [179] proposed an algorithm with only a 12 % de-anonymization error rate on an online photo-sharing Web site purely based on network topology information.”
Data and Structural k-Anonymity in Social Networks (2009, background): “As shown in [9,10], when the structure of a random graph is known, the probability that there are two nodes with identical 3-radius neighborhoods is less than 2−cn, where n represents the number of nodes in the graph, and c is a constant value, c > 0; this means that the vast majority of the nodes c”
Collective Data-Sanitization for Preventing Sensitive Information Inference Attacks in Social Networks (2018, background): “In [9], the authors consider a de-anonymization algorithm to re-identify the users in an anony-”
Multiparty Differential Privacy via Aggregation of Locally Trained Classifiers (2010, result): “Merely anonymizing the data is not sufficient – an adversary with access to publicly available auxiliary information can still recover the information about individual, as was the case with the de-anonymization of the Netflix dataset [1].”
Randomizing Social Networks: a Spectrum Preserving Approach (2008, background): “Although [7] shows that graph randomization can greatly reduce the chance for the attackers to re-identify the subgraph known to them, we here still assume that, in G′, the attackers have identified the subgraph corresponding to G(X), denoted by G′(X).”
Preserving the Privacy of Sensitive Relationships in Graph Data (2007, background): “The existing work looks at the identifying structural properties of the graph nodes [2] [7], or considers relations to be attributes of nodes [13].”
Social Network Analysis and Mining for Business Applications (2011, methodology): “The methods of the second category [Hanhijarvi et al. 2009; Hay et al. 2007; Ying and Wu 2008, 2009a, 2009b] add noise to the data, in the form of random additions, deletions or switching of edges, in order to prevent adversaries from identifying their target in the network, or from inferring…”
Protecting privacy when mining and sharing user data (2012, background): “In [80], the authors experimentally evaluate how much background information about the structure of the neighborhood of an individual would be su cient for an attacker to uniquely identify the individual in such an anonymized graph.”
Secure Deep Graph Generation with Link Differential Privacy (2020, background): “The rich relational structures in graph data often allow attackers to recover private information through various ways of collective inference [Zhang et al., 2014; Narayanan and Shmatikov, 2009].”