Walk based Laplacians for Modeling Diffusion on Complex Networks
For researchers studying diffusion processes on networks, this work provides a more flexible modeling tool that captures memory effects, though it is an incremental extension of existing Laplacian frameworks.
This paper introduces a parametric family of walk-based Laplacians for modeling diffusion on complex networks, which incorporate memory effects by excluding or downweighting backtracking trajectories. The framework includes nonbacktracking and backtrack-downweighted variants, and experiments on real-world networks demonstrate modeling flexibility and computational efficiency with GPU acceleration.
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.