Cost Effective Outbreak Detection in Networks

From Cohen Courses
Jump to navigationJump to search


This work proposes a method that exploits the property of Submodularity of commonly used cost functions in order to efficiently define a (near) optimal sensor-placement strategy.

Two different data sets provide both their motivation and application: A Water Sensor Network and a Network of Blogs

The first setting corresponds to intelligently placing sensors in a water distribution system so that any contaminants can be reliably and quickly detected. Different cost functions associated with this problem are; placing sensors to minimize detection time, placing sensors to minimize the total affected population of people, and placing sensors under a limited budget.

For the blog data, the same methods are applied to detect information cascades as opposed to contaminants (although, these can be thought of as one and the same). However, instead of sensors the blog domain is reporting which blogs an interested user should read in order to 'keep up' with it all. Users may be interested in reading blogs that let them be the 'first to know' (minimizing time to detect) or ones that will eventually catch most of the cascades.

In both settings, submodularity is used to speed up the algorithm as well as give theoretical bounds for its performance. The results for the water pipe network earned them a first place finish in the Battle of the Water Sensor Networks

Related papers