On the vulnerability of large graphs

Hanghang Tong; B. Aditya Prakash; Charalampos Tsourakakis; Tina Eliassi-Rad; Christos Faloutsos; Duen Horng Chau

doi:10.1109/ICDM.2010.54

On the vulnerability of large graphs

Hanghang Tong, B. Aditya Prakash, Charalampos Tsourakakis, Tina Eliassi-Rad, Christos Faloutsos, Duen Horng Chau

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

Given a large graph, like a computer network, which k nodes should we immunize (or monitor, or remove), to make it as robust as possible against a computer virus attack? We need (a) a measure of the 'Vulnerability' of a given network, (b) a measure of the 'Shield-value' of a specific set of k nodes and (c) a fast algorithm to choose the best such k nodes. We answer all these three questions: we give the justification behind our choices, we show that they agree with intuition as well as recent results in immunology. Moreover, we propose NetShield, a fast and scalable algorithm. Finally, we give experiments on large real graphs, where NetShield achieves tremendous speed savings exceeding 7 orders of magnitude, against straightforward competitors.

Original language	English (US)
Title of host publication	Proceedings - 10th IEEE International Conference on Data Mining, ICDM 2010
Pages	1091-1096
Number of pages	6
DOIs	https://doi.org/10.1109/ICDM.2010.54
State	Published - 2010
Externally published	Yes
Event	10th IEEE International Conference on Data Mining, ICDM 2010 - Sydney, NSW, Australia Duration: Dec 14 2010 → Dec 17 2010

Publication series

Name	Proceedings - IEEE International Conference on Data Mining, ICDM
ISSN (Print)	1550-4786

Other

Other	10th IEEE International Conference on Data Mining, ICDM 2010
Country/Territory	Australia
City	Sydney, NSW
Period	12/14/10 → 12/17/10

ASJC Scopus subject areas

General Engineering

Online availability

10.1109/ICDM.2010.54

Library availability

Discover UIUC Full Text

Cite this

Tong, H, Prakash, BA, Tsourakakis, C, Eliassi-Rad, T, Faloutsos, C & Chau, DH 2010, On the vulnerability of large graphs. in Proceedings - 10th IEEE International Conference on Data Mining, ICDM 2010., 5694090, Proceedings - IEEE International Conference on Data Mining, ICDM, pp. 1091-1096, 10th IEEE International Conference on Data Mining, ICDM 2010, Sydney, NSW, Australia, 12/14/10. https://doi.org/10.1109/ICDM.2010.54

@inproceedings{dcb9d75231094dfeb916de7b4982d17d,

title = "On the vulnerability of large graphs",

abstract = "Given a large graph, like a computer network, which k nodes should we immunize (or monitor, or remove), to make it as robust as possible against a computer virus attack? We need (a) a measure of the 'Vulnerability' of a given network, (b) a measure of the 'Shield-value' of a specific set of k nodes and (c) a fast algorithm to choose the best such k nodes. We answer all these three questions: we give the justification behind our choices, we show that they agree with intuition as well as recent results in immunology. Moreover, we propose NetShield, a fast and scalable algorithm. Finally, we give experiments on large real graphs, where NetShield achieves tremendous speed savings exceeding 7 orders of magnitude, against straightforward competitors.",

author = "Hanghang Tong and Prakash, {B. Aditya} and Charalampos Tsourakakis and Tina Eliassi-Rad and Christos Faloutsos and Chau, {Duen Horng}",

year = "2010",

doi = "10.1109/ICDM.2010.54",

language = "English (US)",

isbn = "9780769542560",

series = "Proceedings - IEEE International Conference on Data Mining, ICDM",

pages = "1091--1096",

booktitle = "Proceedings - 10th IEEE International Conference on Data Mining, ICDM 2010",

note = "10th IEEE International Conference on Data Mining, ICDM 2010 ; Conference date: 14-12-2010 Through 17-12-2010",

}

TY - GEN

T1 - On the vulnerability of large graphs

AU - Tong, Hanghang

AU - Prakash, B. Aditya

AU - Tsourakakis, Charalampos

AU - Eliassi-Rad, Tina

AU - Faloutsos, Christos

AU - Chau, Duen Horng

PY - 2010

Y1 - 2010

N2 - Given a large graph, like a computer network, which k nodes should we immunize (or monitor, or remove), to make it as robust as possible against a computer virus attack? We need (a) a measure of the 'Vulnerability' of a given network, (b) a measure of the 'Shield-value' of a specific set of k nodes and (c) a fast algorithm to choose the best such k nodes. We answer all these three questions: we give the justification behind our choices, we show that they agree with intuition as well as recent results in immunology. Moreover, we propose NetShield, a fast and scalable algorithm. Finally, we give experiments on large real graphs, where NetShield achieves tremendous speed savings exceeding 7 orders of magnitude, against straightforward competitors.

AB - Given a large graph, like a computer network, which k nodes should we immunize (or monitor, or remove), to make it as robust as possible against a computer virus attack? We need (a) a measure of the 'Vulnerability' of a given network, (b) a measure of the 'Shield-value' of a specific set of k nodes and (c) a fast algorithm to choose the best such k nodes. We answer all these three questions: we give the justification behind our choices, we show that they agree with intuition as well as recent results in immunology. Moreover, we propose NetShield, a fast and scalable algorithm. Finally, we give experiments on large real graphs, where NetShield achieves tremendous speed savings exceeding 7 orders of magnitude, against straightforward competitors.

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

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

U2 - 10.1109/ICDM.2010.54

DO - 10.1109/ICDM.2010.54

M3 - Conference contribution

AN - SCOPUS:79951739872

SN - 9780769542560

T3 - Proceedings - IEEE International Conference on Data Mining, ICDM

SP - 1091

EP - 1096

BT - Proceedings - 10th IEEE International Conference on Data Mining, ICDM 2010

T2 - 10th IEEE International Conference on Data Mining, ICDM 2010

Y2 - 14 December 2010 through 17 December 2010

ER -

On the vulnerability of large graphs

Abstract

Publication series

Other

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this