An Improved Method for Graph Data Anonymization with Emphasis on Preserving the Average Path length

Document Type : Original Article

Authors

damghan university

Abstract

In recent decades, in view of the widespread use of graph data in different applications, for instance     in social networks, communications networks, etc. many researchers have investigated different                anonymization approaches for such data. Although relational data anonymization is mature enough, graph data anonymization is a challenging and relatively new field of research. One of the most important     anonymization models against identity disclosure risk in graph data addresses the number of links a node’s neighbors have, in the graph. In this paper, an improved method is proposed that realizes this model using both edge addition and deletion to the original graph. The application of the method to a number of        different real-world graphs confirms that the method can produce more useful graphs in terms of one of the most important characteristics in such data, i.e., the Average Path Length in the graph and graph structure will undergo less change.
 

Keywords

References

   [1]      A. Padrola and V. Muntés-Mulero, “Graph anonymization via metric embeddings: Using classical anonymization for graphs,” Intelligent Data Analysis, pp. 365–388, 2014.##
   [2]      Sh. Ji, T. Wang, J. Chen, W. Li, P. Mittal, and R. Beyah, “De-SAG: On the De-anonymization of Structure-Attribute Graph Data,” IEEE Transactions on Dependable and Secure Computing, pp. 1-14, 2016.##
   [3]      A. Shaharkhiz and H. Shahriari, “A method for preserving privacy in published multi-relational social networks,” International Conference on Knowledge Management and Information Sharing - KMIS 2011, France, 2011.##
   [4]      E. Sargolzaee and M. Abdollahi Azgomi, “Preserving the Privacy of Published Social Networks Data Based on Graph Modification,” Proc. of the 10th International ISC Conference on Information Security and Cryptology (ISCISC'13), pp. 30-37, 2013. (in Persian)##.
   [5]      F. Rousseau, J. Casas-Roma, and M. Vazirgiannis, “Community-preserving anonymization of graphs,” Knowledge and Information Systems, pp. 315-343, 2017.##
   [6]      T. Feder, S. U. Nabar and E. Terzi, “Anonymizing graphs,” CoRRabs. 0810/5578, 2008.##
   [7]      M. Hay, G. Miklau, D. Jensen, P. Weis, and S. Srivastava, “Anonymizing social networks,” Technical Report No.    07-19. Computer Science Department, University of Massachusetts Amherst, Amherst, 2007.##
   [8]      X. Ying, K. Pan, X. Wu, and L. Guo, “Comparisons of randomization and k-degree anonymization schemes for privacy preserving social network publishing,” In: Workshop on social network mining and analysis, pp. 1–10, 2009##
   [9]      X. Ying and X. Wu, “Randomizing social networks: a spectrum preserving approach,” In: Proceedings of the SIAM international conference on data mining, 2008.##
[10]      L. Sweeney, “k-anonymity: a model for protecting privacy”. Int J Uncertain Fuzziness Knowl Based Syst, vol. 10, pp. 557–570, 2002##.
 [11]      B. Zhou and J. Pei, “Preserving privacy in social networks against neighborhood attacks,” In: Proceedings of the IEEE 24th international conference on data engineering, 2008.##
[12]   K. Rahmati, H. Naderi, and S. Keshvari, “Content-Structural Graph Clustering and a New Measure for Its Evaluation,” Journal of Advanced Defence Science and Technology, vol. 9, pp. 201-210, 2018##.
[13]      R. M. Karp, “Reducibility among combinatorial problems,” Complexity of computer computations, Springer, Boston, MA, pp. 85-103, 1972.##
[14]      www.orgnet.com##
[15]      W. W. Zachary, “An information flow model for conflict and fission in small groups,” Journal of Anthropological Research, vol. 33, pp. 452–473, 1977##.
[16]      M. Girvan and M. E. Newman, “Community structure in social and biological networks,” Proceedings of the national academy of sciences, vol. 99, pp. 7821–7826, 2002.##

Files

History

  • Receive Date: 08 April 2018
  • Accept Date: 13 October 2018
  • Publish Date: 22 June 2019

Share

How to cite

Statistics