A theory of maximum likelihood for weighted infection graphs

We study the problem of parameter estimation based on infection data from an epidemic outbreak on a graph. We assume that successive infections occur via contagion; i.e., transmissions can only spread across existing directed edges in the graph. Our stochastic spreading model allows individual nodes to be infected more than once, and the probability of the transmission spreading across a particular edge is proportional to both the cumulative number of times the source nodes has been infected in previous stages of the epidemic and the weight parameter of the edge. We propose a maximum likelihood estimator for inferring the unknown edge weights when full information is available concerning the order and identity of successive edge transmissions. When the weights take a particular form as exponential functions of a linear combination of known edge covariates, we show that maximum likelihood estimation amounts to optimizing a convex function, and produces a solution that is both consistent and asymptotically normal. Our proofs are based on martingale convergence theorems and the theory of weighted Pólya urns. We also show how our theory may be generalized to settings where the weights are not exponential. Finally, we analyze the case where the available infection data comes in the form of an unordered set of edge transmissions. We propose two algorithms for weight parameter estimation in this setting and derive corresponding theoretical guarantees. Our methods are validated using both synthetic data and real-world data from the Ebola spread in West Africa. 47 pages, 1 figure, 12 tables