Citation :

Mariam RAMDI, Ouafae BAIDA, Abdelouahid LYHYAOUI, "Neighborhood-Based Similarity Anonymization (NSA): A Multi-Level Approach for Graph Anonymization," International Journal of Engineering Trends and Technology (IJETT), vol. 73, no. 12, pp. 151-161, 2025. Crossref, https://doi.org/10.14445/22315381/IJETT-V73I12P112

Abstract

Social network emergence has enabled the dissemination of vast amounts of data, beneficial to numerous applications but detrimental to privacy. Typical anonymization approaches often face the challenge of finding a balance between the utility and the protection of privacy, leading to excessive information loss or weak anonymization. In this paper, a new methodology, Neighborhood-Based Similarity Anonymization (NSA), is proposed, which strengthens privacy through an evaluation of user similarity at multi-level network neighborhoods. Unlike conventional approaches that consider direct user associations, NSA adopts 1-hop (direct), 2-hop (friends-of-friends), and 3-hop (third-degree) neighborhood similarities for intelligent edge elimination decisions aimed at retaining the connected graph, where ‘hop’ defines the distance between users in the network graph. With the real-world Twitter dataset, the efficiency of the proposed method, NSA, for the protection of privacy with retention of structural integrity, is shown to outperform common similarity-based anonymization techniques with an outstanding balance between privacy and utility.

Keywords

Privacy, Reidentification, Data Utility, Anonymization, Social Networks.

References

[1] R. Mariam et al., “An Innovative User Similarity-Based Privacy Preservation Approach,” Journal of Theoretical and Applied Information Technology, vol. 102, no. 17, 2024.
[Google Scholar] [Publisher Link]

[2] Latanya Sweeney, “k-Anonymity: A Model for Protecting Privacy,” International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, vol. 10, no. 5, pp. 557-570, 2002.
[CrossRef] [Google Scholar] [Publisher Link]

[3] Ashwin Machanavajjhala et al., “L-Diversity: Privacy Beyond k-Anonymity,” ACM Transactions on Knowledge Discovery from Data (TKDD), vol. 1, no. 1, pp. 3-es, 2007.
[CrossRef] [Google Scholar] [Publisher Link]

[4] Ninghui Li, Tiancheng Li, and Suresh Venkatasubramanian, “T-Closeness: Privacy Beyond k-Anonymity and L-Diversity,” 2007 IEEE 23^rd International Conference on Data Engineering, Istanbul, Turkey, pp. 106-115, 2007.
[CrossRef] [Google Scholar] [Publisher Link]

[5] Cynthia Dwork, “Differential Privacy,” Automata, Languages and Programming, pp. 1-12, 2006.
[CrossRef] [Google Scholar] [Publisher Link]

[6] Michael Hay et al., “Anonymizing Social Networks,” Computer Science Faculty Publication Series, University of Massachusetts Amherst, pp. 1-18, 2007.
[Google Scholar]

[7] Sen Zhang, Weiwei Ni, and Nan Fu, “Differentially Private Graph Publishing with Degree Distribution Preservation,” Computers & Security, vol. 106, 2021.
[CrossRef] [Google Scholar] [Publisher Link]

[8] Bin Zhou, and Jian Pei, “Preserving Privacy in Social Networks against Neighborhood Attacks,” 2008 IEEE 24^th International Conference on Data Engineering, Cancun, Mexico, pp. 506-515, 2008.
[CrossRef] [Google Scholar] [Publisher Link]

[9] Kun Liu, and Evimaria Terzi, “Towards Identity Anonymization on Graphs,” SIGMOD '08: Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data, pp. 93-106, 2008.
[CrossRef] [Google Scholar] [Publisher Link]

[10] Michael Hay et al., “Resisting Structural Re-Identification in Anonymized Social Networks,” Proceedings of the VLDB Endowment, vol. 1, no. 1, pp. 102-114, 2008.
[CrossRef] [Google Scholar] [Publisher Link]

  [11] Arvind Narayanan, and Vitaly Shmatikov, “De-Anonymizing Social Networks,” 2009 30^th IEEE Symposium on Security and Privacy, Oakland, CA, USA, pp. 173-187, 2009.
[CrossRef] [Google Scholar] [Publisher Link]

[12] Alina Campan, and Traian Marius Truta, “Data and Structural k-Anonymity in Social Networks,” International Workshop on Privacy, Security, and Trust in KDD, pp. 33-54, 2008.
[CrossRef] [Google Scholar] [Publisher Link]

[13] Yang Li et al., “Private Graph Data Release: A Survey,” ACM Computing Surveys, vol. 55, no. 11, pp. 1-39, 2023.
[CrossRef] [Google Scholar] [Publisher Link]

[14] Xiaowei Ying, and Xintao Wu, “Randomizing Social Networks: A Spectrum Preserving Approach,” Proceedings of the 8^th SIAM International Conference on Data Mining (SDM), pp. 739-750, 2008.
[CrossRef] [Google Scholar] [Publisher Link]

[15] Chris Clifton, “Privacy-Preserving Data Mining,” Encyclopedia of Database Systems, Springer, New York, pp. 2819-2821, 2018.
[CrossRef] [Google Scholar] [Publisher Link]

[16] Vibhor Rastogi et al., “Relationship Privacy: Output Perturbation for Queries with Joins,” PODS '09: Proceedings of the Twenty-Eighth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, pp. 107-116, 2009.
[CrossRef] [Google Scholar] [Publisher Link]

[17] Sean Chester, and Gautam Srivastava, “Social Network Privacy for Attribute Disclosure Attacks,” 2011 International Conference on Advances in Social Networks Analysis and Mining, Kaohsiung, Taiwan, pp. 445-449, 2011.
[CrossRef] [Google Scholar] [Publisher Link]