Pvk-Degree Anonymity: Shielding Multi-Social Networks Against Dopv Attacks

TL;DR

As users increasingly link multiple social accounts (e.g., linking Twitter/X to Instagram), they inadvertently create a unique structural "fingerprint" composed of their friend counts across different platforms. This paper identifies the Dopv (Degree of paired vertices) Attack—a method to re-identify users by combining their degrees from two published graphs. To counter this, the authors develop Pvk-degree anonymity, an algorithm that ensures no user’s dual-platform degree signature is unique, while maintaining the social network's structural integrity.

Background & Motivation: The Multi-Network Vulnerability

Most research in graph privacy assumes a siloed environment. However, the reality of modern social media is an interconnected web. If an attacker knows Alice has 150 friends on Graph A and 300 on Graph B, they can look for the pair (150, 300) across both datasets. Even if Graph A and Graph B independently satisfy k-anonymity, the combination of degrees often remains unique.

The authors' central insight is that anonymity must be global across platforms. If we treat the degree pair $(d_1,d_2)$ as a single identifier, we can apply heuristic grouping to hide the individual in a crowd of $k$ similar peers.

Methodology: The Pvk-Anonymity Pipeline

The proposed solution follows a rigorous three-step process:

1. Dopv Grouping & Merging

The algorithm treats each Dopv as a point in a 2D coordinate system. It sorts these pairs and groups them using a cost function that minimizes the "Anonymizing Cost"—the total number of edges that must be added or removed to make all group members have identical $(d_x,d_y)$ values.

Figure 1: Examples showing how unpaired nodes (Npp) and paired nodes (Dopv) are processed to reach k-anonymity.

2. Ensuring Graphical Realizability (The Havel Theorem)

Not every sequence of integers can actually form a real graph. To prevent the algorithm from generating "impossible" degree sequences, the authors utilize the Havel Theorem. They implement a "double-target" method that chooses between odd and even candidate degrees to ensure the final sequence is "graphical."

3. Graph Modification

Once the target degrees are set, the algorithm modifies the edges. It prioritizes keeping original edges and only adds the minimum necessary new links (Case 1) or removes excess links (Case 2) to match the anonymous degree sequence.

Experiments & Results

The authors validated their approach using R-MAT models, which simulate real-world "power-law" distributions and "small-world" phenomena common in social networks.

• Utility Preservation: The Average Path Length (APL) showed negligible change, meaning the "six degrees of separation" property of the network remained intact.
• Clustering Stability: The Average Clustering Coefficient (ACC) remained stable, indicating that the local community structures were not destroyed by the edge modifications.
• Efficiency: While running time increases with $k$ and vertex count, the heuristic remains scalable for medium-sized networks.

Figure 2: Percentage of edges added/deleted to reach Pvk-degree anonymity across different k-values.

Critical Insight & Conclusion

This work highlights a critical shift from Node Privacy to Identity Privacy across Graphs. The Dopv attack is a low-cost, high-efficiency heuristic that doesn't requires complex subgraph isomorphism—just basic degree knowledge.

Takeaway: As data publication becomes more common, researchers must stop looking at graphs in isolation. The Pvk-degree anonymity model provides a robust framework for multi-graph protection, though future work is needed to scale the Havel-based checks for massive, billion-node real-world datasets.

Limitations: The current study relies on artificial datasets. While R-MAT is a standard surrogate, real-world user behavior may introduce noise or higher-order correlations (like mutual friend counts) that this degree-only model might still be vulnerable to.