Mathematical Modeling of Disease Spread Using Graph Theory and Network Analysis

Abstract

This paper presents a theoretical framework for modelling infectious disease spread using graph-theoretical approaches and network-based optimization algorithms. Classical compartmental models, such as the SIR system, are extended to a network representation where individuals are represented as nodes and epidemiologically relevant contacts are represented as edges, enabling the study of heterogeneity in transmission dynamics. The model evaluates three vaccination strategies, random immunization, Minimum Spanning Tree (MST) targeting, and shortest-path targeting, to determine their relative efficiency under limited vaccine coverage. Simulations demonstrate that targeted strategies dramatically outperform random vaccination, reducing final epidemic size by up to 67.8 percent (MST) and 71.8 percent (shortest-path) at 30 percent coverage. These results are consistent with percolation theory, showing that strategic node removal fragments the susceptible network and raises the epidemic threshold. The analysis highlights that MST targeting ensures cluster coverage with minimal redundancy, while shortest-path targeting disrupts the most efficient transmission routes, leading to delayed epidemic peaks and flatter curves. By operationalizing graph-theoretical constructs for vaccination planning, this study bridges descriptive epidemiological modelling with prescriptive public health interventions, offering a scalable and resource-efficient framework for epidemic preparedness.