Markov chain approach to anomalous diffusion on Newman-Watts networks

Abstract

A Markov chain (MC) formalism is used to investigate the mean-square displacement (MSD) of a random walker on Newman-Watts (NW) networks. It leads to a precise analysis of the conditions for the emergence of anomalous sub- or super-diffusive regimes in such random media. Whereas results provided by most numerical approaches used so far base their results on the computation of a large number of independent runs over many equivalent substrates, the MC framework is applied only once to each equivalent sample. Starting from the simple cycle graph with $2k$ nearest neighbor connections, for which exact MSD expressions within the MC formalism can be derived, the randomness and complexity of the substrate is easily controlled by the number $x$ of added links. Results for different values of $k$, $x$, and the number $N$ of nodes make it possible to distinguish actual anomalous regimes from transient behavior and finite size effects. Albeit the high computing cost restricts the size of our networks to $N\le 1500$ nodes, our very precise results justify a new and more comprehensive scaling ansatz for walker dynamics, from which the behavior for very large networks can be derived.

arXiv comment24 pages, 13 figures

References in corpus (25)

• Epidemic processes in complex networks
• Random graphs with arbitrary degree distributions and their applications
• Renormalization group analysis of the small-world network model
• Random walks and diffusion on networks
• Mean-field solution of the small-world network model
• Diffusion, localization and dispersion relations on ``small-world'' lattices
• A network analysis of countries' export flows: firm grounds for the building blocks of the economy
• Exploring complex networks by walking on them
• Random walks on weighted networks
• Exactly solvable analogy of small-world networks
• Fractional dynamics on networks: Emergence of anomalous diffusion and Lévy flights
• Relaxation Properties of Small-World Networks
• Random spread on the family of small-world networks
• Scaling Properties of Random Walks on Small-World Networks
• Random walk and trapping processes on scale-free networks
• Exact results and scaling properties of small-world networks
• Characterizing the structure of small-world networks
• Path Laplacian operators and superdiffusive processes on graphs. I. One-dimensional case
• Scaling of random spreading in small world networks
• Random Multi-Hopper Model. Super-Fast Random Walks on Graphs
• Path Laplacian operators and superdiffusive processes on graphs. II. Two-dimensional lattice
• Neighborhood properties of complex networks
• Walks on Apollonian networks
• Traversal Times for Random Walks on Small-World Networks
• Onset of anomalous diffusion from local motion rules