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'.

Bianchi, D., Donatelli, M., Durastante, F., Mazza, M. (2022). Compatibility, embedding and regularization of non-local random walks on graphs. JOURNAL OF MATHEMATICAL ANALYSIS AND APPLICATIONS, 511(1) [10.1016/j.jmaa.2022.126020].

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

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
Pubblicato
Rilevanza internazionale
Articolo
Esperti anonimi
Settore MAT/08
Settore MATH-05/A - Analisi numerica
English
Con Impact Factor ISI
Fractional graph Laplacian
Path graph Laplacian
Non-local dynamics
The work of all authors has been partially supported by the GNCS-INdAM.
Bianchi, D., Donatelli, M., Durastante, F., Mazza, M. (2022). Compatibility, embedding and regularization of non-local random walks on graphs. JOURNAL OF MATHEMATICAL ANALYSIS AND APPLICATIONS, 511(1) [10.1016/j.jmaa.2022.126020].
Bianchi, D; Donatelli, M; Durastante, F; Mazza, M
Articolo su rivista
File in questo prodotto:
File Dimensione Formato  
bianchi 2022 jmaa.pdf

solo utenti autorizzati

Tipologia: Versione Editoriale (PDF)
Licenza: Copyright degli autori
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/2108/344052
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 7
  • ???jsp.display-item.citation.isi??? 5
social impact