Maximum-Entropy Random Walks on Hypergraphs
This provides a method for analyzing directional flows and information diffusion in complex systems like social or biological networks, though it appears incremental as it extends existing hypergraph random walk models with entropy-based inference.
The authors tackled the problem of modeling random walks on hypergraphs with higher-order interactions by developing a maximum-entropy framework for directed hypergraphs, resulting in a transition kernel derived via Kullback-Leibler divergence projection and implemented with Sinkhorn–Schrödinger-type iterations.
Random walks are fundamental tools for analyzing complex networked systems, including social networks, biological systems, and communication infrastructures. While classical random walks focus on pairwise interactions, many real-world systems exhibit higher-order interactions naturally modeled by hypergraphs. Existing random walk models on hypergraphs often focus on undirected structures or do not incorporate entropy-based inference, limiting their ability to capture directional flows, uncertainty, or information diffusion in complex systems. In this article, we develop a maximum-entropy random walk framework on directed hypergraphs with two interaction mechanisms: broadcasting where a pivot node activates multiple receiver nodes and merging where multiple pivot nodes jointly influence a receiver node. We infer a transition kernel via a Kullback--Leibler divergence projection onto constraints enforcing stochasticity and stationarity. The resulting optimality conditions yield a multiplicative scaling form, implemented using Sinkhorn--Schrödinger-type iterations with tensor contractions. We further analyze ergodicity, including projected linear kernels for broadcasting and tensor spectral criteria for polynomial dynamics in merging. The effectiveness of our framework is demonstrated with both synthetic and real-world examples.