Abstract Sexually transmitted infections (STIs) remain a pressing public health concern, spreading primarily through sexual-contact networks whose structure plays a decisive role in epidemic dynamics. Previous studies have reported that Susceptible–Infected–Susceptible (SIS) dynamics on networks combining heterosexual, homosexual, and bisexual contacts—nonbipartite networks—display lower epidemic thresholds than those observed in heterosexual-only (bipartite) networks. This observation raised the question of whether bipartivity alone accounts for these differences. In this work, we construct bipartite graphs that can display epidemic thresholds equal to or smaller than those of their nonbipartite counterparts, demonstrating that bipartivity per se is not the determining factor. Instead, epidemic behavior is driven by the contribution of small subgraphs—such as edges, short paths, triangles, and squares—to the total communicability of vertices. Graphs with identical numbers of vertices, edges, and degree sequences tend to exhibit faster dynamics and lower epidemic thresholds when they contain more triangles, favoring nonbipartite networks. However, bipartite networks can surpass nonbipartite ones when contributions from longer paths or squares outweigh the influence of triangles. These findings are validated on small graphs, random graph models, and real-world sexual-contact networks.
Abstract Relevance to Life Sciences: From a biological and epidemiological perspective, our results show that STI transmission is shaped not simply by the presence or absence of heterosexual versus same-sex contacts, but by the fine-scale structure of sexual interactions. In particular, tightly interconnected patterns of contacts—such as triangles and triangle-related motifs—act as local amplification mechanisms that accelerate transmission, while other configurations, such as longer chains and square-like structures, can also sustain spread even in populations lacking same-sex contacts. These results highlight that individuals embedded in specific relational patterns may disproportionately influence epidemic outcomes, independent of their number of partners. By explicitly linking sexual-network motifs to infection dynamics, this work provides a mechanistic basis for understanding heterogeneity in STI spread and suggests that prevention strategies targeting structurally critical patterns of interaction may be more effective than uniform interventions. Such insights are directly relevant for the design of targeted public health campaigns, risk assessment, and network-informed disease mitigation strategies.
Abstract Mathematical Content: Methodologically, our approach is grounded in a linearized formulation of the SIS model, which yields an upper bound on the number of infected individuals relative to the full nonlinear dynamics. Within this framework, we derive analytical bounds for the epidemic threshold using trace inequalities and tools from algebraic graph theory. A notable contribution is a new and concise proof of a result by Nikiforov concerning the spectral radius of the adjacency matrix, obtained here via matrix trace inequalities. To characterize disease propagation, we establish bounds expressed in terms of total communicability and the Estrada index, linking matrix functions of the adjacency matrix to the contribution of small graph motifs. These results formally demonstrate how edges, short paths, triangles, and squares govern SIS dynamics, and are further supported by extensive computational simulations on artificial, random, and empirical sexual-contact networks.