Cost-effective outbreak detection in networks
By Jure Leskovec, Andreas Krause, Carlos Guestrin, Christos Faloutsos, Jeanne M. VanBriesen, Natalie S. Glance. 2007
2,780 citations recorded by the source corpus.
Given a water distribution network, where should we place sensors toquickly detect contaminants? Or, which blogs should we read to avoid missing important stories?. These seemingly different problems share common structure: Outbreak detection can be modeled as selecting nodes (sensor locations, blogs) in a network, in order to detect the spreading of a virus or information asquickly as possible. We present a general methodology for near optimal sensor placement in these and related problems. We demonstrate that many realistic outbreak detection objectives (e.g., detection likelihood, population affected) exhibit the property of "submodularity". We exploit 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. We also derive online bounds on the quality of the placements obtained by any algorithm. Our algorithms and bounds also handle cases where nodes (sensor locations, blogs) have different costs. We evaluate our approach on several large real-world problems,including a model of a water distribution network from the EPA, andreal blog data. The obtained sensor placements are provably near optimal, providing a constant fraction of the optimal solution. We show that the approach scales, achieving speedups and savings in storage of several orders of magnitude. We also show how the approach leads to deeper insights in both applications, answering multicriteria trade-off, cost-sensitivity and generalization questions.
Subfields: Artificial Intelligence, Civil and Structural Engineering, Computer Science Applications
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Bernhard Schölkopf
- Yoshua Bengio
- Mohit Bansal
- Jure Leskovec
- Eric P. Xing
- Percy Liang
- Sergey Levine
- Charu C. Aggarwal
In Civil and Structural Engineering
- Andreas Krause
- Laks V. S. Lakshmanan
- D. Golovin
- Wei Lu
- Carlos Guestrin
- Amit Goyal
- Bernhard Schölkopf
- Ashwinkumar Badanidiyuru
In Computer Science Applications
- Laks V. S. Lakshmanan
- Wei Lu
- Andreas Krause
- Ashwinkumar Badanidiyuru
- Amit Goyal
- Kristina Lerman
- Bernhard Schölkopf
- Manuel Gomez-Rodriguez
Citations in the corpus
- Scalable Influence Estimation in Continuous-Time Diffusion Networks (2013, methodology): “Moreover, lazy evaluation [5] can be employed to reduce the required number of marginal gains per iteration.”
- Lazier Than Lazy Greedy (2014, methodology): “For this purpose, accelerated/lazy variants (Minoux 1978; Leskovec et al. 2007) of the celebrated greedy algorithm of Nemhauser, Wolsey, and Fisher (1978) have been extensively used.”
- Submodular Function Maximization (2014, methodology): “However, perhaps surprisingly, at least one of the greedy solutions – the solution S uc returned by the uniform cost or the one S cb provided by the cost-benefit greedy algorithm cannot perform too badly: it can be shown that max { f ( S uc ) , f ( S cb ) } ≥ 1 − 1 /e 2 OPT (Leskovec et al., 2007).”
- A classification for community discovery methods in complex networks (2011, methodology): “The general goal is similar to recent works such as [143, 144, 145].”
- Patterns of temporal variation in online media (2011, background): “Moreover, our results can be used for better placing of content to maximize clickthrough rates [5] and for .nding in.uential blogs and Twitters [23].”
- Max-cover in map-reduce (2010, methodology): “Max-k-Cover-based framework has been used a lot in many data mining applications; earliest ones include identifying the most influential users in social networks, under a model of influence propagation [20, 24, 5].”
- Information Contagion: An Empirical Study of the Spread of News on Digg and Twitter Social Networks (2010, neutral): “2007b), and identification of influential blogs (Gruhl and Liben-nowell 2004; Leskovec et al. 2007a).”
- Maximizing Social Influence in Nearly Optimal Time (2012, background): “These have focused largely on heuristics, such as assuming that all nodes have relatively low influence or that the input graph is clustered [12, 14, 25, 38], as well as empirically-motivated implementation improvements [27, 13].”
- Fast algorithms for maximizing submodular functions (2014, methodology): “An often used version of greedy known as lazy greedy [28, 23] seems to perform much better in practice.”
- Information is not a Virus, and Other Consequences of Human Cognitive Limits (2016, background): “The analogy between the spread of a disease and information is the basis of computational methods that attempt to amplify the spread of information in networks by identifying influential “superspreaders” [1–5], and those that make inferences about the network from observations of how information spr”
- CELF++: optimizing the greedy algorithm for influence maximization in social networks (2011, methodology): “The most notable work is [6], where submodularity is exploited to develop an efficient algorithm called CELF , based on a “lazy-forward” optimization in selecting seeds.”
- Influence Maximization on Social Graphs: A Survey (2018, methodology): “This triggers a number of research efforts to optimize the algorithm, which fall into two categories, i.e., reducing the number of MC simulations, and reducing the complexity of MC [3], [52], [56], [57], [58].”
- Influence Maximization in Continuous Time Diffusion Networks (2012, methodology): “We can speed up our algorithm by implementing the following speed-ups: Lazy evaluation (LE, Leskovec et al. (2007) ): it dramatically reduces the number of evaluations of marginal gains by exploiting the submodularity of σ(A; T ).”