An Algorithm with Low Execution Time for Anonymizing Graph Degree Sequence Based on Weighting Graph Edges

Maryam Kiabod ¹ ( Faculty of Computer Engineering- Najafabad Branch, Islamic Azad University, Najafabad, Iran )
Mohammad Naderi Dehkordi ² ( Big Data Research Center- Najafabad Branch, Islamic Azad University, Najaf Abad, Iran )
Behrang Barekatain ³ ( Big Data Research Center- Najafabad Branch, Islamic Azad University, Najaf Abad, Iran )

Submited date : 2023-01-22 Accepted date : 2023-04-25

Keywords: Optimization, Social networks, Utility, privacy preserving,

Abstract :

Social networks have been introduced as an attractive, low-cost and accessible environment for communication between users. Analyzing the information collected in these networks, as one of the main goals, can violate the privacy of users. For this purpose, several algorithms have been presented to anonymize the graph of social networks, which try to protect the privacy of social network users. However, no method has been proposed that considers the simultaneous improvement of graph utility and execution time. In this regard, the current research tries to overcome this problem by combining two algorithms, time Saving k-degree anonymization method (TSRAM) and NaFa4KDA. The first algorithm reduces the time of anonymization of the degree sequence by drawing a compact tree from the degree sequence of the graph, and the second algorithm uses an effective method to reduce the number of scans of selection edges and also increase the accuracy of the algorithm in selecting the most suitable edge. for editing, it simultaneously improves the execution time of the algorithm and the usefulness of the graph. The results of comparing the proposed algorithm with other similar algorithms show that the proposed combined algorithm has significantly increased and decreased the utility of the graph and the execution time in the process of anonymization. On average, the evaluation results show a 34% improvement in execution time and a 10% improvement in graph utility.

References:

 

[1] D. Yang, B. Qu, "Privacy-preserving social media data publishing for personalized ranking-based recommendation", IEEE Trans. on Knowledge and Data Engineering, vol. 31, no. 3, pp. 507-520, March 2019 (doi: 10.1109/TKDE.2018.2840974).

[2]   F. Ferri, P. Grifoni, T. Guzzo, "New forms of social and professional digital relationships: the case of Facebook", Social Network Analysis and Mining, vol. 2, no. 2, pp. 121–137, June 2012 (doi: 10.1007/s13278-011-0038-4).

[3] Q. Wang, C. Zeng, W. Zhou, T. Li, S.S. Iyengar, L. Shwartz, G.Y. Grabarnik, "Online interactive collaborative filtering using multi-armed bandit with dependent arms", IEEE Trans. on Knowledge and Data Engineering, vol. 31, no. 8, pp. 1569–1580, Aug. 2019 (doi: 10.1109/TKDE.2018.2866041).

[4] L. Sweeney, “k-anonymity: A model for protecting privacy", International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, vol. 10, no. 05, pp. 557–570, Oct. 2002 (doi: 10.1142/S021848­8502001648).

[5]   A. Machanavajjhala, J. Gehrke, D. Kifer, M. Venkitasubramaniam, "L-diversity: Privacy beyond k-anon­ym­i­ty", Proceeding of the IEEE/ICDE, pp. 1-12, Atlanta, GA, USA, April 2006 (doi: 10.1109/ICDE.20­06­.1).

[6]   N. Li, T. Li, S. Venkatasubramania, "t-Closeness: Privacy beyond k-anonymity and -diversity", Proceeding of the IEEE/ICFE, pp. 106–115, Istanbul, Turkey, April 2007 (doi: 10.1109/ICDE.2007.367856).

[7]   M. Yuan, L. Chen, P. S. Yu, T. Yu, "Protecting sensitive labels in social network data anonymization", IEEE Trans. on Knowledge and Data Engineering, vol. 25, no. 3, pp. 633–647, March 2013 (doi: 10.1109/TKDE.2­01­1­.259).

[8]   J. Casas-Roma, J.C.J. Herrera-Joancomartí, V. Torra, "A survey of graph-modification techniques for privacy-preserving on networks", Artificial Intelligence Review, vol. 47, no. 3, pp. 341–366, May 2017 (doi: 10.1007/s10462-016-9484-8).

[9]   J. Casas-Roma, J. Herrera-Joancomartí, V. Torra, "k-Degree anonymity and edge selection: improving data utility in large networks", Knowledge and Information Systems, vol. 50, no. 2, pp. 447–474, April 2017 (doi: 10.1007/s10115-016-0947-7).

[10] J. Abawajy, M. I. Ninggal, T. Herawan, "Privacy preserving social network data publication", IEEE Communications Surveys and Tutorials, vol. 18, no. 3, pp. 1974-1997, March 2016 (doi: 10.1109/COM­ST.2­016.2­5­33668).

[11] E. Zheleva, L. Getoor, "Preserving the privacy of sensitive relationships in graph data", Lecture Notes in Computer Science, vol. 4890, pp. 153–171, Berlin, Heidelberg, 2008 (doi: 10.1007/978-3-540-78478-4_9).

[12] A. Campan, T.M. Truta, "Data and structural K-anonymity in social networks", Lecture Notes in Computer Science, vol. 5456, pp. 33–54, Berlin, Heidelberg, 2009 (doi: 10.1007/978-3-642-01718-6_4).

[13] S. Chester, B. Kapron, G. Ramesh, G. Srivastava, A. Thomo, S. Venkatesh, "κ-Anonymization of social networks by vertex addition", Proceeding of the CEUR, vol. 789, pp. 107–116, Vienna, Austria, Jan. 2011.

[14] M. Kiabod, M.N. Dehkordi, B. Barekatain, "TSRAM : A time-saving k-degree anonymization method in social network", Expert Systems with Applications, vol. 125, pp. 378–396, July 2019 (doi: 10.1016/j.es­wa.20­19.0­1.059).

[15] M. Kiabod, M. Naderi, B. Barekatain, "A fast graph modification method for social network anonymization", Expert Systems with Applications, vol. 180, pp. 1-19 Article Number: 115148, Oct. 2021 (doi: 10.1016/j.eswa.2021.1­15148).

[16] S. Chester, B.M. Kapron, G. Ramesh, G. Srivastava, A. Thomo, S. Venkatesh, "Why waldo befriended the dummy? k-Anonymization of social networks with pseudo-nodes", Social Network Analysis and Mining, vol. 3, no. 3, pp. 381–399, Sept. 2013 (doi: 10.1007/s13278-012-0084-6).

[17] T. Ma, Y. Zhang, J. Cao, J. Shen, M. Tang, Y. Tian, A. Al-Dhelaan, M. Al-Rodhaan, "KDVEM: a k-degree anonymity with vertex and edge modification algorithm", Computing, vol. 97, no. 12, pp. 1165–1184, Dec. 2015 (doi: 10.1007/s00607-015-0453-x).

[18] R. Bredereck, V. Froese, S. Hartung, A. Nichterlein, R. Niedermeier, N. Talmon, "The complexity of degree anonymization by vertex addition", Theoretical Computer Science, vol. 607, pp. 16–34, Nov. 2015 (doi: 10.101­6­/j.­tcs.2015.07.004).

[19] K.R. Macwan, S.J. Patel, "k-degree anonymity model for social network data publishing", Advances in Electrical and Computer Engineering, vol. 17, no. 4, pp. 117–124, Jan. 2017 (doi: 10.4316/AEC­E.­201­7.­04­015).

[20] A. Sharma, S. Pathak, "Enhancement of k - anonymity algorithm for privacy preservation in social media", Interna­tional Journal of Engineering and Technology, vol. 7, pp. 40–45, June 2018 (doi: 10.14419/ijet.v7i2­.27.1­1747).

[21] F. Rousseau, J. Casas-Roma, M. Vazirgiannis, "Community-preserving anonymization of graphs", Knowled­ge and Information Systems, vol. 54, no. 2, pp. 315–343, May 2018 (doi: 10.1007/s10115-017-1064-y).

[22] M. Siddula, L. Li, Y. Li, "An empirical study on the privacy preservation of online social networks", IEEE Access, vol. 6, pp. 19912–19922, April 2018 (doi: 10.1109/ACCESS.2018.2822693).

[23] X. Zhang, J. Liu, J. Li, L. Liu, "Large-scale dynamic social network directed graph k-in&out-degree anonymity algorithm for protecting community structure", IEEE Access, vol. 7, pp. 108371-108383,  Aug. 2019 (doi: 10.1109/ACCESS.2019.2933151).

[24] M. Siddula, Y. Li, X. Cheng, Z. Tian, Z. Cai, "Anonymization in online social networks based on enhanced equi-cardinal clustering", IEEE Trans. on Computational Social Systems, vol. 6, no. 4, pp. 809–820, July 2019 (doi: 10.1109/TCSS.2019.2928324).

[25] S. Bourahla, M. Laurent, Y. Challal, "Privacy preservation for social networks sequential publishing", Computer Networks, vol. 170, Article Number: 107106, April 2020 (doi: 10.1016/j.comnet.2020.107106).

[26] M. Bi, Y. Wang, Z. Cai, X. Tong, "A privacy-preserving mechanism based on local differential privacy in edge computing", China Communications, vol. 17, no. 9, pp. 50–65, March 2020 (doi: 10.23919/JCC.2020.0­9.005).

[27] C. Bazgana, P. Cazalsa, J. Chlebíková, "Degree-anonymization using edge rotations", Theoretical Computer Science, vol. 873, pp. 1–15, June 2021 (doi: 10.1016/j.tcs.2021.04.020).

[28] R. Al-asbahi, "Structural anonymity for privacy protection in social network", International Journal of Scientific and Research Publications, vol. 11, no. 6, pp. 102–107, June 2021 (doi: 10.29322/IJSRP.11.06.2­021.p11­414).

[29] A. Singh, M. Singh, D. Bansal, S. Sofat, "Optimised K-anonymisation technique to deal with mutual friends and degree attacks", International Journal of Information and Computer Security, vol. 14, no. 3–4, pp. 281-299, April 2021 (doi: 10.1504/IJICS.2021.114706).

[30] N. Xiang, X. Ma, "TKDA: An improved method for k-degree anonymity in social graphs", Proceeding of the IEEE/ISCC, pp. 1-6, Rhodes, Greece, June/July 2022 (doi: 10.1109/ISCC55528.2022.9912964).

[31] X. Ren, D. Jiang, "A personalized α,β,l,k-anonymity model of social network for protecting privacy", Wireless Communications and Mobile Computing, vol. 2022, pp. 1-11, Jan. 2022 (doi: 10.1155/2022/7187528).

[32] A. Majeed, S. Khan, S.O. Hwang, "A comprehensive analysis of privacy-preserving solutions developed for online social networks", Electronics (Switzerland), vol. 11, no. 13, pp. 1–37, June 2022 (doi: 10.3390/el­ectronics11131931).

[33] A. Karimi-Rizi, M. Naderi-Dehkordi, N. Nematbakhsh, "Publishing health information without distortion while balancing desired privacy-preserving and utility", Journal of Intelligent Procedures in Electrical Technology, vol. 13, no. 50, pp. 47-66, Sept. 2022 (dor: 20.1001.1.23223871.1401.13.50.3.4).

[34] J. Casas-roma, J. Salas, F. D. Malliaros, "k-Degree anonymity on directed networks", Knowledge and Information Systems, vol. 61, pp. 1743–1768, Dec. 2019 (doi: 10.1007/s10115-018-1251-5).

[35] L. Zheng, H. Yue, Z. Li, X. Pan, M. Wu, F. Yang, "k-anonymity location privacy algorithm based on clustering", IEEE Access, vol. 6, pp. 28328–28338, Dec. 2018 (doi: 10.1109/ACCESS.2017.2780111).

[36] Y. Lu, X. Hou, X. Chen, "A novel travel-time based similarity measure for hierarchical clustering ustering", Neurocomputing, vol. 173, pp. 3–8, Jan. 2016 (doi: 10.1016/j.neucom.2015.01.090).

[37] D. Lusseau, K. Schneider, O. J. Boisseau, P. Haase, E. Slooten, S. M. Dawson, "The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations: Can geographic isolation explain this unique trait?", Behavioral Ecology and Sociobiology, vol. 54, no. 4, pp. 396–405, June 2003 (doi: 10.1007/s00265-003-0651-y).

[38] J. Leskovec, J. Kleinberg, C. Faloutsos, "Graph evolution: densification and shrinking diameters", ACM Trans. on Knowledge Discovery from Data, vol. 1, no. 1, Article Number: 2, April 2006 (doi: 10.1145/121729­9.12­17301).

[39] J. Leskovec, K.J. Lang, M.W. Mahoney, "Community structure in large networks : natural cluster sizes and the absence of large well-defined clusters", Internet Mathematics, vol. 6, no. 1, pp. 29--123, Nov. 2009 (doi: 10.1080/15427951.2009.10129177).

[40] J. Yang, J. Leskovec, "Defining and evaluating network communities based on ground-truth", Proceeding of the IEEE/ICDM, pp. 745–754, Brussels, Belgium, Oct. 2012 (doi: 10.48550/arXiv.1205.6233).

[41] L. Danon, A. Díaz-Guilera, J. Duch, A. Arenas, D. Albert, J. Duch, "Comparing community structure identification", Journal of Statistical Mechanics: Theory and Experiment, vol. 09008, no. 9, pp. 219–228, Sept. 2005 (doi: 10.1088/1742-5468/2005/09/P09008).