2019/06/07 by S. Jalil Kazemitabar, Arash Amini, Kazemitabar, S. Jalil +1
Medicine · Physics and Astronomy · #Applications (stat.AP) #Complex Network Analysis Techniques #Data-Driven Disease Surveillance #FOS: Computer and information sciences #FOS: Physical sciences #Opinion Dynamics and Social Influence #Physics and Society (physics.soc-ph) #Social and Information Networks (cs.SI)
paper · pdf · doi:10.48550/arxiv.1906.03052
openalex publication_date 2019/06/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider the problem of identifying the source of an epidemic, spreading\nthrough a network, from a complete observation of the infected nodes in a\nsnapshot of the network. Previous work on the problem has often employed\ngeometric, spectral or heuristic approaches to identify the source, with the\ntrees being the most studied network topology. We take a fully statistical\napproach and derive novel recursions to compute the Bayes optimal solution,\nunder a susceptible-infected (SI) epidemic model. Our analysis is time and rate\nindependent, and holds for general network topologies. We then provide two\ntractable algorithms for solving these recursions, a mean-field approximation\nand a greedy approach, and evaluate their performance on real and synthetic\nnetworks. Real networks are far from tree-like and an emphasis will be given to\nnetworks with high transitivity, such as social networks and those with\ncommunities. We show that on such networks, our approaches significantly\noutperform geometric and spectral centrality measures, most of which perform no\nbetter than random guessing. Both the greedy and mean-field approximation are\nscalable to large sparse networks.\n