Privacy Preservation in Sequential Published Social Networks Against Mutual Friend Attack


  • Jyothi Vadisala Andhra University
  • Valli Kumari Vatsavayi





Social Network, Privacy, Dynamic, Anonymize, Mutual Friend.


In recent years the social networks are widely used the way of connecting people, interact with each other and share the information. The social network data is rich in content and the data are published for third party users such as researchers. The social interaction between individual’s changes rapidly as time changes so there is a need of privacy preserving in dynamic networks. An adversary can acquire some local knowledge about individuals in the network and can easily breach the privacy of a few victims. This paper mainly focuses on preserving privacy in sequential published network data where the adversary has some knowledge about the number of mutual friends of the target victims over a time period. The kw-Number of Mutual Friend Anonymization model is proposed to anonymize each sequential published network. In this privacy model, k indicates the privacy level and w is the time interval taken by the adversary to acquire the knowledge of the victim. By this approach the adversary cannot identify the victim by acquiring the knowledge of each sequential published data. The performance evaluation shows that the proposed approach can preserve many characteristics of the dynamic social networks.


  1. B. Zhou, J. Pei and W. Luk, ``A brief survey on anonymization techniques for privacy preserving publishing of social network data'', ACM SIGKDD Explorations Newsletter, Vol.10, No.2, (2008), pp. 12 -- 22.
  2. Wu, Xintao and Ying, Xiaowei and Liu, Kun and Chen, Lei, Managing and Mining Graph Data, Springer US,(2010).
  3. Cheng, James and Fu, Ada Wai-chee and Liu, Jia, ``K-isomorphism: Privacy Preserving Network Publication Against Structural Attacks'', Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data, (2010), pp.459--470.
  4. Liu, Kun and Terzi, Evimaria, ``Towards Identity Anonymization on Graphs'', Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data, (2008), pp.93--106.
  5. B. Zhou and J. Pei, ``Preserving Privacy in Social Networks Against Neighborhood Attacks'', 2008 IEEE 24th International Conference on Data Engineering, April (2008), pp.506--515.
  6. Zou, Lei and Chen, Lei and "{O}zsu, M. Tamer, ``K-automorphism: A General Framework for Privacy Preserving Network Publication'', VLDB Endowment, Vol.2, No.1, August (2009), pp.946--957.
  7. Hay, Michael and Miklau, Gerome and Jensen, David and Towsley, Don and Weis, Philipp, ``Resisting Structural Re-identification in Anonymized Social Networks'', VLDB Endowment., Vol.1, No.1, August (2008), pp.102--114.
  8. Tai, Chih-Hua and Yu, Philip S. and Yang, De-Nian and Chen, Ming-Syan, ``Privacy-preserving Social Network Publication Against Friendship Attacks'', Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, (2011), pp.1262--1270.
  9. Chong Jing Sun and Philip S. Yu and Xiangnan Kong and Yan Fu, ``Privacy Preserving Social Network Publication Against Mutual Friend Attacks'', Transaction Data Privacy, Vol.7, No.2, (2014), pp.71--97.
  10. X. Wu, X. Ying, K. Liu, and L. Chen, ``A Survey of Privacy Preservation of Graphs and Networks,'' Managing and Mining Graph Data, (2010) vol. 40, pp. 421--453
  11. B. Zhou, J. Pei, and W. Luk, ``A Brief Survey on Anonymization Techniques for Privacy Preserving Publishing of Network Data,'' ACM SIGKDD Explorations, (2008) vol. 10, pp. 12-22
  12. B. Thompson and D. Yao,``The Union-Split Algorithm and Cluster-Based Anonymization of Social Networks,'' Proc. Fourth Int'l Symp. Information, Computer, and Comm. Security (ASIACCS), (2009).
  13. Wang, Ke and Fung, Benjamin C. M.,``Anonymizing Sequential Releases'', Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, (2006), pp.414—423.
  14. J.W. Byun, Y. Sohn, E. Bertino, and N. Li,``Secure Anonymization for Incremental Data Sets'' Proc. Third VLDB Int'l Conf. Secure Data Management (SDM), (2006).
  15. X. Xiao and Y. Tao,``M-Invariance: Towards Privacy Preserving Re-Publication of Dynamic Data Sets'' Proc. ACM SIGMOD Int'l Conf. Management of Data (SIGMOD), (2007).
  16. Bhagat, Smriti and Cormode, Graham and Krishnamurthy, Balachander and Srivastava, Divesh, ``Prediction Promotes Privacy in Dynamic Social Networks'', Proceedings of the 3rd Conference on Online Social Networks}, (2010), pp.6-6.
  17. N. Medforth and K. Wang, ``Privacy Risk in Graph Stream Publishing for Social Network Data'', 2011 IEEE 11th International Conference on Data Mining, (2011), pp.437--446.
  18. Zlatic, Vinko and Garlaschelli, Diego and Caldarelli, Guido, ``Complex networks with arbitrary edge multiplicities'', Physics, Vol.97, (2011), pp.8--11.
  19. Faloutsos, Michalis and Faloutsos, Petros and Faloutsos, Christos, ``On Power-law Relationships of the Internet Topology'', ACM SIGCOMM Comput. Commun. Rev., Vol.29, No.4, August (1999), pp.251--262.
  20. Jure Leskovec and Andrej Krevl, ``{SNAP Datasets}: {Stanford} Large Network Dataset Collection'',, June, (2014).

View Full Article: