Unraveling Contagion Origins: Optimal Estimation through Maximum-Likelihood and Starlike Tree Approximation in Markovian Spreading Models

Identifying the source of epidemic-like spread in networks is crucial for tasks like removing internet viruses or finding the rumor source in online social networks. The challenge lies in tracing the source from a snapshot observation of infected nodes. How do we accurately pinpoint the source? Utilizing snapshot data, we apply a probabilistic approach, focusing on the graph boundary and the observed time, to detect sources via an effective maximum likelihood algorithm. A novel starlike tree approximation extends applicability to general graphs, demonstrating versatility. We highlight the utility of the Gamma function for analyzing the asymptotic behavior of the likelihood ratio between nodes. Comprehensive evaluations confirm algorithmic effectiveness in diverse network scenarios, advancing rumor source detection in large-scale network analysis and information dissemination strategies.