Measuring the impact of MVC attack in large complex networks

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

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-review

22 Citations (Scopus)


Measuring the impact of network attack is an important issue in network science. In this paper, we study the impact of maximal vertex coverage (MVC) attack in large complex networks, where the attacker aims at deleting as many edges of the network as possible by attacking a small fraction of nodes. First, we present two metrics to measure the impact of MVC attack. To compute these metrics, we propose an efficient randomized greedy algorithm with near-optimal performance guarantee. Second, we generalize the MVC attack into an uncertain setting, in which a node is deleted by the attacker with a prior probability. We refer to the MVC attack under such uncertain environment as the probabilistic MVC attack. Based on the probabilistic MVC attack, we propose two adaptive metrics, and then present an adaptive greedy algorithm for calculating such metrics accurately and efficiently. 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 the proposed algorithms for computing the proposed metrics.

Original languageEnglish
Pages (from-to)685-702
Number of pages18
JournalInformation Sciences
Publication statusPublished - 10 Sept 2014

Scopus Subject Areas

  • Software
  • Control and Systems Engineering
  • Theoretical Computer Science
  • Computer Science Applications
  • Information Systems and Management
  • Artificial Intelligence

User-Defined Keywords

  • (Adaptive) submodularity
  • Complex network
  • FM sketch
  • MVC attack


Dive into the research topics of 'Measuring the impact of MVC attack in large complex networks'. Together they form a unique fingerprint.

Cite this