Degree Type


Date of Award


Degree Name

Master of Science


Computer Science


Computer Science

First Advisor

Samik . Basu

Second Advisor

Pavan . Aduri


How can we mitigate the unwanted diffusion of information in a social network? In this work

we look at this problem and propose a solution through the identification of critical nodes. If we

know which nodes act as the enablers to the spread of diffusion by a varied set of sources, then

by removing these enablers from the network we can minimize the spread of diffusion from a large

fraction of the sources. We call these enablers the critical nodes in a network. Identifying k critical

nodes such that removal of these nodes maximally disrupts the influence from any possible seed

is the ICN(k) problem. We use the notion of impact of a set of nodes and use it to characterize

the ICN(k) problem in the IC Model. Informally, impact of a set of nodes quantifies the necessity

of the nodes in the diffusion process. We develop heuristics that rely on greedy strategy and

modular or submodular approximations of impact function. We empirically evaluate our heuristics

by comparing the level of disruption achieved by identifying and removing critical nodes as opposed

to that achieved by removing the most influential nodes. We also run our algorithm on real-world

Twitter data and show that the critical nodes identified by our algorithm can be considered critical

to the diffusion of information.

Copyright Owner

Raj Gaurav Ballabh Kumar



File Format


File Size

72 pages