TY - JOUR
T1 - Node Immunization on Large Graphs
T2 - Theory and Algorithms
AU - Chen, Chen
AU - Tong, Hanghang
AU - Prakash, B. Aditya
AU - Tsourakakis, Charalampos E.
AU - Eliassi-Rad, Tina
AU - Faloutsos, Christos
AU - Chau, Duen Horng
N1 - Publisher Copyright:
© 2015 IEEE.
PY - 2016/1/1
Y1 - 2016/1/1
N2 - Given a large graph, like a computer communication network, which k nodes should we immunize (or monitor, or remove), to make it as robust as possible against a computer virus attack? This problem, referred to as the node immunization problem, is the core building block in many high-impact applications, ranging from public health, cybersecurity to viral marketing. A central component in node immunization is to find the best k bridges of a given graph. In this setting, we typically want to determine the relative importance of a node (or a set of nodes) within the graph, for example, how valuable (as a bridge) a person or a group of persons is in a social network. First of all, we propose a novel 'bridging' score Δλ, inspired by immunology, and we show that its results agree with intuition for several realistic settings. Since the straightforward way to compute Δλ is computationally intractable, we then focus on the computational issues and propose a surprisingly efficient way (O(nk2+m) ) to estimate it. Experimental results on real graphs show that (1) the proposed 'bridging' score gives mining results consistent with intuition; and (2) the proposed fast solution is up to seven orders of magnitude faster than straightforward alternatives.
AB - Given a large graph, like a computer communication network, which k nodes should we immunize (or monitor, or remove), to make it as robust as possible against a computer virus attack? This problem, referred to as the node immunization problem, is the core building block in many high-impact applications, ranging from public health, cybersecurity to viral marketing. A central component in node immunization is to find the best k bridges of a given graph. In this setting, we typically want to determine the relative importance of a node (or a set of nodes) within the graph, for example, how valuable (as a bridge) a person or a group of persons is in a social network. First of all, we propose a novel 'bridging' score Δλ, inspired by immunology, and we show that its results agree with intuition for several realistic settings. Since the straightforward way to compute Δλ is computationally intractable, we then focus on the computational issues and propose a surprisingly efficient way (O(nk2+m) ) to estimate it. Experimental results on real graphs show that (1) the proposed 'bridging' score gives mining results consistent with intuition; and (2) the proposed fast solution is up to seven orders of magnitude faster than straightforward alternatives.
KW - Immunization
KW - graph mining
KW - scalability
UR - http://www.scopus.com/inward/record.url?scp=84961625682&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84961625682&partnerID=8YFLogxK
U2 - 10.1109/TKDE.2015.2465378
DO - 10.1109/TKDE.2015.2465378
M3 - Article
AN - SCOPUS:84961625682
SN - 1041-4347
VL - 28
SP - 113
EP - 126
JO - IEEE Transactions on Knowledge and Data Engineering
JF - IEEE Transactions on Knowledge and Data Engineering
IS - 1
M1 - 7181715
ER -