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 consider two closely related problems of finding a small clique of comorbid diseases that corresponds to the highest mortality rate among a given patient population, and finding an incrementally larger clique of diseases containing a given clique of diseases with the highest marginal mortality rate. To tackle these problems, we explore two approaches (i) a mixed integer programming formulation that maximizes a single fractional objective subject to linear constraints, and (ii) an extension of the classical Bron–Kerbosch enumerative algorithm. We conduct a detailed computational study and report results from our experiments with both approaches on datasets derived from 10.6 million de-identified patient electronic health records.