  We study the epidemic source detection problem in contact tracing networks
modeled as a graph-constrained maximum likelihood estimation problem using the
susceptible-infected model in epidemiology. Based on a snapshot observation of
the infection subgraph, we first study finite degree regular graphs and regular
graphs with cycles separately, thereby establishing a mathematical equivalence
in maximal likelihood ratio between the case of finite acyclic graphs and that
of cyclic graphs. In particular, we show that the optimal solution of the
maximum likelihood estimator can be refined to distances on graphs based on a
novel statistical distance centrality that captures the optimality of the
nonconvex problem. An efficient contact tracing algorithm is then proposed to
solve the general case of finite degree-regular graphs with multiple cycles.
Our performance evaluation on a variety of graphs shows that our algorithms
outperform the existing state-of-the-art heuristics using contact tracing data
from the SARS-CoV 2003 and COVID-19 pandemics by correctly identifying the
superspreaders on some of the largest superspreading infection clusters in
Singapore and Taiwan.
