A Novel Graph-modification Technique for User Privacy-preserving on Social Networks

• Autorzy: Hamideh Erfani Seyedeh , Mortazavi Reza

Identyfikatory

DOI

10.26636/jtit.2019.134319

• Języki publikacji: EN

Abstrakty

EN

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 na¨ıve 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.

Słowa kluczowe

EN

graph modification; social networks; privacypreserving publication of data; graph anonymization; database security

• Wydawca: Instytut Łączności - Państwowy Instytut Badawczy
• Czasopismo: Journal of Telecommunications and Information Technology
• Rocznik: 2019
• Tom: nr 3
• Strony: 27--38
• Opis fizyczny: Bibliogr. 39 poz., rys., tab.

Twórcy

autor

Hamideh Erfani Seyedeh

• School of Engineering, Damghan University, 36716-41167, Damghan, Iran

autor

Mortazavi Reza

• School of Engineering, Damghan University, 36716-41167, Damghan, Iran

Bibliografia

• [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: 10.1049/iet-net.2017.0137).
• [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: 10.1145/3125622).
• [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: 10.1109/ICME.2011.6012166).
• [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).
• [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: 10.1145/1397735.1397744).
• [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).
• [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: 10.1145/1540276.1540279).
• [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: 10.1007/978-3-540-78478-4 9).
• [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: 10.1016/j.ins.2015.08.048).
• [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: 10.1145/2020408.2020599).
• [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: 10.1145/1739041.1739058).
• [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: 10.1145/2492517l2492643).
• [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: 10.1109/TKDE.2011.232).
• [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: 10.1007/978-3-319-14379-8 5).
• [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: 10.2991/ameii-15.2015.102).
• [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: 10.1016/j.future.2016.05.007).
• [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 (doi: 10.1007/978-3-642-20149-3 8).
• [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: 10.4108/icst.collaboratecom.2011.247177).
• [19] T. Feder, S. U. Nabar, and E. Terzi, “Anonymizing graphs”, arXiv:0810.5578 [cs.DB].
• [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: 10.1007/s00500-012-0850-4).
• [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: 10.1145/1807167.1807218).
• [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: 10.1145/1376616.3776629).
• [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: 10.1007/s10115-010-0311-2).
• [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: 10.14778/1687627.1687734).
• [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: 10.1016/j.jnca.2015.05.013).
• [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: 10.1007/s10462-016-9484-8)
• [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
• [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: 10.1109/FUZZY.2011.6007447).
• [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: 10.1007/978-3-319-12054-6 18).
• [30] P. Samarati, “Protecting respondents’ identities in microdata release”, IEEE Trans. Knowl. Data Engin. (TKDE), vol. 13, no. 6, pp. 1010–1027, 2001 (doi: 10.1109/69.971193).
• [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: 10.1142/S0218488502001648).
• [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: 10.1109/ICDE.2008.4497459).
• [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: 10.1007/s10115-013-0674-2).
• [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: 10.1109/WI-IAT.2009.108).
• [35] G. Kossinets and D. J. Watts, “Empirical analysis of an evolving social network”, Science, vol. 311, no. 5757, pp. 88–90, 2006 (doi: 10.1126/science.1116869).
• [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
• [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: 10.1073/pnas.122653799).
• [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: 10.1007/978-1-4419-9863-7 874).
• [39] CPLEX, GAMS. The solver manuals, GAME/CPLEX; 1996 [Online]. Available: https://www.gams.com/latest/docs/S CPLEX.html

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2019).