Call for Paper - September 2020 Edition
IJCA solicits original research papers for the September 2020 Edition. Last date of manuscript submission is August 20, 2020. Read More

Securing Social Network Graph against Structural Attack based on Ant Colony Optimization

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Year of Publication: 2017
Munmun Bhattacharya, Bratati Hui

Munmun Bhattacharya and Bratati Hui. Securing Social Network Graph against Structural Attack based on Ant Colony Optimization. International Journal of Computer Applications 167(9):21-26, June 2017. BibTeX

	author = {Munmun Bhattacharya and Bratati Hui},
	title = {Securing Social Network Graph against Structural Attack based on Ant Colony Optimization},
	journal = {International Journal of Computer Applications},
	issue_date = {June 2017},
	volume = {167},
	number = {9},
	month = {Jun},
	year = {2017},
	issn = {0975-8887},
	pages = {21-26},
	numpages = {6},
	url = {},
	doi = {10.5120/ijca2017914372},
	publisher = {Foundation of Computer Science (FCS), NY, USA},
	address = {New York, USA}


31% of global population use online social networks. These people can be from any class or may be very powerful, or may be world famous personnel, who are very likely to be stalked for inferring private information or people exploiting their privacy. For a better revenue, when any social networking sites sell these huge volume of data for either data mining or analysis to any third party organizations, the privacy of the users are put in danger. Naive anonymization is not effective enough to prevent most of the strategic attacks. Structural attack is kind of strategic attack. Here, using the structural knowledge available to the adversary, he can identify or infer some useful information about individual from a published anonymized social network graph. The available anonymization algorithms to prevent the structural attack are either insufficient or they degrades the data mining quality of the graph. So we consider preserving the data mining quality of the graph while eliminating most vulnerable edges under attack. We develop a privacy preserving strategy based on ant colony optimization which is a type of swam robot intelligence algorithm. We test this algorithm in some publicly available social graphs for checking the quality of the graph before and after anonymization using some known parameter of graphs.


  1. Munmun Bhattacharya, Sandipan Roy “Prevention of Walk Based Attack on Social Network Graphs Using Ant Colony Optimization” IEMCON 2015, Vancouver, Canada, October 15th -17th, 2015.
  2. Lars Backstorm, Cynthia Dwork, and Jon Kleinberg. Wherefore art thou r3579x? anonymized social networks, hidden patterns, and structural steganography. In International World Wide Web Conference, 2007.
  3. Michael Hay, Gerome Miklau, David Jensen, Don Towsley, and Philipp Weis. Resisting structural re-identification in anonymized social networks. In International Conference on Very Large Data Bases, 2008.
  4. Zhou, Bin, and Jian Pei. "Preserving privacy in social networks against neighborhood attacks." 2008 IEEE 24th International Conference on Data Engineering. IEEE, 2008.
  5. Dorigo M. and G. Di Caro (1999). “The Ant Colony Optimization Meta-Heuristic”, New Ideas in Optimization, McGraw-Hill, 11-32, ISBN:0-07-709506-5.
  6.  L. M. Gambardella, ` E. D. Taillard, and M. Dorigo. “Ant colonies for the quadratic assignment problem”. Journal of the Operational Research Society, 50(2):167–176, 1999. 
  7. E. W. Dijkstra, “A note on two problems in connexion with graphs,” Numerische Mathematik, vol. 1, pp. 269–271, 1959.
  8. Das, Sudipto, E. Ömer, and Amr El Abbadi. "Anonymizing weighted social network graphs." 2010 IEEE 26th International Conference on Data Engineering (ICDE 2010). IEEE, 2010.
  9. Mislove, Alan, et al. "Measurement and analysis of online social networks." Proceedings of the 7th ACM SIGCOMM conference on Internet measurement. ACM, 2007.
  10. Lusseau, David. "Evidence for social role in a dolphin social network." Evolutionary ecology 21.3 (2007): 357-366.
  11. R. Guimera, L. Danon, A. Diaz-Guilera, F. Giralt and A. Arenas, Physical Review E , vol. 68, 065103(R), (2003).
  12. M. Girvan and M. E. J. Newman, Community structure in social and biological networks, Proc. Natl. Acad. Sci. USA 99, 7821-7826 (2002).


Social Network Graph;Perturb Graph;Anonymization; Structural Attack; Ant Colony Optimization.