Cost-effective outbreak detection in networks

Summary

This work exploits submodularity to develop an efficient algorithm that scales to large problems, achieving near optimal placements, while being 700 times faster than a simple greedy algorithm and achieving speedups and savings in storage of several orders of magnitude.

Keywords

Computer science, Outbreak, Virology, Medicine

References

The Mathematical Theory of Infectious Diseases and its applicationsN. R. Ling — 1978
Talk of the Network: A Complex Systems Look at the Underlying Process of Word-of-MouthJacob Goldenberg, Barak Libai, Eitan Muller — 2001
A Note on the Budgeted Maximization of Submodular FunctionsAndreas Krause, Carlos Guestrin — 2005
An analysis of approximations for maximizing submodular set functions—IGeorge L. Nemhauser, Laurence A. Wolsey, Marshall L. Fisher — 1978
An accelerated sequential algorithm for producing D -optimal designsThomas G. Robertazzi, S.C. Schwartz — 1989
Diffusion of innovationsEverett M. Rogers, Arvind Singhal, Margaret M. Quinlan — 1964
The dynamics of viral marketingJure Leskovec, Lada A. Adamic, Bernardo A. Huberman — 2005
Information diffusion through blogspaceDaniel Gruhl, R. Guha, David Liben‐Nowell — 2004
A note on maximizing a submodular set function subject to a knapsack constraintMaxim Sviridenko — 2004
Efficient immunization strategies for computer networks and populations.Reuven Cohen, Shlomo Havlin, Daniel ben‐Avraham — 2002
Immunization of complex networks.Romualdo Pastor‐Satorras, Alessandro Vespignani — 2001
Mining knowledge-sharing sites for viral marketingMatthew Richardson, Pedro Domingos — 2002
Maximizing the spread of influence through a social networkDavid Kempe, Jon Kleinberg, Éva Tardos — 2003
Sensor Placement in Municipal Water Networks with Temporal Integer Programming ModelsJonathan W. Berry, William E. Hart, Cynthia A. Phillips — 2006
The Budgeted Maximum Coverage ProblemSamir Khuller, Anna Moss, Joseph Naor — 1999
Deriving marketing intelligence from online discussionNatalie Glance, Matthew Hurst, Kamal Nigam — 2005
PREDATOR - PREY MODEL FOR DISCRETE SENSOR PLACEMENTRoberto Gueli — 2008
Optimal Layout of Early Warning Detection Stations for Water Distribution Systems SecurityAvi Ostfeld, Elad Salomons — 2004
Efficient Sensor Placement Optimization for Securing Large Water Distribution NetworksAndreas Krause, Jure Leskovec, Carlos Guestrin — 2008
On the Bursty Evolution of BlogspaceRavi Kumar, Jasmine Novak, Prabhakar Raghavan — 2003

Cited by

Efficient Estimation of Influence Functions for SIS Model on Social NetworksMasahiro Kimura, Kazumi Saito, Hiroshi Motoda — 2009
CGC: A Flexible and Robust Approach to Integrating Co-Regularized Multi-Domain Graph for ClusteringJames W. Diehm — 2016
Etude, représentation et applications des traverses minimales d'un hypergraphe. (Representation and applications of hypergraph minimal transversals)M. N. Jelassi — 2014
Automatic Generation of Issue Maps: Structured, Interactive Outputs for Complex Information NeedsCarlos Guestrin, Dafna Shahaf — 2012
The Structure and Dynamics of Information Sharing NetworksLada A. Adamic, Martin J. Strauss, Xiaolin Shi — 2009
Fast Multi-stage Submodular MaximizationKai Wei, Rishabh Iyer, Jeff Bilmes — 2014
Finding her master's voice: the power of collective action among female muslim bloggersNitin Agarwal, Merlyna Lim, Rolf T. Wigand — 2011
Optimal Network Design for the Spread of CascadesDaniel Sheldon, Bistra Dilkina, Adam N. Elmachtoub — 2010
A fast approximation for influence maximization in large social networksJong-Ryul Lee, Chin‐Wan Chung — 2014
Fast Algorithms for Mining Co-evolving Time SeriesLi, Lei — 2011
An Efficient Simulation-Based Approach to Ambulance Fleet Allocation and Dynamic RedeploymentYisong Yue, Lavanya Marla, Ramayya Krishnan — 2012
On Maximum Coverage in the Streaming Model & Application to Multi-topic Blog-WatchBarna Saha, Lise Getoor — 2009
Unsupervised Graph-Based Similarity Learning Using Heterogeneous FeaturesPradeep Muthukrishnan — 2011
An upper bound based greedy algorithm for mining top-k influential nodes in social networksChuan Zhou, Peng Zhang, Jing Guo — 2014
Infectious Communities Forging - Using Information Diffusion Model in Social Network MiningTianran Hu, Xuechen Feng — 2011
Fast and Accurate Influence Maximization on Large Networks with Pruned Monte-Carlo SimulationsNaoto Ohsaka, Takuya Akiba, Yuichi Yoshida — 2014
Simulated Annealing Based Influence Maximization in Social NetworksQingye Jiang, Guojie Song, Cong Gao — 2011
A Wikipedia Based Semantic Graph Model for Topic Tracking in BlogsphereJintao Tang, Ting Wang, Qin Lu — 2011
Approximation Algorithms for Reducing the Spectral Radius to Control Epidemic SpreadSudip Saha, Abhijin Adiga, B. Aditya Prakash — 2015
Collaborative data dissemination in opportunistic vehicular networksYong Li, Zhaocheng Wang, Depeng Jin — 2012

Related papers

DETERMINING QUALITY REQUIREMENTS AT THE UNIVERSITIES TO IMPROVE THE QUALITY OF EDUCATIONNor Hanim Mustafa, Dinmukhamed Kelesbayev, Zh.D. Alibekova — 2018
Study on Outbreaks of Influenza-like Illness in Yunnan,2009Yibin Xiang — 2011
Analysis of outbreaks of infectious intestinal disease in Ireland: 1998 and 1999.Carissa Bonner, B. Foley, P G Wall — 2001
Two Linked Enteroinvasive Escherichia coli Outbreaks, Nottingham, UK, June 2014Sophie Newitt, Vanessa MacGregor, Vivienne Robbins — 2016
A Study of 279 General Outbreaks of Gastrointestinal Infection in the North-East Region of EnglandG M Tebbutt, Deborah Wilson, I Holtby — 2009
Foodborne Disease Outbreaks, 5-Year Summary, 1983-1987.Nancy H. Bean, Patricia M. Griffin, Joy S. Goulding — 1990
The Multiple Origins of Ebola Disease Outbreaks.Seth D. Judson, Vincent J. Munster — 2023
An outbreak of acute hemorrhagic conjunctivitis in Yugoslavia in 1973.Matevž Likar, L. Talanyi-Pfeifer, Julie Marin — 1975
Surveillance on Epidemic Outbreaks of Influenza-like Illness in Shenzhen from 2010 to 2011Chunli Wu — 2012