|
Abstract:
|
In a water distribution network, where should we place sensors to quickly detect contaminants? Or, which blogs should we read to avoid missing important stories? Outbreak detection in both problems can be modeled as selecting nodes 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 exploit the property of 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 evaluate our approach on the two cases mentioned above, showing how the approach leads to deeper insights in both applications, answering criteria trade-off, cost-sensitivity and generalization questions.
|
