Local and nonlocal dynamics on graphs: theory and computation

Classical dynamics on graphs, like diffusion and random walks, can be defined using the graph Laplacian $L$. In this thesis we investigate fractional dynamics, a generalization of the classical dynamics on graphs: these dynamics are defined by means of a fractional power $L^\alpha$, $\alpha \in (0,1)$, of the graph Laplacian, and they have been recently used to model long-range, nonlocal dynamics on a network, i.e. situations in which the moving agents or particles can also jump directly between non-adjacent nodes, with a probability that is smaller for nodes that are a large distance apart. In order to compare this nonlocal behaviour with the locality of the classical dynamics, we prove power-law decay bounds for the entries of the fractional graph Laplacian, also showing the superdiffusive behaviour of fractional dynamics on infinite path graphs, and performing experiments to reveal the superior efficiency in network exploration of fractional dynamics, compared to the classical ones. The solution to the fractional diffusion equation can be written in the form $f(L) b$, and computed efficiently using rational Krylov methods. We propose some techniques that improve the convergence of Krylov methods for the computation of the non-analytic functions that appear in fractional dynamics, namely a rank-one shift and a subspace projection, and we show their effectiveness with some experiments on real-world graphs using the Shift-and-Invert Krylov method