Abstract Online Social Networks (OSNs) data are published to be used for the purpose of analysis in scientific research. Yet, offering such data in its crude structure raises serious privacy concerns. An adversary may attack the privacy of certain victims easily by collecting local background knowledge about individuals in a social network such as information about its neighbors. The subgraph attack that is based on frequent pattern mining and members’ background information may be used to breach the privacy in the published social networks. Most of the current anonymization approaches do not guarantee the privacy preserving of identities from attackers in case of using the frequent pattern mining and background knowledge. In this paper, a secure k-anonymity algorithm that protects published social networks data against subgraph attacks using background information and frequent pattern mining is proposed. The proposed approach has been implemented and tested on real datasets. The experimental results show that the anonymized OSNs can preserve the major characteristics of original OSNs as a tradeoff between privacy and utility.

References

[1] Abawajy J., Ninggal M., and Herawan T., “Vertex Re‐Identification Attack Using Neighbourhood‐Pair Properties,” Concurrency and Computation: Practice and Experience, vol. 28, no. 10, pp. 2906-2919, 2015.

[2] Adamic L. and Glance N., “The Political Blogosphere And The 2004 US Election: Divided They Blog,” in Proceedings of the 3rd International Workshop on Link Discovery, Chicago, pp. 36-43, 2005.

[3] Aggarwal C., Mining Graph Data, Springer, 2015.

[4] Anusha K. and Ramana K., “Degree Smoothing On Social Networks against Frequent Shared Patterns,” International Journal of Advanced Research in Science and Technology, vol. 4, no. 4, pp. 435-439, 2015. 0 2000 4000 6000 8000 10000 13579Transitivity Distribution Frequency Transitivity DistributionK=10,N=5000 Original Anonymized 0 5000 10000 15000 20000 13579Transitivity Distribution Frequency Transitivity DistributionK=10,N=10000 Original Anonymized 0 100 200 300 400 500 123456789Shortest Path lengths Frequency Shortest Path lengthsK=5,N=5000 Anonymized Original 0 50 100 150 200 250 300 350 123456789 Shortest path lengths Frequency Shortest Path lengthsK=5,N=10000 Anonymized Original 0 100 200 300 400 123456789 Shortest path lengths Frequency Shortest Path lengthsK=10,N=5000 Anonymized Original 0 100 200 300 400 123456789Shortest path lengths Frequency Shortest Path lengthsK=10,N=10000 Anonymized Original 0 2000 4000 6000 8000 10000 135791113 Degree Distribution Frequancy DegreeDistribution k=15 k=10 k=5 Original Securely Publishing Social Network Data 701

[5] Backstrom L., Dwork C., and Kleinberg J., “Wherefore Art Thou R3579x?: Anonymized Social Networks, Hidden Patterns, and Structural Steganography,” in Proceedings of the 16th International Conference on World Wide Web, Banff, pp. 181-190, 2007.

[6] Campan A., Alufaisan Y., Truta T., and Richardson T., “Preserving Communities in Anonymized Social Networks,” Transactions on Data Privacy, vol. 8, no. 1, pp. 55-58, 2015.

[7] Chester S., Gaertner J., Stege U., and Venkatesh S., “Anonymizing Subsets of Social Networks with Degree Constrained Subgraphs,” in Proceedings of IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, Istanbul, pp. 418-422, 2012.

[8] Deshpande A., “A Review on Privacy Priserving Data Publishing of Social Network. Advanced Technologies in Computing and Networking,” in Proceedings of National Conference on Advanced Technologies in Computing and Networking, pp. 432-434, 2015.

[9] Emelda C. and Jaya R., “Distributed Data Anonymization with Hiding Sensitive Node Labels,” International Journal of Innovative Research in Advanced Engineering, vol. 1, no. 8, pp. 392-396, 2015.

[10] Fung B., Jin Y., and Li J., “Preserving Privacy and Frequent Sharing Patterns for Social Network Data Publishing,” in Proceedings of IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, Niagara Falls, pp. 479-485, 2013.

[11] Hay M., Miklau G., Jensen D., Towsley D., and Weis P., “Resisting Structural Re-Identification in Anonymized Social Networks,” Proceedings of the VLDB Endowment, vol. 1, no. 1, pp. 102- 114, 2008.

[12] Kossinets G., Kleinberg J., and Watts D., “The Structure Of Information Pathways In A Social Communication Network,” in Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Las Vegas, pp. 435-443, 2008.

[13] Leskovec J., Backstrom L., Kumar R., and Tomkins A., “Microscopic Evolution of Social Networks,” in Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Las Vegas, pp. 462-470, 2008.

[14] Li G. and Wang Y., “A Privacy-Preserving Classification Method Based on Singular Value Decomposition,” The International Arab Journal of Information Technology, vol. 9, no. 6, pp. 529- 534, 2012.

[15] Liu C. and Mittal P., “LinkMirage: How to Anonymize Links in Dynamic Social Systems,” Technical Report, Cornell Univercity, 2015.

[16] Liu K. and Terzi E., “Towards identity Anonymization on Graphs,” in Proceedings of the ACM SIGMOD International Conference on Management of Data, Vancouver, pp. 93-106, 2008.

[17] Prashanth R. and Shaik M., “Sensitive Label Privacy Protection on Social Network Data,” IOJETR Transactions on Data Mining, pp. 1131- 1140, 2014.

[18] Song Y., Karras P., Xiao Q., and Bressan S., “Sensitive Label Privacy Protection on Social Network Data,” in Proceedings of International Conference on Scientific and Statistical Database Management, Berlin, pp. 562-571, 2012.

[19] Tassa T. and Cohen D., “Anonymization of centralized and Distributed Social Networks by Sequential Clustering,” IEEE Transactions on Knowledge and Data Engineering, vol. 25, no. 2, pp. 311-324, 2013.

[20] Wang P., Zhang X., and Huang P., “Privacy Preservation in Social Network Based on Anonymization Techniques,” Computer Modelling and New Technologies, vol. 18, pp. 249-253, 2014.

[21] Wu X., Ying X., Liu K., and Chen L., “A Survey of Privacy-Preservation of Graphs and Social Networks,” in Proceedings of Managing and Mining Graph Data, Boston, pp. 421-453, 2010.

[22] Ying X. and Wu X., “on Link Privacy in Randomizing Social Networks,” Knowledge and Information Systems, vol. 28, no. 3, pp. 645-663, 2011.

[23] Ying X. and Wu X., “Randomizing Social Networks: a Spectrum Preserving Approach,” in Proceedings of the SIAM International Conference on Data Mining, pp. 739-750, 2008.

[24] Zakerzadeh H., Aggarwal C., and Barker K., “Big Graph Privacy,” in Proceedings of the EDBT/ICDT Joint Conference, Brussels, pp. 255- 262, 2015.

[25] Zhou B., Pei J., and Luk W., “A Brief Survey on Anonymization Techniques for Privacy Preserving Publishing of Social Network Data,” ACM SIGKDD Explorations Newsletter, vol. 10, no. 2, pp. 12-22, 2008.

[26] Zhou B. and Pei J., “Preserving Privacy in Social Networks Against Neighborhood Attacks,” in Proceedings of the IEEE 24th International Conference on Data Engineering, Washington, pp. 506-515, 2010. 702 The International Arab Journal of Information Technology, Vol. 16, No. 4, July 2019 Emad Elabd Ph.D., Associate Professor, Department of Information Systems, Menoufia University, Egypt. He got his Ph.D. in the field of Web services compliance over high-level specifications at LIRIS, University Lyon1, France, 2011. He received bachelor´s degrees in Electronic Engineering from Menoufia University, Egypt where he did his master’s studies in computer science also. His research interests include Web services modeling and analysis with access control and time aspects, Web services (specification, composition), Semantic Web, privacy, LBS, and Information Retrieval. Hatem AbdullKader obtained hisBSc and MSC degrees, both inelectrical engineering from the Alexandria University, Faculty ofEngineering, Egypt, 1990 and 1995,respectively. He obtained his PhDdegree in electrical engineering alsofrom Faculty of Engineering, Alexandria University,Faculty of Engineering, Egypt in 2001. His areas ofinterest are data security, Web applications andartificial intelligence, and he is specialized in neuralnetworks. He is currently a professor in theInformation Systems Department, Faculty ofComputers and Information, Menoufia University,Egypt, since 2004. Waleed Ead Lecturer, Information System department, Faculty of Computers and Information, Beni- suef university,Egypt. His BSc and MSc degree in Information system from Zagazig and menoufia university, respectively. He is a Ph.D candidate at menoufia university. His main research interests is privacy preserving in data publishong.