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.
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.
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.
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, Alexandria, VA, USA, 2005, pp. 71–80 (ISBN: 1-59593-228-3).
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.
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).
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. 10, no. 2, pp. 12–22, 2008.
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.
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.
View in Google Scholar
[10] C.-H. Tai, P. S. Yu, D.-N. Yang, and M.-S. Chen, “Privacy-preserving 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.
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.
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.
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.
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, Ö. Ulusoy, A. Uz Tansel, and E. Arkun, Eds. Springer, 2015, pp. 77–100.
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.
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.
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.
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.
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 SIGMOD’10, Indianapolis, IN, USA, 2010, pp. 459–470.
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 SIGMOD’08, Vancouver, Canada, 2008, pp. 93–106.
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, pp. 47–77, 2011.
View in Google Scholar
[24] L. Zou, L. Chen, and M. T. Özsu, “K-automorphism: a general framework for privacy preserving network publication”, in Proc. of the VLDB Endowment, vol. 2, no. 1, pp. 946–957, 2009.
View in Google Scholar
[25] M. I. H. Ninggal and J. H. Abawajy, “Utility-aware social network graph anonymization”, J. of Netw. and Comp. Appl., vol. 56, pp. 137–148, 2015.
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.
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 [Online]. Available: https://scholarworks.umass.edu/cgi/viewcontent.cgi?article=1175&context=cs_faculty_pubs.
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.
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, and Y. Endo, Eds. LNCS, vol. 8825. Springer, 2014, pp. 204–216.
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.
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.
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.
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.
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.
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.
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 [Online]. Available: http://www.ijeir.info/article_81694_e3849caf4384bbe53aed25f3afd8d93e.pdf.
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.
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, and H. Yokota, Eds. New York, NY: Springer, 2013, pp. 647–648.
View in Google Scholar
[39] CPLEX, GAMS. The solver manuals, GAMS/CPLEX, 1996 [Online]. Available: https://www.gams.com/latest/docs/S_CPLEX.html.
View in Google Scholar
Downloads
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.