2025/09/24 by Hugo P. Maia, Maia, Hugo P., Wesley Cota +5
Computer Science · Engineering · Physics and Astronomy · #Biological network #Complex Network Analysis Techniques #Complex system #Computational complexity theory #Dynamical systems theory #Efficient algorithm #Evacuation and Crowd Dynamics #Heterogeneous network #Markov process #Opportunistic and Delay-Tolerant Networks #Scaling
paper · pdf · doi:10.1038/s41467-026-75402-0
published in Nature Communications (Nature Portfolio)
openalex publication_date 2026/07/15 · openalex created_date 2026/07/16 · openalex updated_date 2026/08/05
Higher-order interactions, where groups of nodes interact collectively rather than pairwisely, are central to many complex systems, from neural and ecological networks to social contagion. However, simulating dynamical processes on such higher-order structures remains computationally challenging due to the combinatorial growth of possible interactions. Here, we develop efficient and statistically exact Gillespie algorithms for Markovian spreading dynamics on large and heterogeneous hypergraphs. By incorporating phantom processes − events that advance time without altering the system’s state − , we drastically reduce the computational complexity of standard algorithms (O(N2)), achieving up to linear scaling with system size. Relying on the susceptible-infected-susceptible model with critical mass thresholds as a benchmark, we show that the optimized algorithms outperform standard approaches by several orders of magnitude, enabling simulations of networks with millions of nodes and broad heterogeneity in both degree and interaction order. Efficient sampling methods, needed to overcome the bottlenecks imposed by either a high maximum order or number of interactions, and other dynamical processes on higher-order networks are tackled. These results establish a general framework for scalable, continuous-time simulations of higher-order contagion and related dynamical processes. Higher-order interactions, where groups of nodes interact collectively rather than in pairs, are central to social contagion dynamics. Here, the authors develop efficient and exact Gillespie algorithms for spreading dynamics on large and heterogeneous hypergraphs, significantly reducing computational complexity.