Measuring robustness of complex networks under MVC attack

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

doi:10.1145/2396761.2398463

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

Department of Computer Science

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

27 Citations (Scopus)

Abstract

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 language	English
Title of host publication	CIKM '12: Proceedings of the 21st ACM international conference on Information and knowledge management
Publisher	Association for Computing Machinery (ACM)
Pages	1512-1516
Number of pages	5
ISBN (Print)	9781450311564
DOIs	https://doi.org/10.1145/2396761.2398463
Publication status	Published - 29 Oct 2012
Event	21st ACM International Conference on Information and Knowledge Management, CIKM 2012 - Maui, United States Duration: 29 Oct 2012 → 2 Nov 2012 https://dl.acm.org/doi/proceedings/10.1145/2396761

Publication series

Name	ACM International Conference Proceeding Series

Conference

Conference	21st ACM International Conference on Information and Knowledge Management, CIKM 2012
Country/Territory	United States
City	Maui
Period	29/10/12 → 2/11/12
Internet address	https://dl.acm.org/doi/proceedings/10.1145/2396761

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

Access to Document

10.1145/2396761.2398463

Cite this

Li, R. H., Yu, J. X., Huang, X., Cheng, H., & Shang, Z. (2012). Measuring robustness of complex networks under MVC attack. In CIKM '12: Proceedings of the 21st ACM international conference on Information and knowledge management (pp. 1512-1516). (ACM International Conference Proceeding Series). Association for Computing Machinery (ACM). https://doi.org/10.1145/2396761.2398463

@inproceedings{99934b63c1a54da9907d99f44e185dec,

title = "Measuring robustness of complex networks under MVC attack",

abstract = "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.",

keywords = "Network robustness, FM sketch, Submodular function, MVC attack",

author = "Li, {Rong Hua} and Yu, {Jeffrey Xu} and Xin Huang and Hong Cheng and Zechao Shang",

note = "The work was supported by grant of the Research Grants Council of the Hong Kong SAR, China No. 419109 and 411211.; 21st ACM International Conference on Information and Knowledge Management, CIKM 2012 ; Conference date: 29-10-2012 Through 02-11-2012",

year = "2012",

month = oct,

day = "29",

doi = "10.1145/2396761.2398463",

language = "English",

isbn = "9781450311564",

series = "ACM International Conference Proceeding Series",

publisher = "Association for Computing Machinery (ACM)",

pages = "1512--1516",

booktitle = "CIKM '12: Proceedings of the 21st ACM international conference on Information and knowledge management",

address = "United States",

url = "https://dl.acm.org/doi/proceedings/10.1145/2396761",

}

Li, RH, Yu, JX, Huang, X, Cheng, H & Shang, Z 2012, Measuring robustness of complex networks under MVC attack. in CIKM '12: Proceedings of the 21st ACM international conference on Information and knowledge management. ACM International Conference Proceeding Series, Association for Computing Machinery (ACM), pp. 1512-1516, 21st ACM International Conference on Information and Knowledge Management, CIKM 2012, Maui, Hawaii, United States, 29/10/12. https://doi.org/10.1145/2396761.2398463

Measuring robustness of complex networks under MVC attack. / Li, Rong Hua; Yu, Jeffrey Xu; Huang, Xin et al.
CIKM '12: Proceedings of the 21st ACM international conference on Information and knowledge management. Association for Computing Machinery (ACM), 2012. p. 1512-1516 (ACM International Conference Proceeding Series).

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

TY - GEN

T1 - Measuring robustness of complex networks under MVC attack

AU - Li, Rong Hua

AU - Yu, Jeffrey Xu

AU - Huang, Xin

AU - Cheng, Hong

AU - Shang, Zechao

N1 - The work was supported by grant of the Research Grants Council of the Hong Kong SAR, China No. 419109 and 411211.

PY - 2012/10/29

Y1 - 2012/10/29

N2 - 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.

AB - 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.

KW - Network robustness

KW - FM sketch

KW - Submodular function

KW - MVC attack

UR - http://www.scopus.com/inward/record.url?scp=84871083279&partnerID=8YFLogxK

U2 - 10.1145/2396761.2398463

DO - 10.1145/2396761.2398463

M3 - Conference proceeding

AN - SCOPUS:84871083279

SN - 9781450311564

T3 - ACM International Conference Proceeding Series

SP - 1512

EP - 1516

BT - CIKM '12: Proceedings of the 21st ACM international conference on Information and knowledge management

PB - Association for Computing Machinery (ACM)

T2 - 21st ACM International Conference on Information and Knowledge Management, CIKM 2012

Y2 - 29 October 2012 through 2 November 2012

ER -

Measuring robustness of complex networks under MVC attack

Abstract

Publication series

Conference

Scopus Subject Areas

User-Defined Keywords

Access to Document

Other files and links

Fingerprint

Cite this