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