Several variants of the graph Laplacian have been introduced to model non-local diffusion processes, which allow a random walker to “jump” 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′ 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′ is not compatible with the dynamics characterizing the original model graph G: the random walks on G′ 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′ with G means that the normalized graph Gˆ can not be embedded into the normalized graph Gˆ′. Eventually, we provide a regularization method to guarantee such compatibility and preserving at the same time all the nice properties granted by G′.

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

Donatelli M.;Mazza M.
2022-01-01

Abstract

Several variants of the graph Laplacian have been introduced to model non-local diffusion processes, which allow a random walker to “jump” 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′ 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′ is not compatible with the dynamics characterizing the original model graph G: the random walks on G′ 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′ with G means that the normalized graph Gˆ can not be embedded into the normalized graph Gˆ′. Eventually, we provide a regularization method to guarantee such compatibility and preserving at the same time all the nice properties granted by G′.
2022
2022
Fractional graph Laplacian; Non-local dynamics; Path graph Laplacian
Bianchi, D.; Donatelli, M.; Durastante, F.; Mazza, M.
File in questo prodotto:
File Dimensione Formato  
bianchi 2022 jmaa.pdf

embargo fino al 01/07/2026

Tipologia: Versione Editoriale (PDF)
Licenza: Creative commons
Dimensione 2 MB
Formato Adobe PDF
2 MB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11383/2131124
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 7
  • ???jsp.display-item.citation.isi??? 5
social impact