Random walks are among the most fundamental stochastic processes that occur
ubiquitously in various interdisciplinary contexts such as in biological networks, the
foraging of animals, the spread of diseases, in finance, human mobility in cities,
friendship networks, among many other “complex systems”. Generally, random
walks are microscopic models for diffusion processes and play a crucial role in the
development of “random search” strategies. One of the main goals of this field is to
find a strategy that a given set of targets distributed among a larger set is most
quickly visited by the walker. This and similar questions constitute one of the major
motivations and driving forces for the subjects of this book. The analysis of new
random walk strategies, especially those which allow faster exploration of a network
or a subset of it, is highly desirable for many interdisciplinary applications and
interesting from a theoretical point of view. Last but not least, the recent upswing of
online networks such as Google and social networks has launched a huge interest in
stochastic motions on networks. In many of these problems of real life such as in
population dynamics, chaotic motions, the time evolution of stock-market prices and
many others, it is impossible and even meaningless to describe time evolutions using
deterministic equations. Instead, one is interested in extracting a maximum of
“statistical information” from these processes. As a result, many different kinds of
random walk models have been proposed and extensively studied.
Author(s): Thomas Michelitsch, Alejandro Pérez Riascos, Bernard Collet, Andrzej Nowakowski, Franck Nicolleau
Publisher: Wiley-ISTE
Year: 2019
Language: English
Pages: 322
Cover......Page 1
Title Page......Page 3
Copyright Page......Page 4
Contents......Page 5
Preface......Page 9
PART 1. Dynamics on General Networks......Page 17
1.1. Introduction......Page 18
1.2.1. Basic graph theory......Page 19
1.2.2. Networks......Page 21
1.3.1. Laplacian matrix......Page 26
1.3.2. General properties of the Laplacian eigenvalues and eigenvectors......Page 28
1.3.3. Spectra of some typical graphs......Page 30
1.4.1. Function g(L) and general conditions......Page 32
1.4.2. Non-negative symmetric matrices......Page 35
1.4.3. Completely monotonic functions......Page 37
1.5. General properties of g(L)......Page 43
1.5.2. Functions g(L) for regular graphs......Page 44
1.5.3. Locality and non-locality of g(L) in the limit of large networks......Page 45
1.6. Appendix: Laplacian eigenvalues for interacting cycles......Page 47
2.1. Introduction......Page 48
2.2. General properties of the fractional Laplacian......Page 49
2.3. Fractional Laplacian for regular graphs......Page 51
2.4. Fractional Laplacian and type (i) and type (ii) functions......Page 56
2.5. Appendix: Some basic properties of measures......Page 63
3.1. Introduction......Page 70
3.2.1. Characterization of networks: the Laplacian matrix......Page 72
3.2.2. Characterization of random walks on networks: Ergodic Markov chains......Page 73
3.2.3. The fundamental theorem of Markov chains......Page 78
3.2.4. The ergodic hypothesis and theorem......Page 83
3.2.5. Strong law of large numbers......Page 90
3.2.6. Analysis of the spectral properties of the transition matrix......Page 92
3.3. Appendix: further spectral properties of the transition matrix......Page 97
3.4.1. Unique overall probability in bipartite networks......Page 99
3.4.2. Eigenvalue structure of the transition matrix for normal walks in bipartite graphs......Page 100
4.1. Introduction......Page 107
4.2. Random walk strategies and......Page 108
4.2.1. Fractional Laplacian......Page 109
4.2.2. Logarithmic functions of the Laplacian......Page 111
4.2.3. Exponential functions of the Laplacian......Page 112
4.3. Lévy flights on networks......Page 113
4.4. Transition matrix for types (i) and (ii) Laplacian functions......Page 116
4.5. Global characterization of random walk strategies......Page 119
4.5.1. Kemeny’s constant for finite rings......Page 122
4.5.2. Global time τ for irregular networks......Page 124
4.6. Final remarks......Page 126
4.7. Appendix: Functions g(L) for infinite one-dimensional lattices......Page 127
4.8. Appendix: Positiveness of the generalized degree in regular networks......Page 128
5.1. Introduction......Page 130
5.2.1. Fractional diffusion equation......Page 131
5.2.2. Diffusion equation and random walks on networks......Page 133
5.2.3. Fractional random walks with continuous time......Page 135
5.2.4. Fractional average probability of return in an infinite ring......Page 138
5.2.5. Probability p(γ) n (t) for a ring in the limit N →∞......Page 140
5.2.6. Efficiency of the fractional diffusive transport......Page 142
5.3. Fractional quantum transport on networks......Page 146
5.3.1. Continuous-time quantum walks......Page 147
5.3.3. Fractional quantum walks......Page 148
5.3.4. Fractional quantum dynamics on interacting cycles......Page 149
5.3.5. Quantum transport on an infinite ring......Page 151
5.3.6. Efficiency of the fractional quantum transport......Page 154
PART 2. Dynamics on Lattices......Page 156
6.1. Introduction......Page 157
6.2.1. Preliminaries......Page 158
6.2.2. Explicit evaluation of the fractional Laplacian matrix for the infinite ring......Page 161
6.2.3. Fractional Laplacian of the finite ring......Page 166
6.3. Riesz fractional derivative continuum limit kernels of the Fractional Laplacian matrix......Page 167
6.3.1. General continuum limit procedure......Page 168
6.3.2. Infinite space continuum limit......Page 173
6.3.3. Periodic string continuum limit......Page 175
6.4. Concluding remarks......Page 177
6.5. Appendix: fractional Laplacian matrix of the ring......Page 178
6.5.1. Euler’s reflection formula......Page 182
6.5.2. Some useful relations for the infinite ring limit......Page 183
6.5.3. Asymptotic behavior of the fractional Laplacian matrix......Page 186
6.5.4. Canonic representations of the fractional Laplacian in the periodic string (i) and infinite space limit (ii)......Page 189
6.6. Appendix: estimates for the fractional degree in regular networks......Page 191
7.1. Introduction......Page 195
7.2.1. Mean occupation times, long-range moves and first passage quantities......Page 199
7.2.2. Probability generating functions and recurrence behavior......Page 208
7.3. Universal features of the FRW......Page 215
7.4. Recurrence theorem for the fractional random walk on d-dimensional infinite lattices......Page 220
7.5. Emergence of Lévy flights and asymptotic scaling laws......Page 228
7.6. Fractal scaling of the set of distinct nodes ever visited......Page 232
7.7. Transient regime 0 < α < 1 of FRW on the infinite ring......Page 238
7.8. Concluding remarks......Page 245
7.9.1. Properties of F(a) |p|......Page 247
7.9.2. Recurrent limits......Page 248
8.1. Introduction......Page 250
8.2. Markovian walks generated by type (i) and type (ii) Laplacian matrix functions......Page 254
8.3. Continuum limits – infinite network limits......Page 257
8.3.1. The Pearson walk......Page 262
8.3.2. Type (i) Laplacian kernels: Emergence of Brownian motion (Rayleigh flights) and normal diffusion......Page 266
8.3.3. Type (ii) Laplacian density kernels: Emergence of Lévy flights and anomalous diffusion......Page 271
8.3.4. Green’s function – MRT......Page 277
8.3.5. Some brief remarks on self-similar fractal distributions of nodes......Page 281
8.4.1. Emergence of symmetric α-stable limiting transition PDFs......Page 284
8.4.2. Some properties of symmetric α-stable PDFs......Page 288
8.4.3. Spectral dimension of the FRW – Lévy flight......Page 293
8.4.4. Evaluation of some integrals and normalization constants of the fractional Laplacian......Page 295
8.4.5. Regularization and further properties of the fractional Laplacian kernel......Page 300
References......Page 303
Index......Page 313
Other titles from iSTE in Mechanical Engineering and Solid Mechanics......Page 316
