Zipf and Heaps laws from dependency structures in component systems

Complex natural and technological systems can be considered, on a coarse-grained level, as assemblies of elementary components: for example, genomes as sets of genes or texts as sets of words. On one hand, the joint occurrence of components emerges from architectural and specific constraints in such systems. On the other hand, general regularities may unify different systems, such as the broadly studied Zipf and Heaps laws, respectively concerning the distribution of component frequencies and their number as a function of system size. Dependency structures (i.e., directed networks encoding the dependency relations between the components in a system) were proposed recently as a possible organizing principles underlying some of the regularities observed. However, the consequences of this assumption were explored only in binary component systems, where solely the presence or absence of components is considered, and multiple copies of the same component are not allowed. Here we consider a simple model that generates, from a given ensemble of dependency structures, a statistical ensemble of sets of components, allowing for components to appear with any multiplicity. Our model is a minimal extension that is memoryless and therefore accessible to analytical calculations. A mean-field analytical approach (analogous to the “Zipfian ensemble” in the linguistics literature) captures the relevant laws describing the component statistics as we show by comparison with numerical computations. In particular, we recover a power-law Zipf rank plot, with a set of core components, and a Heaps law displaying three consecutive regimes (linear, sublinear, and saturating) that we characterize quantitatively.

Figure 1

Illustration of the model. The model is defined by two steps. The first step creates a dependency structure by an incremental node-addition process with mean out-degree $D$ (left panel; the new node on the left attaches to two existing nodes, indicated by dotted lines). The second step builds realizations drawing at random $k$ precursor nodes (larger circles in figure, where $k=2$) and taking all components belonging to their forward “cones” of dependency (shaded in gray). This second step assigns multiplicities to the components appearing in each realization: The abundance of component $i$ is the number of precursors whose forward cones contain $i$. In the realization illustrated in the right panel, the nodes (components) in the light-gray regions have multiplicity 1, while those in the dark-gray region have multiplicity 2.

Figure 2

Simulations match the analytical prediction for the distribution of total abundance in a set of realizations (empirical Zipf's law) and for the abundance-occurrence relation. (a) Rank-plot of component abundances. (b) Rank-plot of component occurrences. (c) Scatterplot of the abundance ($y$ axis) versus the occurrence ($x$ axis) of each component. Colored symbols are results of simulations (1000 realizations) with varying number of precursors $k$, and the dashed lines are the analytical prediction. (Parameters: $U=1000,D=1.5$.)

Figure 3

The model reproduces the characteristic three-regimes structure of Heaps's law. (a) The number of distinct components $F\left(N\right)$ of a realization as a function of realization size $N$ (in log-log scale). The colored circles are simulations, and lighter shades of blue correspond to larger numbers $k$ of precursors ($k$ ranges from 1 to 3000). The red dashed lines are the analytical prediction (17). The area of the solid curves represents the $90\%$ variability interval. (Parameters: $U=500,D=2,13000$ realizations.) (b) The same plot of $F\left(N\right)$, in linear scale, for three values of the mean out-degree $D$: 1 (dark blue), 1.5 (blue), and 2 (light blue). (c) Effective exponent versus realization size for increasing values of $U$ (black- to red-colored lines, ranging logarithmically from $U=10$ to $U\approx 6000$). Triangles correspond to the analytical estimate of $N_c$, which captures well the transition to a plateau region. The analytical estimate of $N_s$ (squares) corresponds to an approximately constant effective exponent.

Figure 4

The stretched exponential is a good approximation of the Heaps plot generated by the model. Number of unique components ($y$ axis, in linear scale) as a function of realization size ($x$ axis, in logarithmic scale), for three different values of $U$, the size of the universe. Simulations are the solid curves (dark blue $U=100$, blue $U=200$, and light blue $U=500$; line width is the $90\%$ variability interval). The dashed red lines are the analytical prediction. (Parameters: $D=1.5,k$ ranging from 1 to 5000.) (Inset) The fitted stretched-exponential exponent $\gamma$ as a function of $U$. Different shades correspond to $D=1,1.25,1.5,1.75,2$, from top to bottom; point size represents errors.

Figure 5

Non-null signatures of component dependency. The distribution of mutual information ($x$ axis), Eq. (30), for the random sampling protocol of Ref. [5] (thick red line) and for the model studied here (thin blue line). The frequency distribution of components was obtained by the positive model (with parameters $U=1000$, $D=1.5,k=50$), and $I(i,j)$ was computed for $R=1000$ realizations of both models. The distribution ($y$ axis) is the normalized empirical distribution for all realizations and all pairs $(i,j)$.