Anomalous diffusion on complex networks

From Santa Fe Institute Events Wiki


A standard random walk over a n-dimensional lattice is a stochastic process where the average square of the distance from the origin <r^2> is proportional to the number of steps of the process <t> - namely <r^2>=c<t>, where c is a constant. Among other names of this process in different contexts -Brownian motion, Wiener process- it is mostly known as diffusion. A possible generalization of this process is to define an anomalous case as <r^2>=c(<t>^h). The exponent h fixes the behavior of the walker. If 0<h<1 we have an antipersistent behavior: the walker prefers to return to its original location; on the other hand, if we choose 1<h<2 we will have a persistent behavior: the walker tends to apart from its origin.

This kind of processes are easily mapped to complex networks. The distance is the shortest path length between the original birth node and the node reached at time t. The interesting fact is that even if the exponent of the walker is 1 (this is a random walker), if we put it over a complex network the resulting average behavior will not necessarily be that of a diffusive process. So, there is a topology-induced anomalous diffusion.

Why this matters? Well, many communication processes in networks are well described as local random walks in the sense that the transmission its realized from one node to another randomly choosing between its neighbors. The idea is to run this walkers over different interesting networks - random, small-world, scale-free and real-world ones - to check the differences in the exponent h and also try to explain those differences. In other words, we want to evaluate what effect network structure has on diffusion processes.