Near-Optimal Algorithms for Controlling Propagation at Group Scale on Networks

Given a network with groups, such as a contact-network grouped by ages, which are the best groups to immunize to control the epidemic? Equivalently, how to choose best communities in social media like Facebook to stop rumors from spreading? Immunization is an important problem in multiple different...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on knowledge and data engineering 2016-12, Vol.28 (12), p.3339-3352
Main Authors: Yao Zhang, Adiga, Abhijin, Saha, Sudip, Vullikanti, Anil, Prakash, B. Aditya
Format: Article
Language:English
Subjects:
Algorithms
Cybersecurity
Data models
diffusion
Digital media
Disease control
Epidemiology
Graph mining
groups
Immune system
Immunization
Mathematical model
Propagation
Public health
Public healthcare
Resource management
Social network services
Social networks
Vaccines
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Given a network with groups, such as a contact-network grouped by ages, which are the best groups to immunize to control the epidemic? Equivalently, how to choose best communities in social media like Facebook to stop rumors from spreading? Immunization is an important problem in multiple different domains like epidemiology, public health, cyber security, and social media. Additionally, clearly immunization at group scale (like schools and communities) is more realistic due to constraints in implementations and compliance (e.g., it is hard to ensure specific individuals take the adequate vaccine). Hence, efficient algorithms for such a "group-based" problem can help public-health experts take more practical decisions. However, most prior work has looked into individual-scale immunization. In this paper, we study the problem of controlling propagation at group scale. We formulate a set of novel Group Immunization problems for multiple natural settings (for both threshold and cascade-based contagion models under both node-level and edge-level interventions) and develop multiple efficient algorithms, including provably approximate solutions. Finally, we show the effectiveness of our methods via extensive experiments on real and synthetic datasets.
ISSN:1041-4347
1558-2191
DOI:10.1109/TKDE.2016.2605088