Higher-order shortest paths in hypergraphs
Preprint
Abstract
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.Keywords
All Related Versions
This publication has 33 references indexed in Scilit:
- The temporal dynamics of group interactions in higher-order social networksNature Communications, 2024
- Higher-order correlations reveal complex memory in temporal hypergraphsNature Communications, 2024
- Higher-order interactions shape collective dynamics differently in hypergraphs and simplicial complexesNature Communications, 2023
- The physics of higher-order interactions in complex systemsNature Physics, 2021
- Networks beyond pairwise interactions: Structure and dynamicsPhysics Reports, 2020
- Simplicial models of social contagionNature Communications, 2019
- Causality-driven slow-down and speed-up of diffusion in non-Markovian temporal networksNature Communications, 2014
- Social fMRI: Investigating and shaping social mechanisms in the real worldPervasive and Mobile Computing, 2011
- Navigation in a small worldNature, 2000
- A critical point for random graphs with a given degree sequenceRandom Structures & Algorithms, 1995