Compatibility, embedding and regularization of non-local random walks on graphs

Abstract

Several variants of the graph Laplacian have been introduced to model non-local diffusion processes, which allow a random walker to {\textquotedblleft jump\textquotedblright} to non-neighborhood nodes, most notably the transformed path graph Laplacians and the fractional graph Laplacian. From a rigorous point of view, this new dynamics is made possible by having replaced the original graph $G$ with a weighted complete graph $G^{\prime }$ on the same node-set, that depends on $G$ and wherein the presence of new edges allows a direct passage between nodes that were not neighbors in $G$. We show that, in general, the graph $G^{\prime }$ is not compatible with the dynamics characterizing the original model graph $G$: the random walks on $G^{\prime }$ subjected to move on the edges of $G$ are not stochastically equivalent, in the wide sense, to the random walks on $G$. From a purely analytical point of view, the incompatibility of $G^{\prime }$ with $G$ means that the normalized graph $\hat{G}$ can not be embedded into the normalized graph ${\hat{G}}^{\prime }$. Eventually, we provide a regularization method to guarantee such compatibility and preserving at the same time all the nice properties granted by $G^{\prime }$.

References in corpus (7)

• Random walks on weighted networks
• Long-Range Navigation on Complex Networks using Lévy Random Walks
• Fractional dynamics on networks: Emergence of anomalous diffusion and Lévy flights
• Optimal Lévy-flight foraging in a finite landscape
• Fractional random walk lattice dynamics
• Nonlocal PageRank
• Asymptotic spectra of large (grid) graphs with a uniform local structure

Cited by in corpus (2)

• A simple model of epidemic dynamics with memory effects
• Nonlocal diffusion of variable order on complex networks