论文
arXiv
ComplexNetwork
中文标题
基于游走的拉普拉斯算子用于建模复杂网络上的扩散过程
English Title
Walk based Laplacians for Modeling Diffusion on Complex Networks
Francesca Arrigo, Fabio Durastante
发布时间
2026/1/16 22:36:08
来源类型
preprint
语言
en
摘要
中文对照

我们提出一种新颖的框架,通过构造基于图上游走的类拉普拉斯算子来建模复杂网络上的扩散过程。该方法引入一族参数化的游走型拉普拉斯算子,通过排除或削弱回溯轨迹(即游走者立即重访已访问节点的路径)自然地纳入记忆效应。该框架包含三类算子:(i) 统计网络中所有遍历路径的游走型拉普拉斯;(ii) 非回溯变体,完全消除即时反向移动;(iii) 回溯降权变体,在上述两类之间提供连续插值。我们证明这些算子扩展了标准拉普拉斯算子的定义,并保留其部分性质。我们采用Krylov子空间方法设计高效算法以计算这些算子,确保所提框架可扩展至大规模网络。在真实世界网络上开展的大量数值实验验证了该方法的建模灵活性,并证实所提算法具备良好的计算效率,包括支持GPU加速。

English Original

We develop a novel framework for modeling diffusion on complex networks by constructing Laplacian-like operators based on walks around a graph. Our approach introduces a parametric family of walk-based Laplacians that naturally incorporate memory effects by excluding or downweighting backtracking trajectories, where walkers immediately revisit nodes. The framework includes: (i) walk-based Laplacians that count all traversals in the network; (ii) nonbacktracking variants that eliminate immediate reversals; and (iii) backtrack-downweighted variants that provide a continuous interpolation between these two regimes. We establish that these operators extend the definition of the standard Laplacian and also preserve some of its properties. We present efficient algorithms using Krylov subspace methods for computing them, ensuring applicability of our proposed framework to large networks. Extensive numerical experiments on real-world networks validate the modeling flexibility of our approach and demonstrate the computational efficiency of the proposed algorithms, including GPU acceleration.

元数据
arXiv2601.11338v2
来源arXiv
类型论文
抽取状态raw
关键词
ComplexNetwork
cs.SI
math.NA