Sampling nodes and hyperedges via random walks on large hypergraphs

Abstract

Hypergraphs provide a fundamental framework for representing complex systems involving interactions among three or more entities. As empirical hypergraphs grow in size, characterizing their structural properties becomes increasingly challenging due to computational complexity and, in some cases, restricted access to complete data, requiring efficient sampling methods. Random walks offer a practical approach to hypergraph sampling, as they rely solely on local neighborhood information from nodes and hyperedges. In this study, we investigate methods for simultaneously sampling nodes and hyperedges via random walks on large hypergraphs. First, we compare three existing random walks in the context of hypergraph sampling and identify an advantage of the so-called higher-order random walk. Second, by extending an established technique for graphs to the case of hypergraphs, we present a non-backtracking variant of the higher-order random walk. We derive theoretical results on estimators based on the non-backtracking higher-order random walk and validate them through numerical simulations on large empirical hypergraphs. Third, we apply the non-backtracking higher-order random walk to a large hypergraph of co-authorships indexed in the OpenAlex database, where full access to the data is not readily available. Despite the relatively small sample size, our estimates largely align with previous findings on author productivity, team size, and the prevalence of open-access publications. Our findings contribute to the development of analysis methods for large hypergraphs, offering insights into sampling strategies and estimation techniques applicable to real-world complex systems.

References in corpus (18)

• Networks beyond pairwise interactions: structure and dynamics
• Historical comparison of gender inequality in scientific careers across countries and disciplines
• The physics of higher-order interactions in complex systems
• High-resolution measurements of face-to-face contact patterns in a primary school
• General state space Markov chains and MCMC algorithms
• Random walks and diffusion on networks
• Contact patterns in a high school: a comparison between data collected using wearable sensors, contact diaries and friendship surveys
• Simplicial Closure and higher-order link prediction
• Dynamics on higher-order networks: A review
• Random walks on hypergraphs
• Community Detection in Large Hypergraphs
• Structural Patterns and Generative Models of Real-world Hypergraphs
• Mapping flows on hypergraphs
• Hyperedge overlap drives explosive collective behaviors in systems with higher-order interactions
• Randomizing hypergraphs preserving degree correlation and local clustering
• Exact and sampling methods for mining higher-order motifs in large hypergraphs
• Quantifying gender imbalance in East Asian academia: Research career and citation practice
• Random Walk Sampling in Social Networks Involving Private Nodes