Epicenter of random epidemic spanning trees on finite graphs

Daniel R. Figueiredo¹ ; Giulio Iacobelli²

¹ Department of Systems Engineering and Computer Science (PESC), Federal University of Rio de Janeiro (UFRJ), Rio de Janeiro, Brazil
² Department of Statistical Methods (DME/IM), Federal University of Rio de Janeiro (UFRJ), Rio de Janeiro, Brazil

Mathematical modelling of natural phenomena, Tome 18 (2023), article no. 2.

Résumé

Epidemic source detection is the problem of identifying the network node that originated an epidemic from a partial observation of the epidemic process. The problem finds applications in different contexts, such as detecting the origin of rumors in online social media, and has been studied under various assumptions. Different from prior studies, this work considers an epidemic process on a finite graph that starts on a random node (epidemic source) and terminates when all nodes are infected, yielding a rooted and directed epidemic tree that encodes node infections (i.e., a directed spanning tree of the graph with every edge directed away from the epidemic source). Assuming knowledge of the underlying graph and the undirected spanning tree (i.e., the infection edges but not their directions), can the epidemic source be accurately identified? This work tackles this problem by introducing the epicenter, an efficient estimator for the epidemic source, and thus, the direction of every edge in the epidemic tree. When the underlying graph is vertex-transitive the epicenter can be computed in linear time and it coincides with the well-known distance center of the epidemic tree. Moreover, on a complete graph the epicenter is also the most likely estimator for the source. Finally, the accuracy of the epicenter is evaluated numerically on five different graph models and the performance strongly depends on the graph structure, varying from 31% (on complete graphs) to 13% (on sparse power-law graphs). However, for all graph models considered the epicenter exhibited an accuracy higher than the distance center, being three times more accurate on sparse power-law graphs.

Détail

DOI : 10.1051/mmnp/2022048

Bibliographie

[1] S. Bubeck, L. Devroye, G. Lugosi Finding Adam in random growing trees Random Struct. Algor. 2017 158 172

[2] K. Cai, H. Xie, J.C.S. Lui Information spreading forensics via sequential dependent snapshots IEEE/ACM Trans. Netw. 2018 478 491

[3] W. Dong, W. Zhang and C.W. Tan, Rooting out the rumor culprit from suspects, in IEEE International Symposium on Information Theory (2013) 2671–2675.

[4] M. Draief and L. Massouli, Epidemics and rumours in complex networks. Cambridge University Press (2010).

[5] M. Drmota, Random trees: an interplay between combinatorics and probability. Springer Science Business Media (2009).

[6] S. Feizi, M. Medard, G. Quon, M. Kellis, K. Duffy Network infusion to infer information sources in networks IEEE Trans. Netw. Sci. Eng. 2019 402 417

[7] J.A. Firth, J. Hellewell, P. Klepac, S. Kissler, A.J. Kucharski, L.G. Spurgin Using a real-world network to model localized COVID-19 control strategies Nat. Med. 2020 1616 1622

[8] A. Frieze, W. Pegden Looking for vertex number one Ann. Appl. Probab. 2017 582 630

[9] J. Jiang, S. Wen, S. Yu, Y. Xiang, W. Zhou K-center: an approach on the multi-source identification of information diffusion IEEE Trans. Inf. Forensics Secur. 2015 2616 2626

[10] J. Jiang, S. Wen, S. Yu, Y. Xiang, W. Zhou Identifying propagation sources in networks: state-of-the-art and comparative studies IEEE Commun. Surv. Tutor. 2017 465 481

[11] N. Kamiyama Arborescence problems in directed graphs: theorems and algorithms Interdiscip. Inf. Sci. 2014 51 70

[12] P. Klepac, S. Kissler, J. Gog Contagion! The BBC four pandemic - the model behind the documentary Epidemics 2018 49 59

[13] A. Kumar, V.S. Borkar, N. Karamchandani Temporally agnostic rumor-source detection IEEE Trans. Signal Inf. Process. Netw. 2017 316 329

[14] G. Lugosi, A.S. Pereira Finding the seed of uniform attachment trees Electr. J. Probab. 2019 15

[15] W. Luo, W.P. Tay, M. Leng How to identify an infection source with limited observations IEEE J. Selected Topics Signal Process 2014 586 597

[16] M. Newman, Networks. Oxford University Press (2018).

[17] C. Nowzari, V.M. Preciado, G.J. Pappas Analysis and control of epidemics: a survey of spreading processes on complex networks IEEE Control Syst. Mag. 2016 26 46

[18] R. Paluch, X. Lu, K. Suchecki, B.K. Szymañski, J.A. Holyst Fast and accurate detection of spread source in large complex networks Sci. Rep. 2018 1 10

[19] R. Pastor-Satorras, C. Castellano, P. Van Mieghem, A. Vespignani Epidemic processes in complex networks Rev. Mod. Phys. 2015 925

[20] R. Pastor-Satorras, A. Vespignani Epidemic spreading in scale-free networks Phys. Rev. Lett. 2001 3200

[21] P.C. Pinto, P. Thiran, M. Vetterli Locating the source of diffusion in large-scale networks Phys. Rev. Lett. 2012 068702

[22] M. Salathe, M. Kazandjieva, J.W. Lee, P. Levis, M.W. Feldman, J.H. Jones A high-resolution human contact network for infectious disease transmission Proc. Natl. Acad. Sci. 2010 22020 22025

[23] D. Shah, T. Zaman Detecting sources of computer viruses in networks: theory and experiment ACM SIGMETRICS Perf Eval Rev 2010 203 214

[24] D. Shah, T. Zaman Rumor centrality: a universal source detector ACM SIGMETRICS Perf Eval Rev 2012 199 210

[25] S. Shelke, V. Attar Source detection of rumor in social network - a review Online Social Netw. Media 2019 30 42

[26] W. Tang, F. Ji, W.P. Tay Estimating infection sources in networks using partial timestamps IEEE Trans. Inf. Forens. Secur. 2018 3035 3049

[27] P.-D. Yu, C.W. Tan, H.-L. Fu Epidemic source detection in contact tracing networks: epidemic centrality in graphs and message-passing algorithms IEEE J. Selected Top. Signal Process 2022 234 249

[28] K. Zhu, Z. Chen and L. Ying, Catch’em all: Locating multiple diffusion sources in networks with partial observations, in AAAI Conference on Artificial Intelligence (2017).