Evaluating the role of critical nodes in disrupting diffusion in independent cascade diffusion model

Date
2019-01-01
Authors
Kumar, Raj Gaurav Ballabh
Major Professor
Advisor
Samik Basu
Pavan Aduri
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Altmetrics
Authors
Research Projects
Organizational Units
Computer Science
Organizational Unit
Journal Issue
Series
Department
Computer Science
Abstract

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.

Comments
Description
Keywords
Citation
DOI
Source