Epidemic Source Detection in Contact Tracing Networks: Epidemic Centrality in Graphs and Message-Passing Algorithms
IEEE Journal on Selected Topics in Signal Processing
; 2022.
Article
in English
| Scopus | ID: covidwho-1731027
ABSTRACT
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. IEEE
Clustering algorithms; Diseases; Estimation; Graph theory; Graphic methods; Maximum likelihood estimation; Message passing; Optimization; SARS; Constrained maximum likelihood estimations; Contact tracing; Detection problems; Estimation problem; Finite degree; Mathematical equivalences; Message-passing algorithm; Regular graphs; Source detection; Subgraphs; Epidemiology
Full text:
Available
Collection:
Databases of international organizations
Database:
Scopus
Language:
English
Journal:
IEEE Journal on Selected Topics in Signal Processing
Year:
2022
Document Type:
Article
Similar
MEDLINE
...
LILACS
LIS