Random Walks on Complex Networks

We investigate random walks on complex networks and derive an exact expression for the mean first-passage time (MFPT) between two nodes. We introduce for each node the random walk centrality $C$, which is the ratio between its coordination number and a characteristic relaxation time, and show that it determines essentially the MFPT. The centrality of a node determines the relative speed by which a node can receive and spread information over the network in a random process. Numerical simulations of an ensemble of random walkers moving on paradigmatic network models confirm this analytical prediction.

Figure 1

(a) $\tau$ vs $K$ and (b) $C$ vs $K$ calculated in the Barabási-Albert network with $N=10000$ and $m=2$. The straight line in (b) has the slope 1.

Figure 2

Time evolution of the fraction of walkers $n$ that pass through a node as a function of (from top to bottom) the node index $i$, the node degree $K$ and the RWC $C$ of the BA network (left column) and the hierarchical network (right column). The value of $n$ at each time $t$ is represented in the gray scale/color code depicted at the right border of each plot.