Issue |
Math. Model. Nat. Phenom.
Volume 18, 2023
|
|
---|---|---|
Article Number | 2 | |
Number of page(s) | 23 | |
Section | Mathematical methods | |
DOI | https://doi.org/10.1051/mmnp/2022048 | |
Published online | 19 January 2023 |
Epicenter of random epidemic spanning trees on finite graphs*
1 Department of Systems Engineering and Computer Science (PESC), Federal University of Rio de Janeiro (UFRJ),
Rio de Janeiro,
Brazil
2 Department of Statistical Methods (DME/IM), Federal University of Rio de Janeiro (UFRJ),
Rio de Janeiro,
Brazil
** Corresponding author: giulio@im.ufrj.br
Received:
3
May
2022
Accepted:
21
November
2022
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.
Mathematics Subject Classification: 05C85 / 05C80 / 62Mxx / 05C05
Key words: Random spanning trees / source identification / network epidemics / inference in networks
© The authors. Published by EDP Sciences, 2023
This is an Open Access article distributed under the terms of the Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.