Cost-effective outbreak detection in networks

Jure LeskovecAndreas KrauseCarlos GuestrinChristos FaloutsosJeanne VanBriesenNatalie Glance

article2007KDD2,804 citationsBest Paper Award

Proposes the CELF algorithm for network outbreak detection, exploiting submodularity to place sensors up to 700 times faster than standard greedy methods while providing provable approximation guarantees on massive water and information networks.

Listen

The article addresses the challenge of efficiently detecting outbreaks or information cascades in large networks, such as placing sensors in water distribution systems to catch contaminants or selecting blogs to monitor for emerging stories. These tasks matter because monitoring every location or source is prohibitively expensive, yet delayed detection can lead to widespread harm or missed information, and simple intuitive strategies like choosing the largest nodes often perform poorly.

The article set out to develop a general methodology for selecting a budgeted set of nodes that detects such spreading processes as effectively as possible. It demonstrates that common detection objectives exhibit submodularity, a diminishing-returns property that enables efficient optimization with performance guarantees.

The work models the problem as maximizing a nondecreasing submodular reward function subject to a cost budget, then exploits this structure with the CELF algorithm, which combines lazy evaluations and cost-benefit comparisons. The approach was tested on an EPA water network model with millions of contamination scenarios and on a real blog dataset containing 10.5 million posts and 17,000 cascades.

Key findings show that CELF produces placements guaranteed to achieve at least half of (1-1/e) of the optimal reward, even with varying node costs, while running up to 700 times faster than a basic greedy method. Online bounds derived in the article prove solutions lie within roughly 5-15 percent of optimality in the evaluated cases. The algorithm substantially outperforms heuristics based on popularity or degree, and it reveals that cost-aware selection favors smaller, high-quality sources over large ones; multicriterion trade-offs can be explored by weighting objectives without losing submodularity.

These results matter because they turn an intractable combinatorial task into a practical, provably good procedure that reduces detection time, affected population, and monitoring cost across domains. Decision makers can therefore allocate limited sensors or reading time with quantified confidence rather than relying on intuition.

The article recommends applying the same submodular framework to related problems such as network security and immunization. When strong guarantees are needed before deployment, further simulation or pilot data on the specific network would strengthen . Main limitations include reliance on accurate cascade or contamination models and the assumption that outbreaks remain sparse; results may degrade if these conditions do not hold.

blogs detection algorithm distribution network Submodular Function Sensor Placement Outbreak Detection

Leskovec et al (2007).pdf

Paper: Maximizing the spread of influence through a social network, David Kempe et al. (2003). This paper establishes the submodular optimization framework and greedy approximation guarantees for influence diffusion processes on networks that form the theoretical foundation of the source work.
Paper: Mining the network value of customers, Pedro M. Domingos et al. (2001). This work introduces the foundational formulation of identifying influential nodes by modeling network diffusion dynamics and word-of-mouth propagation.
Paper: Graphs over time: densification laws, shrinking diameters and possible explanations, J. Leskovec et al. (2005). This paper introduces empirical graph evolution and information diffusion patterns that inform the network cascade models analyzed in the source.
Paper: Group formation in large social networks: membership, growth, and evolution, L. Backstrom et al. (2006). This study analyzes empirical cascade and social group formation patterns that provide critical context for modeling spreading processes on real-world networks.

Paper: Efficient influence maximization in social networks, Wei Chen et al. (2009). This paper directly builds on the CELF lazy-forward optimization scheme introduced in the source to develop faster heuristics and scalable algorithms for influence maximization.
Paper: Earthquake shakes Twitter users: real-time event detection by social sensors, Takeshi Sakaki et al. (2010). This paper applies real-time network sensor monitoring principles to social media streams for detecting physical outbreaks and real-world events like earthquakes.
Paper: Epidemic processes in complex networks, Romualdo Pastor-Satorras et al. (2015). This comprehensive review synthesizes mathematical models of epidemic spreading and percolation on complex networks, extending the theoretical understanding of contagion dynamics.
Paper: Catastrophic cascade of failures in interdependent networks, S. Havlin et al. (2009). This work investigates cascading failure dynamics across coupled networks, extending single-network spreading models to interdependent infrastructures.

Cover for Cost-effective outbreak detection in networks

Abstract

Given a water distribution network, where should we place sensors to quickly 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 as quickly 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, and real 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.

1 Introduction
2 Outbreak Detection
2.1 Problem statement
2.2 Placement objectives
2.3 Properties of the placement objectives
2.4 Multicriterion optimization
3 Proposed algorithm
3.1 Bounds for the algorithm
3.2 Online bounds for any algorithm
4 Scaling up the algorithm
4.1 Speeding up function evaluations
4.2 Reducing function evaluations
5 Case study: Blog Network
5.1 Experimental setup
5.2 Objective functions
5.3 Solution quality
5.4 Cost of a blog
5.5 Comparison to heuristic blog selection
5.6 Fractionally selecting blogs
5.7 Generalization to future data
5.8 Scalability
6 Case study: Water networks
6.1 Experimental setup
6.2 Objective functions
6.3 Solution quality
6.4 Multicriterion optimization
6.5 Scalability
7 Discussion and related work
7.1 Relationship to Influence Maximization
7.2 Related work
8 Conclusions
Acknowledgements
References

Knowls

Knowl 1 — Submodularity of Expected Penalty Reduction in Outbreak Detection
theoretical result
Let a network be represented by a graph $G = (V, E)$ , and let $\mathcal{I}$ be a set of outbreak scenarios, where each scenario $i \in \mathcal{I}$ occurs with prior probability $P(i) \ge 0$ such that $\sum_{i \in \mathcal{I}} P(i) = 1$ . An outbreak in scenario $i$ spreads dynamically across $G$ . For any placed sensor set $\mathcal{A} \subseteq V$ , the detection time of scenario $i$ is defined as:

$T(i, \mathcal{A}) = \min_{s \in \mathcal{A}} T(i, s)$

where $T(i, s)$ is the time at which node $s$ detects outbreak scenario $i$ , with $T(i, \emptyset) = \infty$ . For each scenario $i$ , let $\pi_i(t)$ be a penalty function mapping detection time $t \in [0, \infty]$ to a penalty value, where $\pi_i(t)$ is monotonically nondecreasing in $t$ and $\pi_i(\infty)$ is the maximum penalty incurred if the scenario is never detected.

The expected penalty incurred by sensor placement $\mathcal{A}$ is $\pi(\mathcal{A}) = \sum_{i \in \mathcal{I}} P(i) \pi_i(T(i, \mathcal{A}))$ . The scenario-specific penalty reduction is $R_i(\mathcal{A}) = \pi_i(\infty) - \pi_i(T(i, \mathcal{A}))$ , and the total expected penalty reduction (reward) is:

$R(\mathcal{A}) = \sum_{i \in \mathcal{I}} P(i) R_i(\mathcal{A}) = \pi(\emptyset) - \pi(\mathcal{A})$

Theorem: For all sensor placements $\mathcal{A} \subseteq \mathcal{B} \subseteq V$ and any sensor $s \in V \setminus \mathcal{B}$ , the expected penalty reduction satisfies the diminishing returns property:

$R(\mathcal{A} \cup \{s\}) - R(\mathcal{A}) \ge R(\mathcal{B} \cup \{s\}) - R(\mathcal{B})$

Thus, $R(\mathcal{A})$ is a nondecreasing submodular set function with $R(\emptyset) = 0$ . This property holds for standard outbreak objectives, including:
1. Detection Likelihood (DL): $\pi_i(t) = 0$ for $t < \infty$ and $\pi_i(\infty) = 1$ , measuring the fraction of detected outbreaks.
2. Detection Time (DT): $\pi_i(t) = \min\{t, T_{\max}\}$ , where $T_{\max}$ is the time horizon.
3. Population Affected (PA): $\pi_i(t)$ is the number of individuals or nodes affected in scenario $i$ prior to detection time $t$ .
Knowl 2 — Cost-Effective Lazy Forward Selection Algorithm
algorithm
Cost-Effective Lazy Forward selection (CELF) optimizes a nondecreasing submodular reward function $R(\mathcal{A})$ under a linear budget constraint $\sum_{s \in \mathcal{A}} c(s) \le B$ . It exploits the submodularity property $\delta_s(\mathcal{A}) \ge \delta_s(\mathcal{B})$ for $\mathcal{A} \subseteq \mathcal{B}$ to avoid evaluating every unselected candidate at every greedy step. An upper bound on the marginal increment $\delta_s$ is maintained for each node in a priority queue. At each iteration, only the current top candidate's marginal gain is recomputed; if it remains greater than or equal to the second-best upper bound, submodularity guarantees it is optimal, eliminating unnecessary evaluations.

CELF runs lazy forward selection under both the unit-cost rule ( $ext{UC}$ ) and the cost-benefit ratio rule ( $ext{CB}$ ), and returns whichever of the two candidate sets achieves the higher reward $R(\mathcal{A})$ .
Function LazyForward(V, R, c, B, rule):
    Input: Ground set of nodes $V$ , submodular reward function $R$ , cost function $c$ , budget $B$ , selection rule $rule \in \{UC, CB\}$
    Output: Sensor placement set $A$
     $A = \emptyset$
    for each $s \in V$ do:
         $\delta_s = +\infty$
    while exists $s \in V \setminus A$ such that $c(A \cup \{s\}) \le B$ do:
        for each $s \in V \setminus A$ do:
             $cur_s = false$
        while true do:
            if $rule == UC$ then:
                 $s^* = \operatorname{argmax}_{s \in V \setminus A, c(A \cup \{s\}) \le B} \delta_s$
            else if $rule == CB$ then:
                 $s^* = \operatorname{argmax}_{s \in V \setminus A, c(A \cup \{s\}) \le B} \frac{\delta_s}{c(s)}$
            if $cur_{s^*} == true$ then:
                 $A = A \cup \{s^*\}$
                break
            else:
                 $\delta_{s^*} = R(A \cup \{s^*\}) - R(A)$
                 $cur_{s^*} = true$
    return $A$
Algorithm CELF(V, R, c, B):
    Input: Ground set $V$ , submodular reward function $R$ , cost function $c$ , budget $B$
    Output: Selected set $A$
     $A_{UC} = LazyForward(V, R, c, B, UC)$
     $A_{CB} = LazyForward(V, R, c, B, CB)$
    return $\operatorname{argmax}\{R(A_{UC}), R(A_{CB})\}$
Knowl 3 — Constant-Factor Approximation Guarantee for Budgeted Submodular Maximization
theoretical result
Let $R: 2^V \to \mathbb{R}_{\ge 0}$ be any nondecreasing submodular set function on ground set $V$ with $R(\emptyset) = 0$ , and let $c: V \to \mathbb{R}_{\ge 0}$ be a nonnegative cost function such that the cost of a set $\mathcal{A} \subseteq V$ is $c(\mathcal{A}) = \sum_{s \in \mathcal{A}} c(s)$ . The optimization problem is:

$\max_{\mathcal{A} \subseteq V} R(\mathcal{A}) \quad \text{subject to} \quad c(\mathcal{A}) \le B$

Let $\mathcal{A}_{GCB}$ be the set obtained by the benefit-cost greedy algorithm (iteratively picking $s = \operatorname{argmax}_{s \in V \setminus \mathcal{A}, c(\mathcal{A} \cup \{s\}) \le B} \frac{R(\mathcal{A} \cup \{s\}) - R(\mathcal{A})}{c(s)}$ ), and let $\mathcal{A}_{GUC}$ be the set obtained by the unit-cost greedy algorithm (iteratively picking $s = \operatorname{argmax}_{s \in V \setminus \mathcal{A}, c(\mathcal{A} \cup \{s\}) \le B} [R(\mathcal{A} \cup \{s\}) - R(\mathcal{A})]$ ).

Theorem: The better of the two greedy solutions satisfies:

$\max\{R(\mathcal{A}_{GCB}), R(\mathcal{A}_{GUC})\} \ge \frac{1}{2}\left(1 - \frac{1}{e}\right) \max_{\mathcal{A} \subseteq V, c(\mathcal{A}) \le B} R(\mathcal{A})$

This provides a polynomial-time approximation guarantee of $\frac{1}{2}(1 - 1/e) \approx 0.316$ for arbitrary nonnegative non-constant node costs. Evaluating this strategy requires $O(B|V|)$ function evaluations (assuming the minimum node cost is lower bounded by a constant), as opposed to $\Omega(B|V|^4)$ evaluations required by $(1 - 1/e)$ knapsack submodular algorithms.
Knowl 4 — Online Performance Bounds for Arbitrary Sensor Placements
theoretical result
For any sensor placement $\hat{\mathcal{A}} \subseteq V$ , an algorithm-independent upper bound on the optimal reward achievable under budget constraint $B$ can be computed post-hoc using the submodularity of $R$ .

For every unselected node $s \in V \setminus \hat{\mathcal{A}}$ , define its marginal gain $\delta_s = R(\hat{\mathcal{A}} \cup \{s\}) - R(\hat{\mathcal{A}})$ and its benefit-cost ratio $r_s = \delta_s / c(s)$ . Let $(s_1, s_2, \dots, s_m)$ be the sequence of elements in $V \setminus \hat{\mathcal{A}}$ sorted in decreasing order of $r_s$ ( $r_{s_1} \ge r_{s_2} \ge \dots \ge r_{s_m}$ ).

Let $k$ be the index such that:

$C = \sum_{i=1}^{k-1} c(s_i) \le B \quad \text{and} \quad \sum_{i=1}^k c(s_i) > B$

Define the fractional budget ratio for the $k$ -th element as $\lambda = \frac{B - C}{c(s_k)}$ .

Theorem: The optimal reward is bounded online by:

$\max_{\mathcal{A} \subseteq V, c(\mathcal{A}) \le B} R(\mathcal{A}) \le R(\hat{\mathcal{A}}) + \sum_{i=1}^{k-1} \delta_{s_i} + \lambda \delta_{s_k}$

This bound is derived by relaxing the submodular optimization problem to a fractional knapsack problem over the marginal gains and can be evaluated lazily during optimization to obtain empirical solution guarantees far tighter than the offline worst-case factor $\frac{1}{2}(1 - 1/e)$ .
Knowl 5 — Inverted Index Representation for Sparse Outbreak Penalty Reduction
model/method
In large-scale outbreak detection problems, most outbreak scenarios $i \in \mathcal{I}$ are spatially localized and affect only a small subset of the network nodes $V$ . Consequently, the individual penalty reduction $R_i(\{s\}) = \pi_i(\infty) - \pi_i(T(i, s))$ is zero for the vast majority of scenario-node pairs $(i, s)$ .

To exploit this sparsity, the penalty reduction function $R$ is stored as an inverted index mapping each candidate node $s \in V$ to a list of scenario identifiers $i$ detected by $s$ along with the corresponding non-zero penalty reductions $R_i(\{s\})$ . For any candidate placement $\mathcal{A} \subseteq V$ , the expected penalty reduction is evaluated by iterating only over the union of scenarios detected by nodes in $\mathcal{A}$ :

$R(\mathcal{A}) = \sum_{i:\, i \text{ detected by } \mathcal{A}} P(i) \max_{s \in \mathcal{A}} R_i(\{s\})$

This sparse inverted index compresses 30 GB of blog cascade logs (originally 3.5 GB in uncompressed index format) down to 50 MB, and compresses 152 GB of water network simulation data down to 16 GB, allowing multi-million scenario datasets to fit entirely within main memory and avoiding disk access bottlenecks during optimization.
Knowl 6 — Equivalence of Influence Maximization Under the Triggering Model to Outbreak Detection
theoretical result
The Triggering Model for influence maximization defines a probability distribution $P$ over directed graphs $G_1 = (V, \mathcal{E}_1), \dots, G_N = (V, \mathcal{E}_N)$ on a fixed node set $V$ . The influence $\sigma(\mathcal{A})$ of a seed set $\mathcal{A} \subseteq V$ is the expected number of nodes reachable from $\mathcal{A}$ over this distribution.

Theorem: The Triggering Model is a special case of the network outbreak detection problem.

Specifically, for each graph $G_i = (V, \mathcal{E}_i)$ in the Triggering distribution, let $G'_i = (V, \mathcal{E}'_i)$ be the directed graph obtained by reversing the direction of every directed edge in $\mathcal{E}_i$ . Under the Population Affected (PA) objective on $G'_i$ , the penalty reduction $R_i(\mathcal{A})$ by sensor set $\mathcal{A}$ corresponds exactly to the number of nodes reachable from $\mathcal{A}$ in $G_i$ . Therefore, the expected penalty reduction equals the influence function:

$R(\mathcal{A}) = \sum_{i} P(i) R_i(\mathcal{A}) = \sigma(\mathcal{A})$
Knowl 7 — Multicriterion Outbreak Detection via Submodular Scalarization
model/method
When detecting outbreaks, multiple conflicting objectives often need to be optimized simultaneously, such as Detection Likelihood ( $R_{DL}$ ), Detection Time ( $R_{DT}$ ), and Population Affected ( $R_{PA}$ ). A sensor placement $\mathcal{A}$ produces a vector of scores $\mathbf{R}(\mathcal{A}) = (R_1(\mathcal{A}), \dots, R_m(\mathcal{A}))$ .

Pareto-optimal placements are obtained using scalarization with positive weighting parameters $\lambda_1 > 0, \dots, \lambda_m > 0$ :

$R(\mathcal{A}) = \sum_{j=1}^m \lambda_j R_j(\mathcal{A})$

Because submodularity and monotonicity are closed under nonnegative linear combinations, the composite scalarized objective $R(\mathcal{A})$ remains a nondecreasing submodular set function with $R(\emptyset) = 0$ . Maximizing $R(\mathcal{A})$ subject to $\sum_{s \in \mathcal{A}} c(s) \le B$ is guaranteed to yield a Pareto-optimal placement. By systematically sweeping the weights $\lambda_j$ , one can trace out Pareto tradeoff curves and identify knee points where multiple objectives achieve near-optimal values simultaneously.
Knowl 8 — Outbreak Detection Performance and Cost-Benefit Tradeoffs in the Blogosphere
empirical result
Outbreak detection was evaluated on a real-world blog dataset comprising 45,000 active blogs, 10.5 million posts, 16.2 million links, and 17,589 cascades (restricted to cascades with $\ge 10$ nodes, with blogs participating in an average of 9.4 cascades).

Key empirical findings include:
1. Solution Quality: Online bounds show that CELF placements are provably within 5% to 15% of the optimal solution across DL, DT, and PA objectives (and at most 13.8% from optimal after selecting 100 blogs under PA).
2. Unit Cost vs. Post Count Cost: Under unit cost ( $c(s) = 1$ ), CELF selected high-volume political blogs (e.g., instapundit.com with 4,593 posts; top 10 blogs accounted for over 21,000 posts in 2006). Under the Number of Posts (NP) cost model where $c(s)$ equals the blog's total post count, CELF instead selected summarizer blogs (e.g., themodulator.org, watcherofweasels.com). To achieve a target PA reward of $R = 0.4$ , the NP cost model required reading only 1,500 posts, whereas the unit cost model required reading 10,710 posts.
3. Comparison to Heuristics: CELF outperformed intuitive heuristic selections (ranking by number of in-links, out-links, total posts, or random) by 41% to 45%.
4. Fractional Blog Reading: Splitting blogs into 7 day-of-week nodes increased the PA score by 12% for the same post budget. Friday was found to be the most effective single day to read posts (PA score of 0.20 for Friday vs. 0.13 for other days under a 1,000-post budget).
5. Temporal Generalization: When training on the first 6 months and evaluating on the subsequent 6 months, selecting unconstrained blogs led to overfitting on low-activity blogs. Restricting candidates to blogs with at least 1 post per day (365 posts/year) eliminated the generalization gap.
Knowl 9 — Sensor Placement and Multi-Objective Tradeoffs in Water Distribution Networks
empirical result
Sensor placement was evaluated on municipal water network models including BWSN1 (129 nodes), BWSN2 (12,527 nodes), and NW3 (21,000 nodes, 25,000 pipes, representing a large US metropolitan area), simulating 3.6 million contamination scenarios over 48 hours using the EPANET physical simulator.

Key empirical findings include:
1. Solution Optimality: Placements obtained by CELF were within 10% of the optimal score according to online bounds.
2. Comparison to Heuristics: CELF achieved a 45% higher PA reduction score than domain heuristics (selecting nodes by population, flow volume, degree, or pipe diameter) and outperformed the maximum over 100 random placement trials.
3. Objective Spatial Topology: Optimizing Population Affected (PA) concentrated sensors densely in high-population nodes, whereas optimizing Detection Likelihood (DL) spread sensors uniformly across the network to provide balanced spatial coverage.
4. Multi-Objective Correlation: Tracing Pareto trade-offs revealed that Population Affected (PA) and Contaminated Water Consumed were nearly perfectly correlated (tradeoff curves collapsed almost to single points), whereas DL and PA exhibited significant tradeoffs with distinct knee points.
5. Scenario Sample Convergence: Evaluating sensor placements on subsamples showed that scores converged rapidly to the true 3.6-million scenario score when using fewer than 100,000 sample scenarios.
Knowl 10 — Runtime and Memory Scalability of the CELF Algorithm
empirical result
CELF and its underlying sparse inverted index representation achieve multiple orders of magnitude speedups over standard greedy algorithms and exhaustive search:
1. Blogosphere Runtime: For selecting 100 blogs from a candidate pool of 45,000 blogs, standard greedy forward selection required 4.5 hours ( $\\approx 16,200$ seconds), whereas CELF completed in 23 seconds—a speedup factor of 700. Computing online bounds simultaneously with CELF required 54 seconds.
2. Water Network Runtime: For placing 10 sensors on the BWSN water network, CELF ran 10 times faster than the standard greedy algorithm, while exhaustive subset search was computationally intractable beyond $k = 3$ .
3. Memory Acceleration: Compressing penalty reduction data into sparse inverted indexes reduced memory requirements from 3.5 GB to 50 MB on the blog dataset and from 152 GB to 16 GB on the water distribution network. Fitting the entire scenario matrix into RAM avoided hard-drive I/O, accelerating objective evaluations by a factor of over 1,000.

Coverage note — No substantial contributed material was omitted from the knowls.

References

1.N. Bailey. The Mathematical Theory of Infectious Diseases and its Applications. Griffin, London, 1975.
2.J. Berry, W. E. Hart, C. E. Phillips, J. G. Uber, and J. Watson. Sensor placement in municipal water networks with temporal integer programming models. J. Water Resources Planning and Management, 2006.
3.S. Bikhchandani, D. Hirshleifer, and I. Welch. A theory of fads, fashion, custom, and cultural change as informational cascades. J. of Polit. Econ., (5), 1992.
4.S. Boyd and L. Vandenberghe. Convex Optimization. Cambridge UP, March 2004.
5.R. Cohen, S. Havlin, and D. ben Avraham. Efficient immunization strategies for computer networks and populations. Physical Review Letters, 91:247901, 2003.
6.G. Dorini, P. Jonkergouw, and et.al. An efficient algorithm for sensor placement in water distribution systems. In 8th Annual Symposium on Water Distribution Systems Analysis, Cincinnati, Ohio, 2006.
7.G. Giakkoupis, A. Gionis, E. Terzi, and P. Tsaparas. Models and algorithms for network immunization. Technical report, C-2005-75, 2005.
8.N. S. Glance, M. Hurst, K. Nigam, M. Siegler, R. Stockton, and T. Tomokiyo. Deriving marketing intelligence from online discussion. In KDD, 2005.
9.J. Goldenberg, B. Libai, and E. Muller. Talk of the network: A complex systems look at the underlying process of word-of-mouth. Marketing Letters, 12, 2001.
10.D. Gruhl, R. Guha, D. Liben-Nowell, and A. Tomkins. Information diffusion through blogspace. In WWW, 2004.
11.R. Gueli. Predator-prey model for discrete sensor placement. In 8th Annual Symposium on Water Distribution Systems Analysis, Cincinnati, Ohio, 2006.
12.D. Kempe, J. Kleinberg, and E. Tardos. Maximizing the spread of influence through a social network. In KDD, 2003.
13.S. Khuller, A. Moss, and J. Naor. The budgeted maximum coverage problem. Inf. Proc. Let., 1999.
14.A. Krause, C. Guestrin. A Note on the Budgeted Maximization of Submodular Functions. Technical Report, CMU-CALD-05-103, 2007.
15.A. Krause, J. Leskovec, C. Guestrin, J. VanBriesen, and C. Faloutsos. Efficient sensor placement optimization for securing large water distribution networks. Submitted to the J. of Water Resources Planning an Management, 2007.
16.R. Kumar, J. Novak, P. Raghavan, and A. Tomkins. On the bursty evolution of blogspace. In WWW, pages 568–576. ACM Press, 2003.
17.J. Leskovec, L. A. Adamic, and B. A. Huberman. The dynamics of viral marketing. In ACM EC, 2006.
18.J. Leskovec, M. McGlohon, C. Faloutsos, N. S. Glance, and M. Hurst. Cascading behavior in large blog graphs. In SDM, 2007.
19.G. Nemhauser, L. Wolsey, and M. Fisher. An analysis of the approximations for maximizing submodular set functions. Mathematical Programming, 14, 1978.
20.A. Ostfeld and E. Salomons. Optimal layout of early warning detection stations for water distribution systems security. J. Water Resources Planning and Management, 130(5):377–385, 2004.
21.A. Ostfeld, J. G. Uber, and E. Salomons. Battle of water sensor networks: A design challenge for engineers and algorithms. In 8th Symposium on Water Distribution Systems Analysis, 2006.
22.R. Pastor-Satorras and A. Vespignani. Immunization of complex networks. Physical Review E, 65, 2002.
23.M. Richardson and P. Domingos. Mining knowledge-sharing sites for viral marketing. In KDD, 2002.
24.T. G. Robertazzi and S. C. Schwartz. An accelerated sequential algorithm for producing D-optimal designs. SIAM J. of Scientific and Statistical Computing, 10(2):341–358, March 1989.
25.E. Rogers. Diffusion of innovations (4th ed.). Free Press, 1995.
26.L. A. Rossman. The epanet programmer’s toolkit for analysis of water distribution systems. In Annual Water Resources Planning and Management Conference, 1999.
27.M. Sviridenko. A note on maximizing a submodular set function subject to knapsack constraint. Operations Research Letters, 32:41–43, 2004.

Citation

MLA

Leskovec, J., et al. “Cost-effective Outbreak Detection in Networks”. Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2007, pp. 420–29, https://doi.org/10.1145/1281192.1281239.

APA

Leskovec, J., Krause, A., Guestrin, C., Faloutsos, C., VanBriesen, J., & Glance, N. (2007). Cost-effective outbreak detection in networks. Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 420–429. https://doi.org/10.1145/1281192.1281239

Chicago

Leskovec, J., A. Krause, C. Guestrin, C. Faloutsos, J. VanBriesen, and N. Glance. 2007. “Cost-effective Outbreak Detection in Networks”. Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 420–29. https://doi.org/10.1145/1281192.1281239.

Harvard

Leskovec, J. et al. (2007) “Cost-effective outbreak detection in networks”, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, pp. 420–429. Available at: https://doi.org/10.1145/1281192.1281239.

Vancouver

1. Leskovec J, Krause A, Guestrin C, Faloutsos C, VanBriesen J, Glance N (2007) Cost-effective outbreak detection in networks. In: Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, pp 420–429

BibTeX

@inproceedings{Leskovec_2007, series={KDD07}, title={Cost-effective outbreak detection in networks}, url={http://dx.doi.org/10.1145/1281192.1281239}, DOI={10.1145/1281192.1281239}, booktitle={Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining}, publisher={ACM}, author={Leskovec, Jure and Krause, Andreas and Guestrin, Carlos and Faloutsos, Christos and VanBriesen, Jeanne and Glance, Natalie}, year={2007}, month=Aug, pages={420–429}, collection={KDD07} }

Metadata:Crossref

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

Cost-effective outbreak detection in networks

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Submodularity of Expected Penalty Reduction in Outbreak Detection

Knowl 2 — Cost-Effective Lazy Forward Selection Algorithm

Knowl 3 — Constant-Factor Approximation Guarantee for Budgeted Submodular Maximization

Knowl 4 — Online Performance Bounds for Arbitrary Sensor Placements

Knowl 5 — Inverted Index Representation for Sparse Outbreak Penalty Reduction

Knowl 6 — Equivalence of Influence Maximization Under the Triggering Model to Outbreak Detection

Knowl 7 — Multicriterion Outbreak Detection via Submodular Scalarization

Knowl 8 — Outbreak Detection Performance and Cost-Benefit Tradeoffs in the Blogosphere

Knowl 9 — Sensor Placement and Multi-Objective Tradeoffs in Water Distribution Networks

Knowl 10 — Runtime and Memory Scalability of the CELF Algorithm

References

Citation

BibTeX

Access the Paper