Network heterogeneity and node capacity lead to heterogeneous scaling of fluctuations in random walks on graphs

Abstract

Random walks are one of the best investigated dynamical processes on graphs. A particularly fascinating phenomenon is the scaling relationship of fluctuations $\sigma$ with the average flux $⟨f⟩$. Here we analyze how network topology and nodes with finite capacity lead to deviations from a simple scaling law $\sigma \sim ⟨f{⟩}^{\alpha }$. Sources of randomness are the random walk itself (internal noise) and the fluctuation of the number of walkers (external noise). We obtained exact results for the extreme case of a star network which are indicative of the behavior of large scale systems with a broad degree distribution.The latter are subsequently studied using Monte Carlo simulations. We find that the network heterogeneity amplifies the effects of external noise. By computing the `effective' scaling of each node we show that multiple scaling relationships can coexist in a graph with a heterogeneous degree distribution at an intermediate level of external noise. Finally, we analyze the effect of a finite capacity of nodes for random walkers and find that this also can lead to a heterogeneous scaling of fluctuations.

12 pages, 11 figures

References in corpus (10)

• Maps of random walks on complex networks reveal community structure
• Synchronization in complex networks
• Fluctuation scaling in complex systems: Taylor's law and beyond
• Congestion and centrality in traffic flow on complex networks
• On the universality of the scaling of fluctuations in traffic on complex networks
• Scaling breakdown in flow fluctuations on complex networks
• Extreme events on complex networks
• The effect of bandwidth in scale-free network traffic
• BioLogistics and the Struggle for Efficiency: Concepts and Perspectives
• Phase Synchronization in Railway Timetables