论文
arXiv
ComplexNetwork
中文标题
超图上的最大熵随机游走
English Title
Maximum-Entropy Random Walks on Hypergraphs
Anqi Dong, Anzhi Sheng, Xin Mao, Can Chen
发布时间
2026/3/13 00:03:30
来源类型
preprint
语言
en
摘要
中文对照

随机游走是分析复杂网络化系统(如社交网络、生物系统和通信基础设施)的基本工具。经典随机游走聚焦于成对交互,而许多现实系统天然呈现高阶交互,更适合用超图建模。现有超图随机游走模型多局限于无向结构,或未引入基于熵的推断,因而难以刻画复杂系统中的方向性流动、不确定性或信息扩散。本文构建了一种面向有向超图的最大熵随机游走框架,涵盖两类交互机制:广播式(一个中心节点激活多个接收节点)与融合式(多个中心节点共同影响一个接收节点)。我们通过 KL 散度投影方法,在满足随机性和平稳性约束条件下推断转移核;所得最优性条件表现为乘性缩放形式,并采用 Sinkhorn–Schrödinger 类型迭代结合张量缩并实现。我们进一步分析遍历性:广播式对应投影线性核,融合式则依赖张量谱准则刻画其多项式动力学行为。该框架的有效性通过合成数据与真实世界案例得到验证。

English Original

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.

元数据
arXiv2603.12098v1
来源arXiv
类型论文
抽取状态raw
关键词
ComplexNetwork
eess.SY
math.CO
math.OC