Extreme robustness of scaling in sample space reducing processes explains Zipf's law in diffusion on directed networks

Abstract

It has been shown recently that a specific class of path-dependent stochastic processes, which reduce their sample space as they unfold, lead to exact scaling laws in frequency and rank distributions. Such Sample Space Reducing processes (SSRP) offer an alternative new mechanism to understand the emergence of scaling in countless processes. The corresponding power law exponents were shown to be related to noise levels in the process. Here we show that the emergence of scaling is not limited to the simplest SSRPs, but holds for a huge domain of stochastic processes that are characterized by non-uniform prior distributions. We demonstrate mathematically that in the absence of noise the scaling exponents converge to $-1$ (Zipf's law) for almost all prior distributions. As a consequence it becomes possible to fully understand targeted diffusion on weighted directed networks and its associated scaling laws law in node visit distributions. The presence of cycles can be properly interpreted as playing the same role as noise in SSRPs and, accordingly, determine the scaling exponents. The result that Zipf's law emerges as a generic feature of diffusion on networks, regardless of its details, and that the exponent of visiting times is related to the amount of cycles in a network could be relevant for a series of applications in traffic-, transport- and supply chain management.

11 pages, 5 figures

References in corpus (5)

• Graph Evolution: Densification and Shrinking Diameters
• Understanding scaling through history-dependent processes with collapsing sample space
• How multiplicity determines entropy and the derivation of the maximum entropy principle for complex systems
• Random acyclic networks
• Analytical computation of frequency distributions of path-dependent processes by means of a non-multinomial maximum entropy approach

Cited by in corpus (8)

• The three faces of entropy for complex systems -- information, thermodynamics and the maxent principle
• Sample space reducing cascading processes produce the full spectrum of scaling exponents
• Heaps' law, statistics of shared components and temporal patterns from a sample-space-reducing process
• Information geometry of scaling expansions of non-exponentially growing configuration spaces
• From Boltzmann to Zipf through Shannon and Jaynes
• Maximum configuration principle for driven systems with arbitrary driving
• Power-law intensity distribution in $\gamma$-decay cascades -- Nuclear Structure as a Scale-Free Random Network
• Correspondence between noisy sample space reducing process and records in correlated random events