Fractional Dynamics on Networks and Lattices

This book analyzes stochastic processes on networks and regular structures such as lattices by employing the Markovian random walk approach. Part 1 is devoted to the study of local and non-local random walks. It shows how non-local random walk strategies can be defined by functions of the Laplacian matrix that maintain the stochasticity of the transition probabilities. A major result is that only two types of functions are admissible: type (i) functions generate asymptotically local walks with the emergence of Brownian motion, whereas type (ii) functions generate asymptotically scale-free non-local “fractional” walks with the emergence of Lévy flights. In Part 2, fractional dynamics and Lévy flight behavior are analyzed thoroughly, and a generalization of Pólya's classical recurrence theorem is developed for fractional walks. The authors analyze primary fractional walk characteristics such as the mean occupation time, the mean first passage time, the fractal scaling of the set of distinct nodes visited, etc. The results show the improved search capacities of fractional dynamics on networks.

Table of Contents:
Preface ix Part 1 Dynamics on General Networks 1 Chapter 1 Characterization of Networks: the Laplacian Matrix and its Functions 3 1.1. Introduction 3 1.2. Graph theory and networks 4 1.2.1. Basic graph theory 4 1.2.2. Networks 6 1.3. Spectral properties of the Laplacian matrix 11 1.3.1. Laplacian matrix 11 1.3.2. General properties of the Laplacian eigenvalues and eigenvectors 13 1.3.3. Spectra of some typical graphs 15 1.4. Functions that preserve the Laplacian structure 17 1.4.1. Function g(L) and general conditions 17 1.4.2. Non-negative symmetric matrices 20 1.4.3. Completely monotonic functions 22 1.5 General properties of g(L) 28 1.5.1. Diagonal elements (generalized degree) 29 1.5.2. Functions g(L) for regular graphs 29 1.5.3. Locality and non-locality of g(L) in the limit of large networks 30 1.6. Appendix: Laplacian eigenvalues for interacting cycles 32 Chapter 2 The Fractional Laplacian of Networks 33 2.1. Introduction 33 2.2. General properties of the fractional Laplacian 34 2.3. Fractional Laplacian for regular graphs 36 2.4. Fractional Laplacian and type (i) and type (ii) functions 41 2.5. Appendix: Some basic properties of measures 48 Chapter 3 Markovian Random Walks on Undirected Networks 55 3.1. Introduction 55 3.2. Ergodic Markov chains and random walks on graphs 57 3.2.1. Characterization of networks: the Laplacian matrix 57 3.2.2. Characterization of random walks on networks: Ergodic Markov chains 58 3.2.3. The fundamental theorem of Markov chains 63 3.2.4. The ergodic hypothesis and theorem 68 3.2.5. Strong law of large numbers 75 3.2.6. Analysis of the spectral properties of the transition matrix 77 3.3 Appendix: further spectral properties of the transition matrix Π 82 3.4. Appendix: Markov chains and bipartite networks 84 3.4.1. Unique overall probability in bipartite networks 84 3.4.2. Eigenvalue structure of the transition matrix for normal walks in bipartite graphs 85 Chapter 4 Random Walks with Long-range Steps on Networks 93 4.1. Introduction 93 4.2 Random walk strategies and g(L) 94 4.2.1. Fractional Laplacian 95 4.2.2. Logarithmic functions of the Laplacian 97 4.2.3. Exponential functions of the Laplacian 98 4.3. Lévy flights on networks 99 4.4. Transition matrix for types (i) and (ii) Laplacian functions 102 4.5. Global characterization of random walk strategies 105 4.5.1. Kemeny’s constant for finite rings 108 4.5.2. Global time τ for irregular networks 110 4.6. Final remarks 112 4.7. Appendix: Functions g(L) for infinite one-dimensional lattices 113 4.8. Appendix: Positiveness of the generalized degree in regular networks 114 Chapter 5 Fractional Classical and Quantum Transport on Networks 117 5.1. Introduction 117 5.2. Fractional classical transport on networks 118 5.2.1. Fractional diffusion equation 118 5.2.2. Diffusion equation and random walks on networks 120 5.2.3. Fractional random walks with continuous time 122 5.2.4. Fractional average probability of return in an infinite ring 125 5.2.5 Probability pn(γ)(t) for a ring in the limit N → ∞ 127 5.2.6. Efficiency of the fractional diffusive transport 129 5.3. Fractional quantum transport on networks 133 5.3.1. Continuous-time quantum walks 134 5.3.2. Fractional Schrödinger equation 135 5.3.3. Fractional quantum walks 135 5.3.4. Fractional quantum dynamics on interacting cycles 136 5.3.5. Quantum transport on an infinite ring 138 5.3.6. Efficiency of the fractional quantum transport 141 Part 2 Dynamics on Lattices 143 Chapter 6 Explicit Evaluation of the Fractional Laplacian Matrix of Rings 145 6.1. Introduction 145 6.2. The fractional Laplacian matrix on rings 146 6.2.1. Preliminaries 146 6.2.2. Explicit evaluation of the fractional Laplacian matrix for the infinite ring 149 6.2.3. Fractional Laplacian of the finite ring 154 6.3. Riesz fractional derivative continuum limit kernels of the Fractional Laplacian matrix 155 6.3.1. General continuum limit procedure 156 6.3.2. Infinite space continuum limit 161 6.3.3. Periodic string continuum limit 163 6.4. Concluding remarks 165 6.5. Appendix: fractional Laplacian matrix of the ring 166 6.5.1. Euler’s reflection formula 170 6.5.2. Some useful relations for the infinite ring limit 171 6.5.3. Asymptotic behavior of the fractional Laplacian matrix 174 6.5.4. Canonic representations of the fractional Laplacian in the periodic string (i) and infinite space limit (ii) 177 6.6. Appendix: estimates for the fractional degree in regular networks 179 Chapter 7 Recurrence and Transience of the “Fractional Random Walk” 183 7.1. Introduction 183 7.2. General random walk characteristics 187 7.2.1. Mean occupation times, long-range moves and first passage quantities 187 7.2.2. Probability generating functions and recurrence behavior 196 7.3. Universal features of the FRW 203 7.4. Recurrence theorem for the fractional random walk on d-dimensional infinite lattices 208 7.5. Emergence of Lévy flights and asymptotic scaling laws 216 7.6. Fractal scaling of the set of distinct nodes ever visited 220 7.7. Transient regime 0 <α<1 of FRW on the infinite ring 226 7.8. Concluding remarks 233 7.9. Appendix: Recurrence and transience of FRW 235 7.9.1. Properties of F(α)|p| 235 7.9.2. Recurrent limits 236 Chapter 8 Asymptotic Behavior of Markovian Random Walks Generated by Laplacian Matrix Functions 239 8.1. Introduction 239 8.2. Markovian walks generated by type (i) and type (ii) Laplacian matrix functions 243 8.3. Continuum limits – infinite network limits 246 8.3.1. The Pearson walk 251 8.3.2. Type (i) Laplacian kernels: Emergence of Brownian motion (Rayleigh flights) and normal diffusion 255 8.3.3. Type (ii) Laplacian density kernels: Emergence of Lévy flights and anomalous diffusion 260 8.3.4. Green’s function – MRT 266 8.3.5. Some brief remarks on self-similar fractal distributions of nodes 270 8.4. Appendix 273 8.4.1. Emergence of symmetric α-stable limiting transition PDFs 273 8.4.2. Some properties of symmetric α-stable PDFs 277 8.4.3. Spectral dimension of the FRW – Lévy flight 282 8.4.4. Evaluation of some integrals and normalization constants of the fractional Laplacian 284 8.4.5. Regularization and further properties of the fractional Laplacian kernel 289 References 293 Index 303