Disrupting diffusion: Critical nodes in network

Thumbnail Image
Date
2018-01-01
Authors
Bhardwaj, Preeti
Major Professor
Advisor
Samik Basu
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Authors
Research Projects
Organizational Units
Organizational Unit
Journal Issue
Is Version Of
Versions
Series
Department
Computer Science
Abstract

With the advent and proliferation of connected entities such as social, marketing, scientific and computer networks, it has become immensely important to understand and analyze the impact of one entity's influence on another in the network. In this context, our objective is to identify a set of entities, which when made ineffective (quarantined or protected) will maximally disrupt the spread of influence in the network. We formulate and study the problem of identifying nodes whose absence can maximally disrupt propagation of information in the independent cascade model of diffusion. We present the notion of impact and characterize critical nodes based on this notion. Informally, impact of a set of nodes quantifies the necessity of the nodes in the diffusion process. We prove that the impact is monotonic. Interestingly, unlike similar formulation of critical edges in the context of Linear Threshold diffusion model, impact is neither submodular nor supermodular. Hence, 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.

Comments
Description
Keywords
Citation
DOI
Source
Subject Categories
Copyright
Wed Aug 01 00:00:00 UTC 2018