Brunella Spinelli
ABSTRACT
Source localization, the act of finding the originator of a disease or rumor in a network, has become an important problem in sociology and epidemiology. The localization is done using the infection state and time of infection of a few designated sensor nodes; however, maintaining sensors can be very costly in practice.
We propose the first online approach to source localization: We deploy a priori only a small number of sensors (which reveal if they are reached by an infection) and then iteratively choose the best location to place a new sensor in order to localize the source. This approach allows for source localization with a very small number of sensors; moreover, the source can be found while the epidemic is still ongoing. Our method applies to a general network topology and performs well even with random transmission delays.
- F. Altarelli, A. Braunstein, L. Dall'Asta, A. Lage-Castellanos, and R. Zecchina. Bayesian inference of epidemics on networks via belief propagation. Physical review letters, 112(11), 2014.Google Scholar
- A. Barabási and R. Albert. Emergence of scaling in random networks. Science, 286, 1999.Google Scholar
- J. Cáceres, M. Hernando, M. Mora, I. Pelayo, M. Puertas, C. Seara, and D. Wood. On the metric dimension of cartesian products of graphs. SIAM J. Discrete Mathematics, 21(2), 2007. Google ScholarDigital Library
- S. Cauchemez and N. Ferguson. Likelihood-based estimation of continuous-time epidemic models from time-series data: application to measles transmission in london. Journal of the Royal Society Interface, 5(25), 2008.Google ScholarCross Ref
- L. Celis, F. Pavetić, B. Spinelli, and P. Thiran. Budgeted sensor placement for source localization on trees. In LAGOS, 2015.Google ScholarCross Ref
- X. Chen, X. Hu, and C. Wang. Approximability of the minimum weighted doubly resolving set problem. In COCOON, 2014.Google Scholar
- V. Colizza, A. Barrat, M. Barthélemy, and A. Vespignani. The role of the airline transportation network in the prediction and predictability of global epidemics. Proc. of the National Academy of Sciences of the USA, 103(7), 2006.Google ScholarCross Ref
- W. Dong, W. Zhang, and C. Tan. Rooting out the rumor culprit from suspects. In IEEE ISIT, 2013.Google ScholarCross Ref
- B. Ehrenberg. How much is your personal data worth? https://www.theguardian.com/news/datablog/2014/apr/22/how-much-is-personal-data-worth, 2014.Google Scholar
- P. Erdös and A. Rényi. On random graphs. I. Publ. Math. Debrecen, 6, 1959.Google Scholar
- M. Farajtabar, M. Gomez-Rodriguez, M. Zamani, N. Du, H. Zha, and L. Song. Back to the past: Source identification in diffusion networks from partially observed cascades. In AISTATS, 2015.Google Scholar
- D. Golovin and A. Krause. Adaptive submodularity: Theory and applications in active learning and stochastic optimization. Journal of Artificial Intelligence Research, 42, 2011. Google ScholarDigital Library
- H. Gray and P. Odell. On least favorable density functions. SlAM Review, 9, 1967.Google Scholar
- A. Gupta, V. Nagarajan, and R. Ravi. Thresholded covering algorithms for robust and max-min optimization. In International Colloquium on Automata, Languages, and Programming, 2010. Google ScholarDigital Library
- J. Jiang, S. Wen, S. Yu, Y. Xiang, and W. Zhou. Identifying propagation sources in networks: State-of-the-art and comparative studies. IEEE Communication Survey Tutorials, 2014.Google Scholar
- O. Kariv and S. Hakimi. An algorithmic approach to network location problems. ii: The p-medians. SIAM journal of Applied Mathematics, 37, 1979.Google Scholar
- M. Lelarge. Efficient control of epidemics over random networks. In SIGMETRICS/Performance, 2009. Google ScholarDigital Library
- A. Lokhov, M. Mézard, H. Ohta, and L. Zdeborová. Inferring the origin of an epidemic with a dynamic message-passing algorithm. Ph. Review E, 90(1), 2014.Google Scholar
- A. Louni, A. Santhanakrishnan, and K. Subbalakshmi. Identification of source of rumors in social networks with incomplete information. ASE SocialCom, 2015.Google Scholar
- A. Louni and K. Subbalakshmi. A two-stage algorithm to estimate the source of information diffusion in social media networks. IEEE INFOCOM Workshop on Dynamic Social Networks, 2014.Google ScholarCross Ref
- W. Luo and W. Tay. Identifying infection sources in large tree networks. In IEEE SECON, 2012.Google ScholarCross Ref
- W. Luo, W. Tay, and M. Leng. How to identify an infection source with limited observations. IEEE Journal of Sel. Topics in Signal Processing, 8(4), 2014.Google Scholar
- J. McAuley and J. Leskovec. Learning to discover social circles in ego networks. In NIPS, 2012. Google ScholarDigital Library
- OpenFlights. Route dataset. http://openflights.org/data.html#route, 2012.Google Scholar
- M. Penrose. Random Geometric Graphs. Oxford Studies in Probability, 2003.Google ScholarCross Ref
- P. Pinto, P. Thiran, and M. Vetterli. Locating the source of diffusion in large-scale networks. Physical Review Letters, 109, 2012.Google Scholar
- B. Prakash, J. Vreeken, and C. Faloutsos. Spotting culprits in epidemics: How many and which ones? IEEE ICDM, 2012. Google ScholarDigital Library
- D. Shah and T. Zaman. Rumors in a network: Who's the culprit? IEEE Transactions on information theory, 57, 2011. Google ScholarDigital Library
- Z. Somda, M. Meltzer, H. Perry, N. Messonnier, U. Abdulmumini, G. Mebrahtu, M. Sacko, K. Touré, S. O. Ki, T. Okorosobo, W. Alemu, and I. Sow. Cost analysis of an integrated disease surveillance and response system: case of burkina faso, eritrea, and mali. Cost Effectiveness and Resource Allocation, 7(1), 2009.Google Scholar
- B. Spinelli, L. Celis, and P. Thiran. Observer placement for source localization: The effect of budgets and transmission variance. In Allerton Conf., 2016.Google ScholarCross Ref
- B. Spinelli, L. Celis, and P. Thiran. Back to the source: An online approach for sensor placement and source localization. https://arxiv.org/pdf/1702.01056v1.pdf, 2017.Google Scholar
- S. Sundareisan, J. Vreeken, and B. Prakash. Hidden hazards: Finding missing nodes in large graph epidemics. In SIAM SDM, 2015.Google Scholar
- H. Wang, P. Zhang, L. Chen, H. Liu, and C. Zhang. Online diffusion source detection in social networks. In IEEE Neural Networks (IJCNN), 2015.Google Scholar
- S. Zejnilovic, J. Gomes, and B. Sinopoli. Network observability and localization of the source of diffusion based on a subset of vertices. In Allerton Conf., 2013.Google Scholar
- S. Zejnilović, J. Gomes, and B. Sinopoli. Sequential observer selection for source localization. In IEEE GlobalSIP, pages 1220--1224, 2015.Google ScholarCross Ref
- X. Zhang, Y. Zhang, T. Lv, and Y. Yin. Identification of efficient observers for locating spreading source in complex networks. Physica A: Statistical Mechanics and its Applications, 442, 2016.Google Scholar
- L. Zheng and C. Tan. A probabilistic characterization of the rumor graph boundary in rumor source detection. In IEEE DSP, 2015.Google ScholarCross Ref
- K. Zhu, Z. Chen, and L. Ying. Locating the contagion source in networks with partial timestamps. Data Mining and Knowledge Discovery, 2015. Google ScholarDigital Library
- K. Zhu and L. Ying. Information source detection in the SIR model: A sample path based approach. In IEEE ITA, 2013.Google Scholar
- K. Zhu and L. Ying. A robust information source estimator with sparse observations. Computational Social Networks, 1(1), 2014.Google Scholar
Index Terms
- Back To The Source: An Online Approach for Sensor Placement and Source Localization
Recommendations
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 ...
On the problem of k-coverage in mission-oriented mobile wireless sensor networks
The problem of sensor deployment to achieve k-coverage of a field, where every point is covered by at least k sensors, is very critical in the design of energy-efficient wireless sensor networks (WSNs). It becomes more challenging in mission-oriented ...
Demo: A remote sensor placement device for scalable and precise deployment of sensor networks
MobiSys '14: Proceedings of the 12th annual international conference on Mobile systems, applications, and servicesThe goal of this work is to develop a new autonomous capability for remotely deploying precisely located sensor nodes without damaging the sensor nodes in the process. Over the course of the last decade there has been significant interest in research to ...
Comments