Node Immunization on Large Graphs: Theory and Algorithms

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

Research output: Contribution to journalArticlepeer-review

67 Scopus citations


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.

Original languageEnglish (US)
Article number7181715
Pages (from-to)113-126
Number of pages14
JournalIEEE Transactions on Knowledge and Data Engineering
Issue number1
StatePublished - Jan 1 2016


  • Immunization
  • graph mining
  • scalability

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics


Dive into the research topics of 'Node Immunization on Large Graphs: Theory and Algorithms'. Together they form a unique fingerprint.

Cite this