Effective social network quarantine with minimal isolation costs

Nowadays, the notion of diseases has been extended from real human diseases to general epidemic information propagations, such as the rumors in distributed systems. Controlling the spread of a disease is usually done through quarantine, where people that have, or are suspected to have, a disease are...

Full description

Saved in:
Bibliographic Details
Main Authors: Zheng, Huanyang, Wu, Jie
Format: Conference Proceeding
Language:English
Subjects:
Algorithms
Approximation
Approximation algorithms
Computers
Conferences
Control systems
Costs
Diseases
effective quarantine strategy
epidemic outbreak
Epidemics
Grippers
minimal isolation costs
Social network
Social network services
Social networks
Sociology
Strategy
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Nowadays, the notion of diseases has been extended from real human diseases to general epidemic information propagations, such as the rumors in distributed systems. Controlling the spread of a disease is usually done through quarantine, where people that have, or are suspected to have, a disease are isolated from having interactions with others. As a tradeoff, normal human interactions are inevitably degraded by the quarantine. This motivates us to explore a robust quarantine strategy that can eliminate epidemic outbreaks with minimal isolation costs. Our problem is shown to be NP-hard. A bounded algorithm with an approximation ratio of two is proposed, through utilizing the feasibility and minimality properties. Finally, real data-driven experiments demonstrate the efficiency and effectiveness of the proposed algorithms in real-world applications.
ISSN:1938-1883
DOI:10.1109/ICC.2016.7511601