New fuzzy k-anonymity method protects 99% of network nodes with 10% uncertainty

Researchers Rachel G. de Jong, Mark P. J. van der Loo, and Frank W. Takes from Leiden University have introduced φ-k-anonymity, a new privacy framework for complex networks that incorporates attacker uncertainty. Traditional k-anonymity assumes attackers have exact knowledge of network structure, but this is unrealistic for large-scale social networks. Their fuzzy variant uses a parameter φ to model the level of uncertainty, with results showing that even modest uncertainty (φ=5%) makes 64% of previously unique nodes anonymous across a benchmark of 39 real-world networks.

To further enhance anonymity, the team applied anonymization algorithms under a strict 5% edge modification budget. While full anonymization is often impossible under exact k-anonymity, with just 10% uncertainty their Greedy algorithm anonymizes over 99% of nodes. The approach also works well on dense synthetic graphs that traditionally resist privacy protection. Crucially, data utility for structural properties and network analysis tasks remains high, with most metrics changing less than 5%. This work suggests that uncertainty-aware privacy guarantees offer a practical path for sharing network data without sacrificing usability.