A Novel Graph-modification Technique for User Privacy-preserving on Social Networks
DOI:
https://doi.org/10.26636/jtit.2019.134319Keywords:
graph-modification, social networks, privacypreserving publication of data, graph anonymization, database securityAbstract
The growing popularity of social networks and the increasing need for publishing related data mean that protection of privacy becomes an important and challenging problem in social networks. This paper describes the (k,l k,l k,l)-anonymity model used for social network graph anonymization. The method is based on edge addition and is utility-aware, i.e. it is designed to generate a graph that is similar to the original one. Different strategies are evaluated to this end and the results are compared based on common utility metrics. The outputs confirm that the naive idea of adding some random or even minimum number of possible edges does not always produce useful anonymized social network graphs, thus creating some interesting alternatives for graph anonymization techniques.
Downloads
References
[1] V. V. H. Pham, S. Yu, K. Sood, and L. Cui, “Privacy issues in social networks and analysis: a comprehensive survey”, IET Networks, vol. 7, no. 2, pp. 74–84, 2018. DOI: https://doi.org/10.1049/iet-net.2017.0137
View in Google Scholar
[2] B. Palanisamy, L. Liu, Y. Zhou, and Q. Wang, “Privacy-preserving publishing of multilevel utility-controlled graph datasets”, ACM Trans. on Internet Technol., vol. 18, no. 2, pp. 1–21, 2018. DOI: https://doi.org/10.1145/3125622
View in Google Scholar
[3] P. Joshi and C. Kuo, “Security and privacy in online social networks: A survey”, in Proc. IEEE Int. Conf. on Multim. and Expo ICME 2011, Barcelona, Spain, 2011. DOI: https://doi.org/10.1109/ICME.2011.6012166
View in Google Scholar
[4] R. Gross and A. Acquisti, “Information revelation and privacy in online social networks”, in WPES ’05: Proceedings of the 2005 ACM Workshop on Privacy in the Electronic Society, Aleksandria, VA, USA, 2005, pp. 71–80 (ISBN: 1-59593-228-3). DOI: https://doi.org/10.1145/1102199.1102214
View in Google Scholar
[5] B. Krishnamurthy and C. Wills, “Characterizing privacy in online social networks”, in Proc. of the 1st Worksh. on Online Soc. Netw., Seattle, WA, USA, 2008, pp. 37–42. DOI: https://doi.org/10.1145/1397735.1397744
View in Google Scholar
[6] T. Truta, M. Tsikerdekis, and S. Zeadally, “Privacy in social networks”, in Privacy in a Digital, Networked World, S. Zeadally and M. Badra, Eds. Springer, 2015, pp. 263–289 (ISBN: 978-3-319-08470-1). DOI: https://doi.org/10.1007/978-3-319-08470-1_12
View in Google Scholar
[7] B. Zhou, J. Pei, and W. Luk, “A brief survey on anonymization techniques for privacy preserving publishing of social network data”, ACM SIGKDD Explor. Newslett., vol. 10l no. 2, pp. 12–22, 2008. DOI: https://doi.org/10.1145/1540276.1540279
View in Google Scholar
[8] E. Zheleva and L. Getoor, “Preserving the privacy of sensitive relationships in graph data”, in Privacy, Security, and Trust in KDD. First ACM SIGKDD International Workshop, PinKDD 2007, San Jose, CA, USA, August 12, 2007, Revised Selected Papers. Springer, 2008, pp. 153–171. DOI: https://doi.org/10.1007/978-3-540-78478-4_9
View in Google Scholar
[9] R. Trujillo-Rasua and I. G. Yero, “k-metric antidimension: A privacy measure for social graphs”, Inform. Sciences, vol. 328, pp. 403–417, 2016. DOI: https://doi.org/10.1016/j.ins.2015.08.048
View in Google Scholar
[10] C.-H. Tai, P. S. Yu, D.-N. Yang, and M.-S. Chen, “Privacypreserving social network publication against friendship attacks”, in Proc. 17th ACM SIGKDD Int. Conf. on Knowl. Discov. and Data Mining KDD’11, San Diego, CA, USA, 2011, pp. 1262–1270. DOI: https://doi.org/10.1145/2020408.2020599
View in Google Scholar
[11] W. Wentao, X. Yanghua, W. Wei, H. Zhenying, and W. Zhihui, “k-symmetry model for identity anonymization in social networks”, in Proc. 13th Int. Conf. on Ext. Database Technol. EDBT’10, Lausanne, Switzerland, 2010, pp. 111–122. DOI: https://doi.org/10.1145/1739041.1739058
View in Google Scholar
[12] J. Casas-Roma, J. Herrera-Joancomart´ ı, and V. Torra, “An algorithm for k-degree anonymity on large networks”, in Proc. IEEE/ACM Int. Conf. on Adv. in Soc. Netw. Anal. and Mining ASONAM 2013, Niagara Falls, ON, Canada, 2013, pp. 671–675. DOI: https://doi.org/10.1145/2492517.2492643
View in Google Scholar
[13] T. Tassa and D. Cohen, “Anonymization of centralized and distributed social networks by sequential clustering”, IEEE Trans. on Knowl. and Data Engin., vol. 25, no. 2, pp. 311–324, 2013. DOI: https://doi.org/10.1109/TKDE.2011.232
View in Google Scholar
[14] B. Fung, Y. Jin, J. Li, and J. Liu, “Anonymizing social network data for maximal frequent-sharing pattern mining”, in Recommendation and Search in Social Networks, ¨ O. Ulusoy, A. Uz Tansel, and E. Arkun, Eds. Springer, 2015, pp. 77–100. DOI: https://doi.org/10.1007/978-3-319-14379-8_5
View in Google Scholar
[15] H. Jiang, “A novel clustering-based anonymization approach for graph to achieve privacy preservation in social network”, in Proc. Int. Conf. on Adv. in Mechan. Engin. and Indust. Inform. AMEII 2015, Zhengzhou, China, 2015, pp. 545–549. DOI: https://doi.org/10.2991/ameii-15.2015.102
View in Google Scholar
[16] Z. Shiwen, L. Qin, and L. Yaping, “Anonymizing popularity in online social networks with full utility”, Future Gener. Comp. Syst., vol. 72, pp. 227–238, 2017. DOI: https://doi.org/10.1016/j.future.2016.05.007
View in Google Scholar
[17] W. Yazhe, X. Long, B. Zheng, and K. C. Lee, “Utility-oriented k-anonymization on social networks”, in Database Systems for advanced Applications. 16th International Conference, DASFAA 2011, Hong Kong, China, April 22-25, 2011, Proceedings, Part I, J. X. Yu, M. H. Kim, and R. Unland, Eds. Springer, 2011, pp. 78–92.
View in Google Scholar
[18] C. Watanabe, T. Amagasa, and L. Liu, “Privacy risks and countermeasures in publishing and mining social network data”, in Proc. 7th Int. Conf. on Collab. Comput.: Network., Appl. and Worksharing CollaborateCom 2011, Orlando, FL, USA, 2011. DOI: https://doi.org/10.4108/icst.collaboratecom.2011.247177
View in Google Scholar
[19] T. Feder, S. U. Nabar, and E. Terzi, “Anonymizing graphs”, arXiv:0810.5578 [cs.DB].
View in Google Scholar
[20] K. Stokes and V. Torra, “Reidentification and k-anonymity: a model for disclosure risk in graphs”, Soft Comput., vol. 16, no. 10, pp. 1657–1670, 2012. DOI: https://doi.org/10.1007/s00500-012-0850-4
View in Google Scholar
[21] J. Cheng, A. W.-C. Fu, and J. Liu, “K-isomorphism: privacy preserving network publication against structural attacks”, in Proc. of the ACM SIGMOD Int. Conf. on Manag. of Data SIGMOND’10, Indianapolis, Indiana, USA, 2010, 459–470. DOI: https://doi.org/10.1145/1807167.1807218
View in Google Scholar
[22] K. Liu and E. Terzi, “Towards identity anonymization on graphs”, in Proc. ACM SIGMOD Int. Conf. on Manag. of Data SIGMOND’08, Vancouver, Canada, 2008, pp. 93–106. DOI: https://doi.org/10.1145/1376616.1376629
View in Google Scholar
[23] B. Zhou and J. Pei, “The k-anonymity and l-diversity approaches for privacy preservation in social networks against neighborhood attacks”, Knowl. and Inform. Syst., vol. 28, no. 1, p. 47–77, 2011. DOI: https://doi.org/10.1007/s10115-010-0311-2
View in Google Scholar
[24] L. Zou, L. Chen, and M. ¨Ozsu, “K-automorphism: a general framework for privacy preserving network publication”, in Proc. of the VLDB Endowment, vol. 2, no. 1, pp. 946–957, 2009. DOI: https://doi.org/10.14778/1687627.1687734
View in Google Scholar
[25] M. I. H. Ningga and J. H. Abawajy, “Utility-aware social network graph anonymization”, J. of Netw. and Comp. Appl., vol. 56, pp. 137–148, 2015. DOI: https://doi.org/10.1016/j.jnca.2015.05.013
View in Google Scholar
[26] J. Casas-Roma, J. Herrera-Joancomartí, and V. Torra, “A survey of graph-modification techniques for privacy-preserving on network”, Artif. Intell. Rev., vol. 47, no. 3, pp. 341–366, 2017. DOI: https://doi.org/10.1007/s10462-016-9484-8
View in Google Scholar
[27] M. Hay, G. Miklau, D. Jensen, P. Weis, and S. Srivastava, “Anonymizing social networks”, Tech. Rep. no. 07-19, Computer Science Department, University of Massachusetts Amherst, 2007.
View in Google Scholar
[28] K. Stokes and V. Torra, “On some clustering approaches for graphs”, in Proc. IEEE Int. Conf. on Fuzzy Syst. FUZZ-IEEE 2011, Taipei, Taiwan, 2011, pp. 409–415. DOI: https://doi.org/10.1109/FUZZY.2011.6007447
View in Google Scholar
[29] J. Casas-Roma, “Privacy-preserving on graphs using randomization and edge-relevance”, in Modeling Decisions for Artificial Intelligence 11th International Conference, MDAI 2014, Tokyo, Japan, October 29-31, 2014. Proceedings, V. Torra, Y. Narukawa, Y. Endo, Eds. LNCS, vol. 8825. Springer, 2014, pp. 204–216. DOI: https://doi.org/10.1007/978-3-319-12054-6_18
View in Google Scholar
[30] P. Samarati, “Protecting respondents’ identities in microdata release”, IEEE Trans. Knowl. Data Engin. (TKDE), vol. 13, no. 6, pp. 1010–1027, 2001. DOI: https://doi.org/10.1109/69.971193
View in Google Scholar
[31] L. Sweeney, “k-anonymity: a model for protecting privacy”, Int. J. of Uncert., Fuzziness Knowl.-Based Syst. (IJUFKS), vol. 10, no. 5, pp. 557–570, 2002. DOI: https://doi.org/10.1142/S0218488502001648
View in Google Scholar
[32] B. Zhou and J. Pei, “Preserving privacy in social networks against neighborhood attacks”, in Proc. IEEE 24th Int. Conf. on Data Engin., Cancun, Mexico, 2008, pp. 506–515. DOI: https://doi.org/10.1109/ICDE.2008.4497459
View in Google Scholar
[33] Y. Wang, L. Xie, B. Zheng, and K. C. K. Lee, “High utility k-anonymization for social network publishing”, Knowl. and Inform. Syst., vol. 41, no. 3, pp. 697–725, 2014. DOI: https://doi.org/10.1007/s10115-013-0674-2
View in Google Scholar
[34] X. He, J. Vaidya, B. Shafiq, N. Adam, and V. Atluri, “Preserving privacy in social networks: a structure-aware approach”, in Proc. IEEE/WIC/ACM Int. Joint Conf. on Web Intell. and Intell. Agent Technol. WI-IAT’09, Milan, Italy, 2009, pp. 47–54. DOI: https://doi.org/10.1109/WI-IAT.2009.108
View in Google Scholar
[35] G. Kossinets and D. J. Watts, “Empirical analysis of an evolving social network”, Science, vol. 311, no. 5757, pp. 88–90, 2006. DOI: https://doi.org/10.1126/science.1116869
View in Google Scholar
[36] R. Mortazavi and S. H. Erfani, “An effective method for utility preserving social network graph anonymization based on mathematical modeling”, Int. J. of Engin., vol. 31, no. 10, pp. 1624–1632, 2018. DOI: https://doi.org/10.5829/ije.2018.31.10a.03
View in Google Scholar
[37] M. Girvan and M. E. J. Newman, “Community structure in social and biological networks”, Proc. of the Nat. Acad. of Sci. USA, vol. 99, no. 12, pp. 7821–7826, 2002. DOI: https://doi.org/10.1073/pnas.122653799
View in Google Scholar
[38] L. J. Lu and M. Zhang, “Edge betweenness centrality”, in Encyclopedia of Systems Biology, W. Dubitzky, O. Wolkenhauer, K.-H. Cho, H. Yokota, Eds. New York, NY: Springer, 2013, pp. 647–648. DOI: https://doi.org/10.1007/978-1-4419-9863-7_874
View in Google Scholar
[39] CPLEX, GAMS. The solver manuals, GAME/CPLEX; 1996.
View in Google Scholar
Downloads
Submitted
Published
Issue
Section
License
Copyright (c) 2019 Journal of Telecommunications and Information Technology
This work is licensed under a Creative Commons Attribution 4.0 International License.
