k-Anonymization of Social Networks by Vertex Addition

Sean Chester, Bruce M. Kapron, Ganesh Ramesh, Gautam Srivastava, Alex Thomo, S. VenkateshADBIS 2011 · OpenReview

Abstract

Social network data release requires balancing privacy and utility. This paper introduces a vertex-addition approach to achieve $k$-anonymity, protecting against degree-based attacks. By adding dummy nodes instead of modifying existing edges, the method maintains critical network properties like clustering coefficients and path lengths. We provide a near-linear time algorithm for unlabeled graphs and evaluate its performance on large-scale real-world datasets.

Introduction

When organizations release social network data for research, they must protect the privacy of the individuals involved. A common threat is the "degree-based attack," where an adversary knows a specific person has exactly $d$ connections and uses this information to identify them in an anonymized graph. To prevent this, researchers use $k$-anonymity: a graph is $k$-anonymous if every node shares its degree with at least $k-1$ other nodes.

Traditionally, this is achieved by adding or removing edges between existing members of the network. However, this "edge-only" approach can significantly distort the network's utility—for example, by creating fake relationships between real people or destroying existing clusters. This paper argues that adding "dummy" nodes is often a better way to satisfy privacy requirements without corrupting the relationships between the original entities.

Previous research has explored various adversarial models and graph types, ranging from $k$-isomorphism to automorphic equivalence. Most of these methods rely on edge addition or removal, which can fundamentally alter the graph's topology. This work distinguishes itself by focusing on vertex addition as the primary permitted operation for both unlabeled and vertex-labeled graphs.

Comparison of graph anonymization techniques across literature.

Methodology

The paper explores two primary scenarios for anonymization:

  1. Vertex-Labeled Graphs: Where nodes have specific attributes. The authors prove that $k$-anonymizing these via vertex addition is NP-complete, indicating that finding an optimal solution for large datasets is computationally difficult.
  2. Unlabeled Graphs: For structural-only graphs, the authors propose a highly efficient Dynamic Programming (DP) approach.

The Algorithm for Unlabeled Graphs

The algorithm operates in four main stages:

  • Partitioning: The degree sequence of the original graph is sorted and partitioned into groups of at least $k$ nodes using DP. The goal is to minimize the "maximum deficiency" (the number of edges needed to bring a node's degree up to the target degree of its group).
  • Augmentation: A set of $m$ dummy vertices is added to the graph.
  • Connection: A bipartite-style connection scheme links original nodes to the new dummy nodes to satisfy their required degree increases.
  • Dummy Anonymization: Edges are added between the dummy nodes themselves to ensure they also meet the $k$-anonymity requirement, preventing them from becoming identifiable outliers.

Experimental Setup

The authors evaluated their approach on three diverse, real-world benchmark datasets representing different network topologies: Enron (email communication), Power Grid (infrastructure), and Net Science (co-authorship).

Characteristics of the benchmark datasets used in the study.

Key Results and Discussion

Experimental results demonstrate that the vertex-addition approach excels in maintaining network utility:

  • Minimal Distortion: Structural properties such as the Clustering Coefficient (CC) and Average Path Length (APL) remained remarkably stable. Even with a high privacy threshold ($k$ set to 2% of total nodes), the Enron dataset's properties were barely altered.
  • Connectivity Preservation: "Hop plots" confirmed that the fundamental reachability of the networks was preserved despite the increase in node count.
  • Efficiency: The algorithm is extremely fast, anonymizing the Enron dataset (over 36,000 nodes) in under 70 seconds. This $O(nk)$ complexity makes it feasible for massive social networks.

The core insight of this work is that adding new entities (dummy nodes) is often less "expensive" for data utility than forcing connections between original nodes. For instance, adding a node to a clique only increases the clique size by one, whereas adding edges between existing nodes can create entirely new, misleading cliques.

Conclusion and Future Work

While vertex addition preserves many properties, it does increase the total size of the dataset, which may be a constraint for specific storage or analysis requirements. Furthermore, the current model focuses on a "modest" adversary who only knows node degrees. Future work will aim to extend this vertex-addition logic to stronger adversarial models, such as $k$-neighborhood anonymity, where attackers possess more complex structural information.

Summary updated

BibTeX
@inproceedings{chester2011k,
  author = {Sean Chester and Bruce M. Kapron and Ganesh Ramesh and Gautam Srivastava and Alex Thomo and S. Venkatesh},
  title = {{k-Anonymization of Social Networks by Vertex Addition}},
  booktitle = {ADBIS},
  year = {2011},
  url = {https://openreview.net/forum?id=ruhb11AYmM},
}
Figure