Identifying Most Lethal Cliques in Disease Comorbidity Graphs

Abstract

Mortality rate refers to the overall likelihood of death within a specific population over a defined period. The knowledge of high mortality rate disease clusters can enable healthcare providers and patients to be proactive and develop tailored interventions that improve patient outcomes. In this paper, we introduce a methodology for systematically incorporating electronic health record data in an optimization framework to find cliques of comorbid diseases that correspond to the highest mortality rates among a given patient population. To this end, we introduce the maximum mortality rate clique problem and devise two approaches to solve it (i) we formulate a mathematical optimization model that maximizes a fractional objective function subject to linear constraints in binary variables, which we reformulate as a mixed-integer linear program and solve using a commercial solver with delayed constraint generation, and (ii) we design an enumerative combinatorial algorithm based on the classical Bron–Kerbosch algorithm for enumerating maximal cliques. We conduct a detailed computational study and report results from our experiments with both approaches on a test bed of instances derived from millions of de-identified patient electronic health records.