Preserving the Social Skeleton: A Comparative Study of MST-Based Edge Weight Anonymization

TL;DR

In the era of big data, social ties are commodities. This paper explores how to hide the exact "strength" of social connections (edge weights) without breaking the fundamental structure of the network. By modeling Kruskal’s and Prim’s algorithms as Linear Programming problems, the authors provide a way to swap real connection data with anonymous values that yield the exact same Minimum Spanning Tree (MST).

Motivation: Why Protect Edge Weights?

In a social network graph, an edge weight isn't just a number—it represents the frequency of interaction, trust levels, or financial transaction volumes between individuals. Prior work has often focused on hiding who is connected to whom, but if an adversary knows the weights, they can still infer sensitive relationships.

The challenge is Utility vs. Privacy: How do you change the weights to protect privacy while ensuring the graph remains useful for researchers (e.g., maintaining the same backbone or shortest paths)?

Methodology: The LP Modeling Approach

The authors build upon the concept that an algorithm's execution is a series of decisions based on inequalities. If an algorithm chooses edge $A$ over edge $B$ because $Weight(A)<Weight(B)$, we can replace these weights with any values $x_A$ and $x_B$ as long as $x_A<x_B$ holds true.

1. Kruskal-Based Anonymization

Kruskal’s algorithm is edge-centric. It sorts all edges and picks the smallest ones that don't form a cycle.

• The Constraint: If edge $i$ is chosen before edge $j$, the model enforces $x_i\le x_j$.
• Insight: This results in a strict global ordering of weights, which limits the number of possible anonymous solutions.

2. Prim-Based Anonymization

Prim’s algorithm is vertex-centric. It grows the tree from a starting node, picking the cheapest edge connected to the currently reached set of vertices.

• The Constraint: An edge is chosen if it is the minimum among edges connecting the growing tree to new vertices.
• Insight: Since Prim only compares local neighbors at each step rather than all edges globally, the resulting system of inequalities is less restrictive.

Figure 1: Comparison of MST construction which serves as the "Ground Truth" for the anonymity model.

Experiments and Discovery

The researchers tested both models using different edge weight ranges (1–5, 2–6, etc.) and measured the "Anonymity Degree" ($\alpha$).

Key Findings:

• Solution Density: Under the same range constraints, Prim’s algorithm yielded 45,261 solutions, whereas Kruskal’s yielded only 126.
• Efficiency: Kruskal’s is lightning fast (sub-second), while Prim’s takes longer (around 150-200 seconds for the same graph).
• Feasibility: Both successfully produced "Anonymity Graphs" that, when processed by standard algorithms, resulted in the exact same MST as the original sensitive data.

Figure 2: Analysis of computation time across different weight ranges.

Critical Insight: Prim is the Winner for Privacy

The most profound takeaway is that Prim’s algorithm is fundamentally better for privacy. Because it doesn't require a total ordering of all edges in the graph, the "feasible region" in the Linear Programming space is much larger. For a data publisher, this means there are millions of ways to disguise the data, making it exponentially harder for an attacker to guess the original values.

Conclusion & Future Work

The paper successfully moves the theoretical LP approach into a practical, algorithmic comparison. While it proves that MST properties can be preserved, future research should explore:

1. Scaling: How do these LP solvers handle graphs with millions of nodes?
2. Multi-Property Preservation: Can we preserve both the MST and the Shortest Paths simultaneously without making the weight constraints so tight that the solution set becomes zero?

This work provides a robust blueprint for web publishers to share social data responsibly, ensuring that while the "Social Skeleton" remains visible for science, the individual "Nerves" (weights) remain hidden.