PMCCPMCCPMCC

Search tips
Search criteria 

Advanced

 
Logo of plosonePLoS OneView this ArticleSubmit to PLoSGet E-mail AlertsContact UsPublic Library of Science (PLoS)
 
PLoS One. 2010; 5(12): e14139.
Published online 2010 December 2. doi:  10.1371/journal.pone.0014139
PMCID: PMC2996287

Zipf's Law Leads to Heaps' Law: Analyzing Their Relation in Finite-Size Systems

Olaf Sporns, Editor

Abstract

Background

Zipf's law and Heaps' law are observed in disparate complex systems. Of particular interests, these two laws often appear together. Many theoretical models and analyses are performed to understand their co-occurrence in real systems, but it still lacks a clear picture about their relation.

Methodology/Principal Findings

We show that the Heaps' law can be considered as a derivative phenomenon if the system obeys the Zipf's law. Furthermore, we refine the known approximate solution of the Heaps' exponent provided the Zipf's exponent. We show that the approximate solution is indeed an asymptotic solution for infinite systems, while in the finite-size system the Heaps' exponent is sensitive to the system size. Extensive empirical analysis on tens of disparate systems demonstrates that our refined results can better capture the relation between the Zipf's and Heaps' exponents.

Conclusions/Significance

The present analysis provides a clear picture about the relation between the Zipf's law and Heaps' law without the help of any specific stochastic model, namely the Heaps' law is indeed a derivative phenomenon from the Zipf's law. The presented numerical method gives considerably better estimation of the Heaps' exponent given the Zipf's exponent and the system size. Our analysis provides some insights and implications of real complex systems. For example, one can naturally obtained a better explanation of the accelerated growth of scale-free networks.

Introduction

Giant strides in Complexity Sciences have been the direct outcome of efforts to uncover the universal laws that govern disparate systems. Zipf's law [1] and Heaps' law [2] are two representative examples. In 1940s, Zipf found a certain scaling law in the distribution of the word frequencies. Ranking all the words in descending order of occurrence frequency and denoting by An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e001.jpg the frequency of the word with rank An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e002.jpg, the Zipf's law reads An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e003.jpg, where An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e004.jpg is the maximal frequency and An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e005.jpg is the so-called Zipf's exponent. This power-law frequency-rank relation indicates a power-law probability distribution of the frequency itself, say An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e006.jpg with An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e007.jpg equal to An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e008.jpg (see Materials and Methods). As a signature of complex systems, the Zipf's law is observed everywhere [3]: these include the distributions of firm sizes [4], wealths and incomes [5], paper citations [6], gene expressions [7], sizes of blackouts [8], family names [9], city sizes [10], personal donations [11], chess openings [12], traffic loads caused by YouTube videos [13], and so on. Accordingly, many mechanisms are put forward to explain the emergence of the Zipf's law [14], [15], such as the rich gets richer [16], [17], the self-organized criticality [18], Markov Processes [19], aggregation of interacting individuals [20], optimization designs [21] and the least effort principle [22]. To name just a few.

Heaps' law [2] can also be applied in characterizing natural language processing, according to which the vocabulary size grows in a sublinear function with document size, say An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e009.jpg with An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e010.jpg, where An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e011.jpg denotes the total number of words and An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e012.jpg is the number of distinct words. One ingredient causing such a sublinear growth may be the memory and bursty nature of human language [23][25]. A particular interesting phenomenon is the coexistence of the Zipf's law and Heaps' law. Gelbukh and Sidorov [26] observed these two laws in English, Russian and Spanish texts, with different exponents depending on languages. Similar results were recently reported for the corpus of web texts [27], including the Industry Sector database, the Open Directory and the English Wikipedia. Besides the statistical regularities of text, the occurrences of tags for online resources [28], [29], keywords for scientific publications [30], words contained by web pages resulted from web searching [31], and identifiers in modern Java, C++ and C programs [32] also simultaneously display the Zipf's law and Heaps' law. Benz et al. [33] reported the Zipf's law of the distribution of the features of small organic molecules, together with the Heaps' law about the number of unique features. In particular, the Zipf's law and Heaps' law are closely related to the evolving networks. It is well-known that some networks grow in an accelerating manner [34], [35] and have scale-free structures (see for example the WWW [36] and Internet [37]), in fact, the former property corresponds to the Heaps' law that the number of nodes grows in a sublinear form with the total degree of nodes, while the latter is equivalent to the Zipf's law for degree distribution.

Baeza-Yates and Navarro [38] showed that the two laws are related: when An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e013.jpg, it can be derived that if both the Zipf's law and Heaps' law hold, An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e014.jpg. By using a more sophisticated approach, Leijenhorst and Weide [39] generalized this result from the Zipf's law to the Mandelbrot's law [40] where An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e015.jpg and An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e016.jpg is a constant. Based on a variant of the Simon model [16], Montemurro and Zanette [41], [42] showed that the Zipf's law is a result from the Heaps' law with An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e017.jpg depending on An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e018.jpg and the modeling parameter. Also based on a stochastic model, Serrano et al. [27] claimed that the Zipf's law can result in the Heaps' law when An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e019.jpg, and the Heaps' exponent is An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e020.jpg. In this paper, we prove that for an evolving system with a stable Zipf's exponent, the Heaps' law can be directly derived from the Zipf's law without the help of any specific stochastic model. The relation An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e021.jpg is only an asymptotic solution hold for very-large-size systems with An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e022.jpg. We will refine this result for finite-size systems with An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e023.jpg and complement it with An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e024.jpg. In particular, we analyze the effects of system size on the Heaps' exponent, which are completely ignored in the literature. Extensive empirical analysis on tens of disparate systems ranging from keyword occurrences in scientific journals to spreading patterns of the novel virus influenza A (H1N1) has demonstrated that the refined results presented here can better capture the relation between Zipf's and Heaps' exponents. In particular, our results agree well with the evolving regularities of the accelerating networks and suggest that the accelerating growth is necessary to keep a stable power-law degree distribution. Whereas the majority of studies on the Heaps' law are limited in linguistics, our work opens up the door to a much wider horizon that includes many complex systems.

Results

Analytical Results

For simplicity of depiction, we use the language of word statistics in text, where An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e025.jpg denotes the frequency of the word with rank An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e026.jpg. However, the results are not limited to language systems. Note that An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e027.jpg is the very number of distinct words with frequency larger than An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e028.jpg. Denoting by An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e029.jpg the total number of word occurrences (i.e., size of the text) and An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e030.jpg the corresponding number of distinct words, then

equation image
(1)

Note that An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e032.jpg with An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e033.jpg a constant. According to the normalization condition An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e034.jpg, when An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e035.jpg and An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e036.jpg (these two conditions are hold for most real systems), An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e037.jpg. Substituting An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e038.jpg in Eq. 1 by An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e039.jpg, we have

equation image
(2)

According to the Zipf's law An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e041.jpg and the relation between the Zipf's and power-law exponents An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e042.jpg, the right part of Eq. 2 can be expressed in term of An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e043.jpg and An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e044.jpg, as

equation image
(3)

Combine Eq. 1 and Eq. 3, we can obtain the estimation of An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e046.jpg, as

equation image
(4)

Obviously, the text size An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e048.jpg is the sum of all words' occurrences, say

equation image
(5)

Notice that the summation An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e050.jpg is larger than the integration An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e051.jpg. The relative error of this approximation, for An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e052.jpg, increases with the increasing of An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e053.jpg and decreases with the increasing of An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e054.jpg (see Figure S1 the numerical results on the sensitivity of relative errors to parameters An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e055.jpg and An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e056.jpg). Substituting An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e057.jpg by Eq. 4, it arrives to the relation between An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e058.jpg and An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e059.jpg:

equation image
(6)

The direct comparison between the empirical observation and Eq. 6, as well as an improved version of Eq. 6, is shown in Materials and Methods. Clearly, Eq. 6 is not a simply power-law form as described by the Heaps' law. We will see that the Heaps' law is an approximate result that can be derived from Eq. 6. Actually, when An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e061.jpg is considerably larger than 1, An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e062.jpg and An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e063.jpg; while if An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e064.jpg is considerably smaller than 1, An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e065.jpg and An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e066.jpg. This approximated result can be summarized as

equation image
(7)

which is in accordance with the previous analytical results [29], [38], [39] for An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e068.jpg and has complemented the case for An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e069.jpg.

Although Eq. 6 is different from a strict power law, numerical results indicate that the relationship between An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e070.jpg and An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e071.jpg can be well fitted by the power-law functions (the fitting is usually much better than the empirical observations about the Heaps' law, see Materials and Methods for some typical examples). In Fig. 1, we report the numerical results with fixed total number of word occurrences An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e072.jpg. When An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e073.jpg is considerably larger or smaller than 1, the numerical results agree well with the known analytical solution in Eq. 7, however, a clear deviation is observed for An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e074.jpg (see Materials and Methods about how to get the numerical results for An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e075.jpg).

Figure 1
Relationship between the Heaps' exponent An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e076.jpg and Zipf's exponent An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e077.jpg.

To validate the numerical results of Eq. 6, we propose a stochastic model. Given the total number of word occurrences An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e080.jpg, clearly, there are at most An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e081.jpg distinct words having the chance to appear. The initial occurrence number of each of these An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e082.jpg words is set as zero. At each time step, these An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e083.jpg words are sorted in descending order of their occurrence number (words with the same number of occurrences are randomly ordered), and the probability a word with rank An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e084.jpg will occur in this time step is proportional to An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e085.jpg. The whole process stops after An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e086.jpg time steps. The distribution of word occurrence always obeys the Zipf's law with a stable exponent An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e087.jpg, and the growth of An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e088.jpg approximately follows the Heaps' law with An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e089.jpg dependent on An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e090.jpg (see Figure S2 for the simulation results of the stochastic model). The simulation results about An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e091.jpg vs. An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e092.jpg of this model are also reported in Fig. 1, which agree perfectly with the numerical ones by Eq. 6. The result of the stochastic model strongly supports the validity of Eq. 6, and thus we only discuss the numerical results of Eq. 6.

In addition to An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e093.jpg, the Heaps' exponent An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e094.jpg also depends on the system size, namely the total number of word occurrences, An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e095.jpg. An example for An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e096.jpg is shown in Fig. 2, and how An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e097.jpg varies in the An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e098.jpg plane is shown in Fig. 3 (see Figure S3 for the comparison of fitting functions and four typical examples of numerical results). It is seen that the exponent An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e099.jpg increases monotonously as the increasing of An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e100.jpg. According to Eq. 6, it is obvious that in the large limit of system size, An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e101.jpg, the exponent An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e102.jpg can be determined by the asymptotic solution Eq. 7. Actually, the asymptotic solution well describes the systems with An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e103.jpg or An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e104.jpg or An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e105.jpg. However, real systems are often with An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e106.jpg around 1 and of finite sizes. As indicated by Fig. 2 and Fig. 3, the growth of An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e107.jpg versus An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e108.jpg is really slow. For example, when An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e109.jpg, for most real systems with An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e110.jpg scaling from An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e111.jpg to An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e112.jpg, the exponent An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e113.jpg is considerably smaller than the asymptotic solution An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e114.jpg. Even for very large An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e115.jpg that is probably larger than any studied real systems, like An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e116.jpg, the difference between numerical result and asymptotic solution can be observed. As we will show in the next section, this paper emphasizes the difference between empirical observations and the asymptotic solution, and the simple numerical method based on Eq. 6 provides a more accurate estimation.

Figure 2
Effect of system size on the Heaps' exponent An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e117.jpg.
Figure 3
Heaps' exponent An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e119.jpg as a function of An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e120.jpg.

Experimental Results

We analyze a number of real systems ranging from small-scale system containing only 40 distinct elements to large-scale system consisting of more than An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e121.jpg distinct elements. The results are listed in Table 1 while the detailed data description is provided in Materials and Methods. Four classes of real systems are considered, including the occurrences of words in different books and different languages (data sets Nos. 1–9), the occurrences of keywords in different journals (data sets Nos. 10–33), the confirmed cases of the novel virus influenza A (data set No. 34), and the citation record of PNAS articles (data set No. 35). Figure 4 reports the Zipf's law and Heaps' law of the four typical examples, each of which belongs to one class, respectively. Figure S4 in the Supporting Information displays the probability density function An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e122.jpg, the Zipf's plot An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e123.jpg and the Heaps' plot An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e124.jpg for all the 35 data sets with the same order as shown in Table 1.

Figure 4
Zipf's law and Heaps' law in four example systems.
Table 1
Empirical statistics and analysis results of real data sets.

To sum up, the empirical results indicate that (i) evolving systems displaying the Zipf's law also obey the Heaps' law even for small-scale systems; (ii) the asymptotic solution (Eq. 7) can well capture the relationship between the Zipf's exponent and Heaps' exponent, and the present numerical result based on Eq. 6 can provide considerably better estimations (the numerical results based on Eq. 6 outperforms Eq. 7 in 34, out of 35, tested date sets).

Discussion

Zipf's law and Heaps' law are well known in the context of complex systems. They were discovered independently and treated as two independent statistical laws for decades. Recently, the increasing evidence on the coexistence of these two laws leads to serious consideration of their relation. However, a clear picture cannot be extracted out from the literature. For example, Montemurro and Zanette [41], [42] suggested that the Zipf's law is a result from the Heaps' law while Serrano et al. [27] claimed that the Zipf's law can result in the Heaps' law. In addition, many previous analyses about their relation are based on some stochastic models, and the results are strongly dependent on the corresponding models – we are thus less confident of their applicability in explaining the coexistence of the two laws observed almost everywhere.

In this article, without the help of any specific stochastic model, we directly show that the Heaps' law can be considered as a derivative phenomenon given that the evolving system obeys the Zipf's law with a stable exponent. In contrast, the Zipf's law can not be derived from the Heaps' law without the help of a specific model or some external conditions. In a word, our analysis indicates that the Zipf's law is more fundamental than the Heaps' law in the systems where two laws coexist, which provides a new perspective on the origin of the Heaps' law. For example, the observed Heaps' law in natural language processing was attributed to the bursty nature and memory effect of human language [23][25], while Serrano, Flammini and Menczer [27] recently showed that the word occurrences in English Wikipedia also display the Heaps' law. Since the English Wikipedia is attributed by many independent editors, the memory effect is obviously not a proper interpretation. Our analysis suggests that the observed Heaps' law may be just an accompanying phenomenon of a more fundamental law – the Zipf's law. However, one can not conclude that the Heaps' law is completely dependent on the Zipf's law since there may exists some mechanisms only resulting in the Heaps' law, namely it is possible that a system displays the Heaps' law while does not obey the Zipf's law. In addition, we refine the known asymptotic solution (Eq. 7) by a more complex formula (Eq. 6), which is considerably more accurate than the asymptotic solution, as demonstrated by both the testing stochastic model and the extensive empirical analysis. In particular, our investigation about the effect of system size fills the gap in the relevant theoretical analyses.

Our analytical result (Eq. 6) indicates that the growth of vocabulary of an evolving system cannot be exactly described by the Heaps' law even though the system obeys a perfect Zipf's law with a constant exponent. In fact, not only the solution of the Heaps' exponent (Eq. 7), but also the Heaps' law itself is an asymptotic approximation obtained by considering infinite-size systems. More terribly, a Zipf's exponent larger than one does not correspond to a true distribution An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e153.jpg since An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e154.jpg will diverge as the increasing of the system size, yet a large fraction of real systems can be well characterized by the Zipf's law with An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e155.jpg (see general examples in Refs. [3], [15] and examples of degree distributions of complex networks in Refs. [46], [47]). Putting the blemish in mathematical strictness behind, the Zipf's law and Heaps' law well capture the macroscopic statistics of many complex systems, and our analysis provides a clear picture of their relation.

Note that, our analysis depends on an ideal assumption of a “perfect” power law (Zipf's law) of frequency distribution, while a real system never displays such a perfect law. Indeed, deviations from a power law have been observed, but the assumption of a perfect power-law distribution is widely used in many theoretical analyses. For example, the degree distribution in email networks [48] has a cutoff at about An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e156.jpg and the one in sexual contact networks [49] displays a drooping head, while in the analysis of epidemic dynamics, the underlying networks are usually supposed to be perfect scale-free networks [50]. Another example is the study on the effects of human dynamics on epidemic spreading [51], [52], where the interevent time distribution of human actions are supposed as a power-law distribution, ignoring the observed cutoffs and periodic oscillations [53], [54]. In a word, although the ideal assumption of a perfect power-law distribution could not fully reflect the reality, the corresponding analysis indeed contributes much to our understanding of many phenomena.

We also tested the power-law distribution with exponential cutoff, as An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e157.jpg, where An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e158.jpg is a free parameter controlling the cutoff effect. According to the stochastic model (we first generate the rank-based distribution An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e159.jpg corresponding to the probability density function An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e160.jpg, and then generate the relation An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e161.jpg versus An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e162.jpg by using the stochastic model), when the cutoff effect gets enhanced (by decreasing An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e163.jpg), the Heaps' exponent An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e164.jpg will increase (see a typical example for An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e165.jpg from Figure S5 in the Supporting Information). The simulation results suggest that the power-law part plays the dominant role, namely even under a very strong cutoff (e.g., An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e166.jpg and An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e167.jpg, with the maximal degree is about 10), the Heaps' law still holds. But if An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e168.jpg obeys an exponential form (it can even have heavier tail than the power-law distribution with strong cutoff, like An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e169.jpg), then An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e170.jpg will grow almost linearly in the early stage and soon bend, deviating from the Heaps' law. The comparison of the An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e171.jpg curves for power-law distribution with exponential cutoff and exponential distribution can be found in Figure S6 in the Supporting Information.

An interesting implication of our results lies in the accelerated growth of scale-free networks. Considering the degree of a node as its occurrence frequency and the total degree of all nodes as the text size, a growing network is analogous to a language system. Then, the scale-free nature corresponds to the Zipf's law of word frequency and the accelerated growth corresponds to the Heaps' law of the vocabulary growth. In an accelerated growing network, the total degree An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e172.jpg (proportional to the number of edges) scales in a power-law form as An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e173.jpg, where An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e174.jpg denotes the number of nodes and An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e175.jpg is the accelerating exponent. At the same time, the degree distribution usually follows a power law as An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e176.jpg where An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e177.jpg denotes the node degree. For example, the Internet at the autonomous system (AS) level displays the scale-free nature with An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e178.jpg (see Table 1 in Ref. [55]) and thus An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e179.jpg. According to a recent report [37] on empirical analysis of the Internet at the AS level, till December 2006, the total degree is An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e180.jpg. The corresponding numerical result of the Heaps' exponent is An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e181.jpg and thus the accelerating exponent can be estimated as An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e182.jpg. In contrast, the asymptotic solution Eq. 7 suggests a steady growing as An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e183.jpg. Compared with the empirical result An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e184.jpg [37], Eq. 6 (An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e185.jpg) gives better result than Eq. 7 (An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e186.jpg). Actually, the asymptotic solution indicates that all the scale-free networks with An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e187.jpg should grow in a steady (linear) manner, which is against many known empirical observations [34][37], while the refined result in this article is in accordance with them. Furthermore, our result provides some insights on the growth of complex networks, namely the accelerated growth can be expected if the network is scale-free with a stable exponent and this phenomenon is prominent when An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e188.jpg is around 2.

Materials and Methods

0.1 Relation between Zipf's Law and Power Law

Given the Zipf's law An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e189.jpg, we here prove that the probability density function An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e190.jpg obeys a power law as An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e191.jpg with An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e192.jpg. Considering the data points with ranks between An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e193.jpg and An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e194.jpg where An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e195.jpg is a very small value. Clearly, the number of data points is An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e196.jpg, which can be expressed by the probability density function as

equation image
(8)

where

equation image
(9)

Therefore, we have

equation image
(10)

namely An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e200.jpg. Analogously, the Zipf's law An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e201.jpg can be derived from the power-law probability density distribution An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e202.jpg, with An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e203.jpg.

0.2 Direct Comparison between Empirical and Analytical Results

Given the parameter An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e204.jpg, according to Eq. 6, we can numerically obtain the function An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e205.jpg. The comparison between Eq. 6 and the empirical data for words in the book “La Divina Commedia” and keywords in the PNAS articles are shown in Fig. 5. The growing tendency of distinct words can be well captured by Eq. 6. Actually, using a more accurate normalization condition An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e206.jpg, as an improved version of Eq. 4, the estimation of An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e207.jpg is determined by

equation image
(11)
Figure 5
Direct comparison between the empirical data and Eq. 6 as well as its improved version.

Given the parameter An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e210.jpg, for an arbitrary An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e211.jpg, one can estimate the corresponding An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e212.jpg according to Eq. 11 and then determine the value of An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e213.jpg by Eq. 5. The numerical results of this improved version are also presented in Fig. 5, which fits better than Eq. 6 to the empirical data. Notice that, both the two analytical results give almost the same slope in the log-log plot of An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e214.jpg function, namely the Heaps' exponents obtained by these two versions are almost the same.

0.3 Examples of Numerical Results

Mathematically speaking, as indicated by Eq. 6, An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e215.jpg does not scale in a power law with An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e216.jpg. However, the numerical results suggest that the dependence of An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e217.jpg on An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e218.jpg can be well approximated as power-law functions. As shown in Fig. 6, for a wide range of An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e219.jpg, An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e220.jpg can be well fitted by An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e221.jpg, and the value of fitting exponent An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e222.jpg depends on both An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e223.jpg and An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e224.jpg.

Figure 6
An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e225.jpg vs. An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e226.jpg according to the numerical results of Eq. 6.

0.4 The case of An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e234.jpg

The numerical solution of Eq. 6 for An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e235.jpg can be obtained by considering the limitation An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e236.jpg, where An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e237.jpg and An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e238.jpg. Accordingly, Eq. 6 can be rewritten as

equation image
(12)

When An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e240.jpg approaches to infinity, An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e241.jpg scales almost linearly with An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e242.jpg since An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e243.jpg. Actually, the solution can be expressed as An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e244.jpg where An external file that holds a picture, illustration, etc.
Object name is pone.0014139.e245.jpg is the well-known Lambert W function [56] that satisfies

equation image
(13)

For any finite system, the numerical result can be produced by Eq. 12.

0.5 Data description

The data sets analyzed in this article can be divided into four classes. According to the data sets shown in Table 1, these four classes are as follows.

(i) Occurrences of words in different books and different languages (data sets Nos. 1–9). The data set No. 1 is the English book (Moby Dick) written by Herman Melville; the data sets No. 2 (De Bello Gallico), No. 3 (Philosophiæ Naturalis Principia Mathematica) and No. 7 (Aeneis) are Latin books written by Gaius Julius Caesar, Isaac Newton and Virgil respectively; the data sets No. 4 (Don Quijote), No. 5 (La Celestina) and No. 8 (Cien aAn external file that holds a picture, illustration, etc.
Object name is pone.0014139.e247.jpgos de soledad) are Spanish novels written by Miguel de Cervantes, Fernando de Rojas and Gabriel García Márquez, respectively; the data set No. 6 (Faust) is a German opera written by Johann Wolfgang von Goethe; the data set No. 9 (La Divina Commedia di Dante) is the Italian epic poem written by Dante Alighieri. All the above data are collected by Carpena et al. [44] and available at http://bioinfo2.ugr.es/TextKeywords/index.html.

(ii) Occurrences of keywords in different journals (data sets Nos. 10–33). These 24 journals, from No. 10 to No. 33 are PNAS, Chin. Sci. Bull., J. Am. Chem. Soc., Acta Chim. Sinica, Crit. Rev. Biochem. Mol. Biol., J. Biochem., J. Nutr. Biochem., Phys. Rev. Lett., Appl. Phys. Lett., Physica A, ACM Comput. Surv., ACM Trans. Graph., Comput. Netw., ACM Trans. Comput. Syst., Econmetrica, J. Econ. Theo., SIAM Rev., SIAM J. Appl. Math., Invent. Math., Ann. Neurol., J. Evol. Biol., Theo. Popul. Biol., MIS Quart., and IEEE Trans. Automat. Contr.. These data are collected from the ISI Web of Knowledge (http://isiknowledge.com/). For every scientific journal, we consider the keywords sequence in each article according to its publishing time. Since most of the published articles do not have keywords before 1990 in ISI database, we limit our collections from 1991 to 2007 (except for ACM Comput. Surv. which is available only from 1994 to 1999).

(iii) Confirmed cases of the novel virus influenza A in 2009 (data set No. 34). The data of the cumulative number of laboratory confirmed cases of H1N1 of each country are available from the website of Epidemic and Pandemic Alert of World Health Organization (WHO) (http://www.who.int/). The analyzed data set reported influenza A starting from April 26th to May 18th, updated each one or two days. After May 18th, the distribution of confirmed cases in each country shifted from a power law to a power-law form with exponential cutoff [45].

(iv) Citation record of PNAS articles (data set No. 35). This data set consists of all the citations to PNAS articles from papers published between 1915 and 2009 according to the ISI database, ordered by time.

Supporting Information

Figure S1

Relative errors of the approximation in Eq. 5.

(0.08 MB PDF)

Figure S2

Zipf's law and Heaps' law resulted from the stochastic model.

(0.48 MB PDF)

Figure S3

Fitting Heaps' law with different system sizes.

(1.04 MB PDF)

Figure S4

Probability density functions, rank-based distributions (Zipf's plots) and Heaps' plots for all the 35 data sets shown in Table 1.

(1.29 MB PDF)

Figure S5

Effects of exponential cutoffs on the Heaps' law.

(1.68 MB PDF)

Figure S6

Comparison of the growing tendencies of $N(t)$ between the cases of power-law distribution with an exponential cutoff and the purely exponential distribution.

(0.09 MB PDF)

Footnotes

Competing Interests: The authors have declared that no competing interests exist.

Funding: The Swiss National Science Foundation (200020-121848) and the National Natural Science Foundation of China (10635040). The funders had no role in study design, data collection and analysis, decision to publish, or preparation of the manuscript.

References

1. Zipf GK. Human Behaviour and the Principle of Least Effort: An introduction to human ecology (Addison-Wesly, Cambridge) 1949.
2. Heaps HS. Information Retrieval: Computational and Theoretical Aspects (Academic Press, Orlando) 1978.
3. Clauset A, Shalizi CR, Newman MEJ. Power-law distributions in empirical data. SIAM Rev. 2009;51:661–703.
4. Axtell RL. Zipf Distribution of U.S. Firm Sizes. Science. 2001;293:1818–1820. [PubMed]
5. Drăgulescu A, Yakovenko VM. Exponential and power-law probability distributions of wealth and income in the United Kingdom and the United States. Physica A. 2001;299:213–221.
6. Redner S. How popular is your paper? An empirical study of the citation distribution. Eur Phys J B. 1998;4:131–134.
7. Furusawa C, Kaneko K. Zipf's Law in Gene Expression. Phys Rev Lett. 2003;90:088102. [PubMed]
8. Bai W-J, Zhou T, Fu Z-Q, Chen Y-H, Wu X, Wang BH. Electric power grids and blackouts in perspective of complex networks. Proc. 4th International Conference on Communications, Circuits and Systems (IEEE Press, New York) 2006.
9. Baek SK, Kiet HAT, Kim BJ. Family name distributions: Master equation approach. Phys Rev E. 2007;76:046113. [PubMed]
10. Cordoba JC. On the distribution of city sizes. J Urban Econ. 2008;63:177–197.
11. Chen Q, Wang C, Wang Y. Deformed Zipf's law in personal donation. EPL. 2009;88:38001.
12. Blasius B, Tönjes R. Zipf's Law in the Popularity Distribution of Chess Openings. Phys Rev Lett. 2009;103:218701. [PubMed]
13. Abhari A, Soraya M. Workload generation for YouTube. Multimedia Tools Appl. 2010;46:91–118.
14. Mitzenmacher M. A brief history of generative models for power law and lognormal distributions. Internet Mathematics. 2004;1:226–251.
15. Newman MEJ. Power laws, Pareto distributions and Zipf's law. Contemporary Physics. 2005;46:323–351.
16. Simon HA. On a class of skew distribution functions. Biometrika. 1955;42:425–440.
17. Barabasi A-L, Albert R. Emergence of scaling in random networks. Science. 1999;286:509–512. [PubMed]
18. Bak P. How Nature Works: The Science of Self-Organized Criticality (Copernicus, New York) 1996.
19. Kanter I, Kessler DA. Markov Processes: Linguistics and Zipf's Law. Phys Rev Lett. 1995;74:4559–4562. [PubMed]
20. Marsili M, Zhang Y-C. Interacting Individuals Leading to Zipf's Law. Phys Rev Lett. 1996;80:2741–2744.
21. Carlson JM, Doyle J. Highly optimized tolerance: A mechanism for power laws in designed systems. Phys Rev E. 1999;60:1412–1427. [PubMed]
22. Cancho RFi, Solé RV. Least effort and the origins of scaling in human language. Proc Natl Acad Sci USA. 2003;100:788–791. [PubMed]
23. Ebeling W, Pöschel T. Entropy and long range correlations in literary English. Europhys Lett. 1994;26:241–246.
24. Kleinberg J. Bursty and Hierarchical Structure in Streams. Data Min Knowl Disc. 2003;7:373–397.
25. Altmann EG, Pierrehumbert JB, Motter AE. Beyond Word Frequency: Bursts, Lulls, and Scaling in the Temporal Distributions of Words. PLoS ONE. 2009;4:e7678. [PMC free article] [PubMed]
26. Gelbukh A, Sidorov G. Zipf and Heaps Laws' Coefficients Depend on Language. Lect Notes Comput Sci. 2001;2004:332–335.
27. Serrano MÁ, Flammini A, Menczer F. Modeling Statistical Properties of Written Text. PLoS ONE. 2009;4:e5372. [PMC free article] [PubMed]
28. Cattuto C, Loreto V, Pietronero L. Semiotic dynamics and collaborative tagging, Proc Natl Acad Sci USA. 2007;104:1461–1464. [PubMed]
29. Cattuto C, Barrat A, Baldassarri A, Schehr G, Loreto V. Collective dynamics of social annotation. Proc Natl Acad Sci USA. 2009;106:10511–10515. [PubMed]
30. Zhang Z-K, Lü L, Liu J-G, Zhou T. Empirical analysis on a keyword-based semantic system. Eur Phys J B. 2008;66:557–561.
31. Lansey JC, Bukiet B. Internet Search Result Probabilities: Heaps' Law and Word Associativity. J Quant Linguistics. 2009;16:40–66.
32. Zhang H-Y. Discovering power laws in computer programs. Inf Process Manage. 2009;45:477–483.
33. Benz RW, Swamidass SJ, Baldi P. Discovery of Power-Laws in Chemical Space. J Chem Inf Model. 2008;48:1138–1151. [PubMed]
34. Dorogovtsev SN, Mendes JFF. Effect of the accelerating growth of communications networks on their structure. Phys Rev E. 2001;63:025101. [PubMed]
35. Smith DMD, Onnela J-P, Johnson NF. Accelerating networks. New J Phys. 2007;9:181.
36. Broder A, Kumar R, Moghoul F, Raghavan P, Rajagopalan S, Stata R, Tomkins A, Wiener J. Graph structure in the Web. Comput Netw. 2000;33:309–320.
37. Zhang G-Q, Zhang G-Q, Yang Q-F, Cheng S-Q, Zhou T. Evolution of the Internet and its cores. New J Phys. 2008;10:123027.
38. Baeza-Yates RA, Navarro G. Block addressing indices for approximate text retrieval. J Am Soc Inf Sci. 2000;51:69–82.
39. van Leijenhorst DC, Weide Th P van der. A formal derivation of Heaps' Law. Inf Sci. 2005;170:263–272.
40. Mandelbrot B. The pareto-levy law and the distribution of income. Int Econo Rev. 1960;1:79–106.
41. Montemurro MA, Zanette DH. New prespectives on Zipf's law in linguistics: from single texts to large corpora. Glottometrics. 2002;4:87–99.
42. Zanette DH, Montemurro MA. Dynamics of Text Generation with Realistic Zipf's Distribution. J Quant Linguistics. 2005;12:29–40.
43. Goldstein ML, Morris SA, Yen GG. Problems with fitting to the power-law distribution. Eur Phys J B. 2004;41:255–258.
44. Carpena P, Bernaola-Galván P, Hackenberg M, Coronado AV, Oliver JL. Level statistics of words: Finding keywords in literary texts and symbolic sequences. Phys Rev E. 2009;79:035102. [PubMed]
45. Han XP, Wang BH, Zhou CS, Zhou T, Zhu JF. Scaling in the Global Spreading Patterns of Pandemic Influenza A and the Role of Control: Empirical Statistics and Modeling, e-print arXiv. 2009.
46. Albert R, Barabási A-L. Statistical mechanics of complex networks. Rev Mod Phys. 2002;74:47–97.
47. Newman MEJ. The structure and function of complex networks. SIAM Rev. 2003;45:167–256.
48. Ebel H, Mielsch L-I, Bornholdt S. Scale-free topology of e-mail networks. Phys Rev E. 2002;66:035103. [PubMed]
49. Liljeros F, Edling CR, Amaral LAN, Stanley HE, Åberg Y. The web of human sexual contacts. Nature. 2001;411:907–908. [PubMed]
50. Pastor-Satorras R, Vespignani A. Epidemic Spreading in Scale-Free Networks. Phys Rev Lett. 2001;86:3200–3203. [PubMed]
51. Vázquez A, Rácz B, Lukács A, Barabási A-L. Impact of Non-Poissonian Activity Patterns on Spreading Processes. Phys Rev Lett. 2007;98:158702. [PubMed]
52. Iribarren JL, Moro E. Impact of Human Activity Patterns on the Dynamics of Information Diffusion. Phys Rev Lett. 2009;103:038702. [PubMed]
53. Zhou T, Kiet HAT, Kim BJ, Wang BH, Holme P. Role of activity in human dynamics. EPL. 2008;82:28002.
54. Radicchi F. Human activity in the web. Phys Rev E. 2009;80:026118. [PubMed]
55. Caldarelli G. Scale-Free Networks: Complex webs in nature and technology (Oxford University Press, Oxford) 2007.
56. Corless RM, Gonnet GH, Hare DEG, Jeffrey DJ, Knuth DE. On the Lambert W function. Adv Comput Math. 1996;5:329–359.

Articles from PLoS ONE are provided here courtesy of Public Library of Science