You Can't See Me: Anonymizing Graphs Using the Szemerédi Regularity Lemma.

Area of Science:

• Graph theory
• Network science
• Data privacy

Background:

• Online interactions generate complex networks revealing user behavior.
• Sharing sensitive network data poses significant privacy risks, especially online.
• k-anonymity techniques obfuscate graph topology to protect node identities.

Purpose of the Study:

• To propose a novel algorithm for enforcing k-anonymity in complex networks.
• To leverage extremal graph theory, specifically the Szemerédi regularity lemma, for graph anonymization.
• To enhance data privacy in online social networks without significant information loss.

Main Methods:

• Computing a regular partition of graph nodes based on the Szemerédi regularity lemma.
• Randomizing edges within the partitions to make nodes structurally indistinguishable.
• Applying the algorithm to real-world network data, such as Facebook networks.

Main Results:

• The proposed algorithm successfully anonymizes graphs by enforcing k-anonymity.
• The anonymized graphs retain a significant portion of their original structural information.
• Experimental results demonstrate the effectiveness of the approach on real-world datasets.

Conclusions:

• The novel k-anonymity algorithm based on the Szemerédi regularity lemma offers a robust solution for privacy preservation in complex networks.
• This method balances data anonymization with the preservation of network structure, crucial for subsequent analysis.
• The approach shows promise for securing sensitive information in online social networks.