Containing viral spread on sparse random graphs: bounds, algorithms, and experiments

DOI10.1080/15427951.2013.798600zbMATH Open1338.05242arXiv1310.1942OpenAlexW2963021936MaRDI QIDQ2808836FDOQ2808836

Authors: Milan Bradonjić, Michael Molloy, Guanhua Yan 

Publication date: 25 May 2016

Published in: Internet Mathematics (Search for Journal in Brave)

Abstract: Viral spread on large graphs has many real-life applications such as malware propagation in computer networks and rumor (or misinformation) spread in Twitter-like online social networks. Although viral spread on large graphs has been intensively analyzed on classical models such as Susceptible-Infectious-Recovered, there still exits a deficit of effective methods in practice to contain epidemic spread once it passes a critical threshold. Against this backdrop, we explore methods of containing viral spread in large networks with the focus on sparse random networks. The viral containment strategy is to partition a large network into small components and then to ensure the sanity of all messages delivered across different components. With such a defense mechanism in place, an epidemic spread starting from any node is limited to only those nodes belonging to the same component as the initial infection node. We establish both lower and upper bounds on the costs of inspecting inter-component messages. We further propose heuristic-based approaches to partition large input graphs into small components. Finally, we study the performance of our proposed algorithms under different network topologies and different edge weight models.

Full work available at URL: https://arxiv.org/abs/1310.1942

Recommendations

• Spread of infection over P.A. random graphs with edge insertion
• On bounding exact models of epidemic spread on networks
• scientific article; zbMATH DE number 7042423
• Infection spread in random geometric graphs
• Contagious sets in random graphs
• Sharp thresholds for contagious sets in random graphs
• Bounding the Size and Probability of Epidemics on Networks
• Spread of information and diseases via random walks in sparse graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80)

Cited In (3)

• Killing nodes as a countermeasure to virus expansion
• Title not available (Why is that?)
• Hardness Results for Seeding Complex Contagion with Neighborhoods

This page was built for publication: Containing viral spread on sparse random graphs: bounds, algorithms, and experiments

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2808836)