2008 · 782 citations · 16 references
ComputingComputer ScienceMathematicsCryptographyNetwork SecurityPrivacy EngineeringData AnonymizationData De-identificationData PrivacyData ProtectionGraph AlgorithmsGraph AnalyticsAnonymityAnonymity GuaranteesAnonymizationAnonymization AlgorithmsAnonymization For Graph DataK-anonymityPractical UtilityPrivacy
The proliferation of network data raises privacy concerns, and removing node identities alone does not guarantee privacy because graph structure and node degrees can reveal identities. We study the graph‑anonymization problem of producing a k‑degree anonymous graph with minimal modifications. We define k‑degree anonymity, formulate the optimization problem, and devise efficient algorithms based on degree‑sequence realizability. Our algorithms are fast and effective on synthetic and real datasets, demonstrating practical utility.
The proliferation of network data in various application domains has raised privacy concerns for the individuals involved. Recent studies show that simply removing the identities of the nodes before publishing the graph/social network data does not guarantee privacy. The structure of the graph itself, and in its basic form the degree of the nodes, can be revealing the identities of individuals. To address this issue, we study a specific graph-anonymization problem. We call a graph k-degree anonymous if for every node v, there exist at least k-1 other nodes in the graph with the same degree as v. This definition of anonymity prevents the re-identification of individuals by adversaries with a priori knowledge of the degree of certain nodes. We formally define the graph-anonymization problem that, given a graph G, asks for the k-degree anonymous graph that stems from G with the minimum number of graph-modification operations. We devise simple and efficient algorithms for solving this problem. Our algorithms are based on principles related to the realizability of degree sequences. We apply our methods to a large spectrum of synthetic and real datasets and demonstrate their efficiency and practical utility.
16
Collective dynamics of ‘small-world’ networks
Duncan J. Watts, Steven H. Strogatz · Nature · 1998 · 43.2K citations
Emergence of Scaling in Random Networks
Albert-Ĺaszló Barabási, Réka Albert · Science · 1999 · 36.4K citations · Full text
V. J. Rayward‐Smith, Thomas H. Cormen, Charles E. Leiserson et al. · Journal of the Operational Research Society · 1991 · 17K citations
1990 · 3.1K citations
L-diversity: privacy beyond k-anonymity
Ashwin Machanavajjhala, Johannes Gehrke, Daniel Kifer et al. · 2006 · 2.4K citations