Performance Analysis of K-Degree Anonymization on Barabási-Albert Graph

Year 2023, , 661 - 670, 28.06.2023

Fatih Soygazi , Damla Oğuz

https://doi.org/10.35414/akufemubid.1149701

Abstract

Anonymity is one the most important problems that emerged with the increasing number of graph-based social networks. It is not straightforward to ensure anonymity by adding or removing some nodes from the graph. Therefore, a more sophisticated approach is required. The consideration of the degree of the nodes in a graph may facilitate having knowledge about specific nodes. To handle this problem, one of the prominent solutions is k-degree anonymization where some nodes involving particular degree values are anonymized by masking its information from the attackers. Our objective is to evaluate the achievement of k-degree anonymization with a well-known graph structure, namely, Barabási-Albert graph, which is similar to the graphs on social networks. Hence, we generate multiple synthetic Barabási-Albert graphs and evaluate the k-degree anonymization performance on these graphs. According to experimental results, the success of k-degree anonymity approximately proportional to the number of edges or nodes.

Keywords

Anonymization, K-degree Anonymity, Barabási -Albert Graph, Social Networks, Knowledge Bases

Barabási-Albert Çizgesinde K-Derece Anonimleştirmenin Performans Analizi

Abstract

Anonimlik, çizge tabanlı sosyal ağların sayısının artmasıyla ortaya çıkan en önemli sorunlardan biridir. Çizgeye bazı düğümler ekleyerek veya çıkararak anonimliği sağlamak kolay değildir. Bu nedenle, daha komplike bir yaklaşım gereklidir. Çizgenin yapısı veya çizgedeki düğümlerin derecesi, belirli düğümler hakkında bilgi sahibi olmayı kolaylaştırabilir. Bu sorun için öne çıkan çözümlerden biri olan k-derece anonimleştirme, belirli dereceleri içeren bazı düğümlerin bilgilerinin saldırganlardan gizlenerek anonimleştirilmesidir. Amacımız, sosyal ağlardaki çizgelere benzeyen Barabási-Albert çizgesi gibi iyi bilinen bir çizge yapısı ile k-derece anonimleştirmenin başarısını değerlendirmektir. Bu nedenle, birden çok sentetik Barabási-Albert çizgesi değerlendiriyoruz. Deneysel sonuçlara göre, k-derece anonimliğin başarısı, yaklaşık olarak kenar veya düğüm sayısı ile orantılıdır.

Keywords

Anonimleştirme, K-derece Anonimlik, Barabási-Albert Çizgesi, Sosyal Ağlar, Bilgi Tabanları

References

• Aggarwal, G., Feder, T., Kenthapadi, K., Motwani, R., Panigrahy, R., Thomas, D., and Zhu, A., 2005. Approximation algorithms for k-anonymity. Journal of Privacy Technology (JOPT).
• Albert, R. and Barabási, A. L., 2002. Statistical mechanics of complex networks. Reviews of modern physics, 74(1), 47.
• Barabási, A. L. 2002. Linked: The New Science of Networks. Perseus Books Group.
• Barabási, A. L. 2016. Network Science. Cambridge University Press, Cambridge.
• Barabási, A. L. and Albert, R., 1999. Emergence of scaling in random networks. Science, 286(5439), 509-512.
• Barabási, A. L., Albert, R., and Jeong, H. 1999. Mean-field theory for scale-free random networks. Physica A: Statistical Mechanics and its Applications, 272(1-2), 173-187.
• Bayardo, R. J., and Agrawal, R. 2005. Data privacy through optimal k-anonymization. In 21st International Conference on Data Engineering (ICDE'05), 217-228.
• Ciriani, V., Capitani di Vimercati, S. D., Foresti, S., and Samarati, P. 2007. “κ-anonymity”, Secure Data Management in Decentralized Systems, 323-353.
• Cohen, R., Rozenfeld, A. F., Schwartz, N., Ben-Avraham, D., and Havlin, S. 2003. Directed and non-directed scale-free networks. Statistical Mechanics of Complex Networks, 23-45.
• Hay, M., Miklau, G., Jensen, D., Towsley, D., and Weis, P., 2008. Resisting structural re-identification in anonymized social networks. Proceedings of the VLDB Endowment, 1(1), 102-114.
• Kiabod, M., Dehkordi, M. N., and Barekatain, B., 2021. A fast graph modification method for social network anonymization. Expert Systems with Applications, 180, 115-148.
• Li, K., Tian, L., Zheng, X., and Hui, B., 2022. Plausible Heterogeneous Graph k-Anonymization for Social Networks. Tsinghua Science and Technology, 27(6), 912-924.
• Liu, K. and Terzi, E., 2008. Towards identity anonymization on graphs. In Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data, 93-106.
• Lu, X., Song, Y., and Bressan, S. 2012. Fast identity anonymization on graphs. In International Conference on Database and Expert Systems Applications, 281-295.
• Ma, J., Qiao, Y., Hu, G., Huang, Y., Sangaiah, A. K., Zhang, C., ... and Zhang, R., 2017. De-anonymizing social networks with random forest classifier. IEEE Access, 6, 10139-10150.
• Minello, G., Rossi, L., and Torsello, A. 2020. k-Anonymity on Graphs Using the Szemerédi Regularity Lemma. IEEE Transactions on Network Science and Engineering, 8(2), 1283-1292.
• Mohapatra, D., and Patra, M. R. 2017. A level-cut heuristic-based clustering approach for social graph anonymization. Social Network Analysis and Mining, 7(1), 1-13.
• Narayanan, A., and Shmatikov, V., 2009. De-anonymizing social networks. In 2009 30th IEEE Symposium on Security and Privacy, 173-187.
• Qian, J., Li, X. Y., Zhang, C., and Chen, L., 2016. De-anonymizing social networks and inferring private attributes using knowledge graphs. In IEEE INFOCOM 2016-The 35th Annual IEEE International Conference on Computer Communications, 1-9.
• Ren, X. M., Jia, B. X., Wang, K. C., and Cheng, J. 2014. Research on k-anonymity privacy protection of social network. Applied Mechanics and Materials, 530, 701-704.
• Rosato, V., Meloni, S., Simonsen, I., Issacharoff, L., Peters, K., Festenberg, N. V., & Helbing, D. 2008. A complex system’s view of critical infrastructures. Managing Complexity: Insights, Concepts, Applications, Springer, 241-260.
• Rossi, L., Musolesi, M., and Torsello, A., 2015. On the k-anonymization of time-varying and multi-layer social graphs. In Ninth International AAAI Conference on Web and Social Media (ICWSM 2015).
• Samarati, P., 2001. Protecting respondents identities in microdata release. IEEE Transactions on Knowledge and Data Engineering, 13(6), 1010-1027.
• Samarati, P., and Sweeney, L. 1998a. Protecting privacy when disclosing information: k-anonymity and its enforcement through generalization and suppression.
• Samarati, P., and Sweeney, L. 1998b. Generalizing data to provide anonymity when disclosing information. PODS, 98(188).
• Sweeney, L. 2002. k-anonymity: A model for protecting privacy. International Journal of Uncertainty, Fuzziness and Knowledge-based Systems, 10(05), 557-570.
• Wu, X., Ying, X., Liu, K., and Chen, L., 2010. A survey of privacy-preservation of graphs and social networks. In Managing and Mining Graph Data, Springer, 421-453.
• Zhong, S., Yang, Z., and Wright, R. N. 2005. Privacy-enhancing k-anonymization of customer data. In Proceedings of the Twenty-Fourth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 139-147.
• Zou, L., Chen, L., & Özsu, M. T., 2009. K-automorphism: A general framework for privacy preserving network publication. Proceedings of the VLDB Endowment, 2(1), 946-957.