Abstract
Several variants of the graph Laplacian have been introduced to model non-local diffusion pro- cesses, which allow a random walker to “jump” to non-neighborhood nodes, most notably the path graph Laplacians and the fractional graph Laplacian, see [2, 3]. 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 0 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. A natural question arises: are the dynamics on the “old” walks along the edges of G compatible with the new dynamics? Indeed, it would be desirable to introduce long-range jumps but preserving at the same time the original dynamics if we move along the edges of G. In other words, for any time-interval where does not take place any long-range jump, a random walk on G 0 should be indistinguishable from the original random walk on G. One can easily figure this by a simple but clarifying example: let us suppose that our random walker is surfing the Net (the original graph G), and just for the sake of simplicity let us suppose that the Net is undirected. The walker then can move towards linked web-pages with a probability that can be both uniforms on the number of total links or dependent on some other parameters. Suppose now that we allow the walker to jump from one web-page to non-linked web-pages by just typing an URL address in the navigation bar so that he can virtually reach directly any possible web-pages on the Net (the induced graph G 0 ). If in any moment, for any reason, the walker is forced again to surf the Net by just following the links, then we should see him moving exactly as he used to do, namely, the probability he moves to the next linked web-page has to be the same as before. Unfortunately, in general, the induced complete graph G 0 , defined accordingly to the proposal in the literature, breaks that compatibility and the new models cease to be expressions of the original model G. In this talk, we will present some of the main results obtained in [1]. We will first introduce a rigorous definition of compatibility and embedding, which stem from a probabilistic and purely an- alytical point of view, respectively. Secondly, we will propose a regularization method to guarantee such compatibility and preserving at the same time all the nice properties granted by G 0 . References [1] D. Bianchi, M. Donatelli, F. Durastante, M. Mazza. Compatibility, embedding and regularization of non-local random walks on graphs. Preprint (2021), arXiv:2101.00425. [2] E. Estrada. Path Laplacian matrices: introduction and application to the analysis of consensus in networks. Linear Algebra Appl. 436.9 (2012): 3373–3391. [3] A. P. Riascos, J. L. Mateos. Fractional dynamics on networks: Emergence of anomalous diffusion and Lévy flights. Phys. Rev. E 90 (2014): 032809.