Jure Leskovec
Andreas Krause
Christos Faloutsos
ABSTRACT
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.
Supplemental Material
- N. Bailey. The Mathematical Theory of Infectious Diseases and its Applications. Griffin, London, 1975.Google Scholar
- 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.Google Scholar
- 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.Google ScholarCross Ref
- S. Boyd and L. Vandenberghe. Convex Optimization. Cambridge UP, March 2004. Google ScholarDigital Library
- R. Cohen, S. Havlin, and D. ben Avraham. Efficient immunization strategies for computer networks and populations. Physical Review Letters, 91:247901, 2003.Google ScholarCross Ref
- G. Dorini, P. Jonkergouw, and et. al. An efficient algorithm for sensor placement in water distribution systems. In at. Dist. Syst. An. Conf., 2006.Google Scholar
- N. S. Glance, M. Hurst, K. Nigam, M. Siegler, R. Stockton, and T. Tomokiyo. Deriving marketing intelligence from online discussion. In KDD, 2005. Google ScholarDigital Library
- 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.Google Scholar
- D. Gruhl, R. Guha, D. Liben-Nowell, and A. Tomkins. Information diffusion through blogspace. WWW'04. Google ScholarDigital Library
- D. Kempe, J. Kleinberg, and E. Tardos. Maximizing the spread of in?uence through a social network. In KDD, 2003. Google ScholarDigital Library
- S. Khuller, A. Moss, and J. Naor. The budgeted maximum coverage problem. Inf. Proc. Let., 1999. Google ScholarDigital Library
- 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.Google Scholar
- R. Kumar, J. Novak, P. Raghavan, and A. Tomkins. On the bursty evolution of blogspace. In WWW, 2003. Google ScholarDigital Library
- J. Leskovec, L. A. Adamic, and B. A. Huberman. The dynamics of viral marketing. In ACM EC, 2006. Google ScholarDigital Library
- J. Leskovec, A. Krause, C. Guestrin, C. Faloutsos, J. VanBriesen, and N. Glance. Cost-effective Outbreak Detection in Networks. TR, CMU-ML-07-111, 2007.Google Scholar
- J. Leskovec, M. McGlohon, C. Faloutsos, N. S. Glance, and M. Hurst. Cascading behavior in large blog graphs. In SDM, 2007.Google ScholarCross Ref
- G. Nemhauser, L. Wolsey, and M. Fisher. An analysis of the approximations for maximizing submodular set functions. Mathematical Programming, 14, 1978.Google Scholar
- 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.Google ScholarCross Ref
- A. Ostfeld, J. G. Uber, and E. Salomons. Battle of water sensor networks: A design challenge for engineers and algorithms. In WDSA, 2006.Google Scholar
- R. Pastor-Satorras and A. Vespignani. Immunization of complex networks. Physical Review E, 65, 2002.Google Scholar
- M. Richardson and P. Domingos. Mining knowledge-sharing sites for viral marketing. KDD '02. Google ScholarDigital Library
- T. G. Robertazzi and S. C. Schwartz. An accelerated sequential algorithm for producing D-optimal designs. SIAM J.Sci.Stat.Comp., 10(2):341--358, 1989. Google ScholarDigital Library
- E. Rogers. Diffusion of innovations. Free Press, 1995.Google Scholar
- L. A. Rossman. The epanet programmer's toolkit for analysis of water distribution systems. In Ann. Wat. Res. Plan. Mgmt. Conference, 1999.Google ScholarCross Ref
- M. Sviridenko. A note on maximizing a submodular set function subject to knapsack constraint. Operations Research Letters, 32:41--43, 2004. Google ScholarDigital Library
Index Terms
- Cost-effective outbreak detection in networks
Recommendations
Minimum-Cost Sensor Placement for Required Lifetime in Wireless Sensor-Target Surveillance Networks
In sensor-target surveillance networks, sensors are typically powered by batteries with limited energy and hence it is important to manage the energy usage. In the literature, several methods have been proposed to maximize the lifetime of these ...
A self-organising algorithm for sensor placement in wireless mobile microsensor networks
This paper proposes a self-organising algorithm for enhancing the coverage of wireless mobile microsensor networks after an initial random placement of sensors. When the sensors move simultaneously in the neighbourhood, unnecessary excessive movement ...
Sensor deployment and target localization in distributed sensor networks
The effectiveness of cluster-based distributed sensor networks depends to a large extent on the coverage provided by the sensor deployment. We propose a virtual force algorithm (VFA) as a sensor deployment strategy to enhance the coverage after an ...
Comments