Wherefore art thou r3579x?: anonymized social networks, hidden patterns, and structural steganography

By Lars Backstrom, Cynthia Dwork, Jon M. Kleinberg. 2007

876 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

Differentially Private Federated Learning: A Client Level Perspective (2017, background): “Unfortunately, anonymization alone often is not sufﬁcient [7, 2] and standard machine learning approaches largely disregard privacy aspects.”
Differentially Private Empirical Risk Minimization (2009, neutral): “Such attacks have been demonstrated by various works, and are possible in many realistic settings, such as when an adversary has side information (Sweeney, 1997; Narayanan and Shmatikov, 2008; Ganta et al., 2008), and when the data has structural properties (Backstrom et al., 2007), among others.”
Universally utility-maximizing privacy mechanisms (2008, background): “Unfortunately, publication schemes initially thought to be “private” have succumbed to privacy attacks [19, 17, 1], highlighting the urgent need for mechanisms that are provably private.”
Large Scale Learning on Non-Homophilous Graphs: New Benchmarks and Strong Simple Methods (2021, background): “Smaller actors can perform certain attacks, but this may be made more difficult by resource requirements such as the need for certain external information [50] or the ability to add nodes and edges before an anonymized version of a social network is released [5].”
Structural Data De-anonymization: Quantification, Practice, and Implications (2014, methodology): “Actually, they may follow the power-law model , exponential model , etc. [21][22][26].”
K-isomorphism: privacy preserving network publication against structural attacks (2010, background): “As a pioneer work on privacy in social networks, Backstrom et al [2] discuss both active and passive attacks using small subgraphs.”
A brief survey on anonymization techniques for privacy preserving publishing of social network data (2008, methodology): “As shown in [3], the creation of 7 vertices by an attacker can reveal an average of 70 target vertices.”
Private analysis of graph structure (2011, background): “Attacks on anonymized social network data are studied, for example, in [1, 8].”
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].”
Zerocoin: Anonymous Distributed E-Cash from Bitcoin (2013, background): “[37] constructed targeted attacks against anonymized social networks to test for relationships between vertices.”
An Analysis of Anonymity in the Bitcoin System (2011, background): “[15] consider privacy attacks which identify users using structure the network and show the difficulty of guaranteeing anonymity in the presence of network data.”
Predict Anchor Links across Social Networks via an Embedding Approach (2016, background): “However, information about anchor links is often not available in practical scenarios, because most users have no motivation or are un-willing to explicitly correlate their identities in different on-line social networks [Backstrom et al. , 2007].”
Differentially private data analysis of social networks via restricted sensitivity (2012, background): “The de.nition of restricted sensitivity is similar to that of global sensitivity except that instead of quantifying over all possible datasets, we take advantage of any beliefs about the dataset that a querier may have, to quantify over a restricted class of datasets.”
Technical Privacy Metrics (2015, background): “xplicitly consider the amount of prior information. 5.2.1Amount of Leaked Information This metric counts the number of information items Ldisclosed by a system, e.g., the number of compromised users [Backstrom et al. 2007] or the number of leaked DNA base pairs [Wang et al. 2009]. However, this metr”