2025/02/05 by Berné L. Nortier, Simon Dobson, Nortier, Berné L. +3 · 5 citations
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Management and Algorithms
paper · pdf · doi:10.48550/arxiv.2502.03020
One of the defining features of complex networks is the connectivity properties that we observe emerging from local interactions. Recently, hypergraphs have emerged as a versatile tool to model networks with non-dyadic, higher-order interactions. Nevertheless, the connectivity properties of real-world hypergraphs remain largely understudied. In this work we introduce path size as a measure to characterise higher-order connectivity and quantify the relevance of non-dyadic ties for efficient shortest paths in a diverse set of empirical networks with and without temporal information. By comparing our results with simple randomised null models, our analysis presents a nuanced picture, suggesting that non-dyadic ties are often central and are vital for system connectivity, while dyadic edges remain essential to connect more peripheral nodes, an effect which is particularly pronounced for time-varying systems. Our work contributes to a better understanding of the structural organisation of systems with higher-order interactions.