Graph theory applications in epidemiology: Network-based modelling of disease spread and vaccination strategies using spanning structures and shortest path frameworks

This study investigates the application of graph-theoretical optimization algorithms in epidemiological modeling to design efficient vaccination strategies. Traditional epidemiological approaches, such as compartmental SIR models, often assume homogeneous mixing, which fails to reflect the heterogeneity of real-world human interactions. To address this limitation, the study applied network-based methods using the SocioPatterns Infectious Disease Dataset collected in a French high school, comprising 327 individuals and approximately 188,000 recorded contacts. Weighted undirected contact networks were constructed and analyzed with Gephi, employing Minimum Spanning Tree (MST) and shortest-path algorithms alongside epidemic simulations. The results revealed that under baseline conditions with no vaccination, the epidemic spread to 81.9% of the population. Targeted vaccination strategies guided by graph-theoretical algorithms significantly reduced epidemic size, peak infection, and epidemic duration. MST-based vaccination reduced epidemic size by up to 67.8% at 30% coverage, while shortest-path targeting achieved a 71.8% reduction. A combined MST and shortest-path strategy outperformed all others, reducing epidemic size by 78.1% under the same conditions. These findings fill a key literature gap by moving beyond descriptive network metrics to prescriptive, algorithm-driven interventions. The study concludes that graph-theoretical strategies offer computationally efficient and scalable frameworks for epidemic control, particularly under resource-constrained conditions. By integrating such models into public health policy, vaccination campaigns can be optimized to save more lives with fewer resources, offering both theoretical advancements and practical contributions to global epidemic preparedness.