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. Levy 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 Schrodinger 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 Levy 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 Levy 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 – Levy 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
