Higher-order shortest paths in hypergraphs
arXiv:2502.03020 · doi:10.1103/1mxy-3cnl
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.
Accepted version, 10 pages and 6 figures. Several sections updated, figures changed, supplementary added. For supplementary materials, see https://github.com/joanne-b-nortier/higher-order-shortest-paths
References in corpus (35)
- Efficient Behavior of Small-World Networks
- Temporal Networks
- Synchronization in small-world systems
- Networks beyond pairwise interactions: structure and dynamics
- The physics of higher-order interactions in complex systems
- Simplicial models of social contagion
- Communicability in complex networks
- Activity driven modeling of time varying networks
- Small But Slow World: How Network Topology and Burstiness Slow Down Spreading
- Evolutionary dynamics of higher-order interactions in social networks
- Simplicial Closure and higher-order link prediction
- What are higher-order networks?
- Explosive higher-order Kuramoto dynamics on simplicial complexes
- Contact patterns among high school students
- Causality-Driven Slow-Down and Speed-Up of Diffusion in Non-Markovian Temporal Networks
- Higher-order interactions in complex networks of phase oscillators promote abrupt synchronization switching
- Can co-location be used as a proxy for face-to-face contacts?
- Higher-order interactions shape collective dynamics differently in hypergraphs and simplicial complexes
- Social contagion models on hypergraphs
- Analytical computation of the epidemic threshold on temporal networks
- Simplicial Activity Driven Model
- Higher-order motif analysis in hypergraphs
- Hypergraph reconstruction from network data
- Components in time-varying graphs
- Explosive cooperation in social dilemmas on higher-order networks
- The temporal dynamics of group interactions in higher-order social networks
- Community Detection in Large Hypergraphs
- Equivalence between non-Markovian and Markovian dynamics in epidemic spreading processes
- Randomized reference models for temporal networks
- Hypergraphx: a library for higher-order network analysis
- Percolation and Topological Properties of Temporal Higher-order Networks
- Randomizing hypergraphs preserving degree correlation and local clustering
- Exact and sampling methods for mining higher-order motifs in large hypergraphs
- Random graphs with arbitrary clustering and their applications
- The structural evolution of temporal hypergraphs through the lens of hyper-cores