Measuring robustness of complex networks under MVC attack

Rong Hua Li*, Jeffrey Xu Yu, Xin Huang, Hong Cheng, Zechao Shang

*Corresponding author for this work

Research output: Chapter in book/report/conference proceedingConference proceedingpeer-review

26 Citations (Scopus)


Measuring robustness of complex networks is a fundamental task for analyzing the structure and function of complex networks. In this paper, we study the network robustness under the maximal vertex coverage (MVC) attack, where the attacker aims to delete as many edges of the network as possible by attacking a small fraction of nodes. First, we present two robustness metrics of complex networks based on MVC attack. We then propose an efficient randomized greedy algorithm with near-optimal performance guarantee for computing the proposed metrics. Finally, we conduct extensive experiments on 20 real datasets. The results show that P2P and co-authorship networks are extremely robust under the MVC attack while both the online social networks and the Email communication networks exhibit vulnerability under the MVC attack. In addition, the results demonstrate the efficiency and effectiveness of our proposed algorithms for computing the corresponding robustness metrics.

Original languageEnglish
Title of host publicationCIKM '12: Proceedings of the 21st ACM international conference on Information and knowledge management
PublisherAssociation for Computing Machinery (ACM)
Number of pages5
ISBN (Print)9781450311564
Publication statusPublished - 29 Oct 2012
Event21st ACM International Conference on Information and Knowledge Management, CIKM 2012 - Maui, United States
Duration: 29 Oct 20122 Nov 2012

Publication series

NameACM International Conference Proceeding Series


Conference21st ACM International Conference on Information and Knowledge Management, CIKM 2012
Country/TerritoryUnited States
Internet address

Scopus Subject Areas

  • Software
  • Human-Computer Interaction
  • Computer Vision and Pattern Recognition
  • Computer Networks and Communications

User-Defined Keywords

  • Network robustness
  • FM sketch
  • Submodular function
  • MVC attack


Dive into the research topics of 'Measuring robustness of complex networks under MVC attack'. Together they form a unique fingerprint.

Cite this