Cost Effective Outbreak Detection in Networks
Summary
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
- The paper Battle of the Water Sensor Networks provides the data and motivation for placement of sensors in a large network of water pipes.
- The paper by Khalid El-Arini et al Turning Down the Noise in the Blogosphere uses submodularity to improve web-search results with customizable preferences.
