Infodemic Source Detection with Information Flow: Foundations and Scalable Computation

We consider the problem of identifying the source of a rumor in a network, given only a snapshot observation of infected nodes after the rumor has spread. Classical approaches, such as the maximum likelihood (ML) and joint maximum likelihood (JML) estimators based on the conventional Susceptible-Infectious (SI) model, exhibit degeneracy, failing to uniquely identify the source even in simple network structures. To address these limitations, we propose a generalized estimator that incorporates independent random observation times. To capture the structure of information flow beyond graphs, our formulations consider rate constraints on the rumor and the multicast capacities for cyclic polylinking networks. Furthermore, we develop forward elimination and backward search algorithms for rate-constrained source detection and validate their effectiveness and scalability through comprehensive simulations. Our study establishes a rigorous and scalable foundation on the infodemic source detection.