Universal and non-universal text statistics: Clustering coefficient for language identification

Abstract: Abstract In this work we analyze statistical properties of 91 relatively small texts in 7 different languages (Spanish, English, French, German, Turkish, Russian, Icelandic) as well as texts with randomly inserted spaces. Despite the size (around 11260 different words), the well known universal statistical laws -namely Zipf and Herdan-Heap’s laws- are confirmed, and are in close agreement with results obtained elsewhere. We also construct a word co-occurrence network of each text. While the degree distribution is again universal, we note that the distribution of clustering coefficients, which depend strongly on the local structure of networks, can be used to differentiate between languages, as well as to distinguish natural languages from random texts.

Statistical characterization of languages has been a field of study for decadesBIBREF0, BIBREF1, BIBREF2, BIBREF3, BIBREF4, BIBREF5. Even simple quantities, like letter frequency, can be used to decode simple substitution cryptogramsBIBREF6, BIBREF7, BIBREF8, BIBREF9, BIBREF10. However, probably the most surprising result in the field is Zipf's law, which states that if one ranks words by their frequency in a large text, the resulting rank frequency distribution is approximately a power law, for all languages BIBREF0, BIBREF11. These kind of universal results have long piqued the interest of physicists and mathematicians, as well as linguistsBIBREF12, BIBREF13, BIBREF14. Indeed, a large amount of effort has been devoted to try to understand the origin of Zipf's law, in some cases arguing that it arises from the fact that texts carry information BIBREF15, all the way to arguing that it is the result of mere chance BIBREF16, BIBREF17. Another interesting characterization of texts is the Heaps-Herdan law, which describes how the vocabulary -that is, the set of different words- grows with the size of a text, the number of which, empirically, has been found to grow as a power of the text size BIBREF18, BIBREF19. It is worth noting that it has been argued that this law is a consequence Zipf's law. BIBREF20, BIBREF21
A different tool used to characterize texts is the adjacency (or co-ocurrence) network BIBREF22, BIBREF23, BIBREF24, BIBREF25. The nodes in this network represent the words in the text, and a link is placed between nodes if the corresponding words are adjacent in the text. These links can be directed -according to the order in which the words appear-, or undirected. In this work we study properties of the adjacency network of various texts in several languages, using undirected links. The advantage of representing the text as a network is that we can describe properties of the text using the tools of network theory BIBREF26. The simplest characterization of a network is its degree distribution, that is, the fraction of nodes with a given number of links, and we will see that this distribution is also a universal power law for all languages. As we argue ahead, this may follow from the fact that Zipf's law is satisfied.
Another interesting use for text statistics is to distinguish texts and languages. In particular, as occurs with letter frequencies, other more subtle statistics may be used to distinguish different languages, and beyond that, provide a metric to group languages into different families BIBREF27, BIBREF28, BIBREF29. In this paper we use the clustering coefficient BIBREF26 to show that even though the degree distribution of the adjacency matrices is common to all languages, the statistics of their clustering coefficients, while approximately similar for various texts in each language, appears to be different from one language to another.
We use different texts (see Appendix (SECREF8)) instead of a large single corpus for each language because clustering coefficients typically decrease as a function of the size of the networkBIBREF30. Actually, we must compare the statistics of the clustering coefficient in texts with adjacency networks of comparable sizes. In the following section we present the rank vs frequency distribution for these texts. We also measure how the vocabulary increases with text size, as well as the respective degree distributions of the networks corresponding to every text, and compare them with a null "random" hypothesis. This null hypothesis consists of a set of texts constructed as follows: we select a text and remove all the spaces between words, then we reintroduce the spaces at random with the restriction that there cannot be a space next to another. We identify as words all strings of letters between consecutive spaces (the restriction avoids the possibility of having empty words). The reason we build the null hypothesis this way instead of the usual independent random letters with random spaces most commonly used BIBREF17, BIBREF31, is that consecutive letters are not independent: they are correlated to ensure word pronunciability, as well as due to spelling rules. Our method for constructing these random texts conserves most of the correlations between consecutive letters in a given language.
Next, we calculate the distribution of the clustering coefficients of the nodes of the adjacency network for each text. These distribution functions are more or less similar for all the texts of the same language, provided the networks are of the same size. However, it is apparent that the distributions are different between different languages. We also compare the clustering coefficient distributions with those of the null hypothesis. The data show that the strongest differences between languages occur for the fractions of nodes with clustering coefficients 0 and 1. We build a scatter plot for these fractions for all the texts in each language. Though there is overlap between some languages, other languages are clearly differentiated in the plot. We fit correlated bivariate gaussian distributions to the data of each language, which allows us to estimate a likelihood that a text is in a given language.
We analyzed 91 texts written in 7 languages: Spanish, English, German, French, Turkish, Russian and Icelandic. We also considered as null texts, 12 realizations of a randomized version the Portrait of Dorian Gray book, twice for each language analyzed here (except Icelandic). As mentioned above, the process for randomizing the text is as follows: first we remove the spaces in the original text. Then, we take the first letter, and with a probability of $1/2$ we add the next letter in the sequence, or the next letter in the sequence and a space. We advance to the last symbol added, and repeat the process until we reach the end of the text. This way we destroy the grammar of the original language, keeping the letter frequencies as well as most of the correlations between consecutive letters. The set of documents we used in this work are shown in Appendix SECREF8.
All texts were intervened to remove punctuation marks, numbers, parenthesis and other uncommon symbols, and all the letters were turned into lower case, so a word appearing with different case letters would not be counted as two different words. Also, we do not transliterate the texts, instead, we use the original symbols of the texts (Cyrillic alphabet for Russian texts or the special characters in Icelandic) using the UTF-8 encoding.
Also, since clustering coefficients depend non trivially on the size of the networks, we cut the texts so they all have essentially the same vocabulary size ($\simeq 11260$).
In table TABREF1 we summarize for each language, the averages of the length, vocabulary size, maximum frequency and number of hapax legomena (i.e. words that appear only once in a document or corpus) of the texts studied here. It is important to note that for different languages, very different text lengths are required to achieve the same vocabulary size. We also note that in all cases, hapax legomena represent approximately half of the vocabulary in each text.
In figure (FIGREF2) we show Zipf plots for some of the texts, including the random texts constructed as described previously. It is clear that all the texts reproduce convincingly Zipf's law: $f(n)\sim 1/n^\alpha $ where $n=1,2,...N_{tot}$ is the word rank, $N_{tot}$ is the size of the vocabulary and $f(n)$ is its frequency. This is in contrast to previous work in which it is argued that there are differences between the Zipf plots of texts and random sequencesBIBREF32, this might be due to the fact that our random text construction preserves correlations between letters, whereas the letters in BIBREF32 were placed independently. Our findings are summarized in Appendix (SECREF7).
Figure (FIGREF2) is the typical rank vs frequency plot for a randomly chosen text in each language. From the figure, we see that $\alpha \simeq 1$, obtained by least squares fits to the plot, describes very well all the texts. Therefore, given that $n/N_{tot}$ is the fraction of words with frequencies greater or equal to $f(n)$, then
where $p(f) \simeq 1/f^{\alpha _z}$ is the frequency distribution of the vocabulary. Now, if $f(n)\sim 1/n^\alpha $, then $p(f)\sim 1/f^{1+1/\alpha }$, i.e. $\alpha _z=1+1/\alpha $. Substituting $\alpha =1$, we have $\alpha _Z = 2$, which is in close agreement with what we observe. See figure (FIGREF5) and the tables in Appendix (SECREF7)
Figure (FIGREF6) shows the size of the vocabulary $V(L)$, as a function of the length $L$ of the text considered. Once again, all the texts, including the random texts, follow the Heaps-Herdan law $V(L)\sim L^{\beta }$ reasonably well. Again, the parameters describing the various texts are given in Appendix(SECREF7)
Continuing with the universal laws describing texts, in figure (FIGREF7) we show an example of the degree distribution for the adjacency network of the texts studied in this work. It is clear that except for the low odd degrees ($k=1,3,5,7$, see inset in fig.(FIGREF7)), the distribution is well described by a power law. The parameters corresponding to the texts are given in Appendix(SECREF7). As mentioned previously, this asymptotic behavior is a consequence of Zipf's law. If we assume that each time a word appears, the input degree $k_{in}$ (alternatively, the output degree $k_{out}$) of the corresponding node increases approximately by one, then the input degree could be expected to grow proportional to the frequency of each word. Further, in general we can expect that the total degree of a node to be $k\approx k_{in}+k_{out}\approx 2k_{in}$ (clearly this is not always true: for example, a word can appear twice, being preceded both times by the same word and followed by different words each time, leading to a degree $k=3$). Then, up to multiplicative factors, we can apply the same argument as in Equation DISPLAY_FORM4 for $\mathrm {p}(k)$, the degree distribution of the network, instead of $p(f)$ From this equation it again follows that if $f(n)\sim 1/n^\alpha $, then $\mathrm {p}(k)\sim 1/k^{1+1/\alpha }$, which is again in close agreement with what we observe.
Thus far, our results confirm that the all our texts exhibit the expected universal statistics observed in natural languages. Actually, it could be argued that these laws may be "too universal", not being able to clearly distinguish texts written in real languages from our random texts. Further, all these laws appear to be consequence of Zipf's law, and this law reflects only the frequency of words, not their order. Thus, all three laws would still hold if the words of the texts were randomly shuffled. Clearly, shuffling the words destroys whatever relations may exist between successive words in a text, depending on the language in which it was written. This relation between successive words is what conveys meaning to a text. Thus, we expect that the clustering coefficient BIBREF26 of the adjacency network of each text,(constructed using words as nodes and linking those that are adjacent in the text), which depends strongly on the local structure, will distinguish between random texts and real texts, and even between texts in different languages.
The clustering coefficient $C_i(k_i)$ of node $i$ with degree $k_i$ is defined as the ratio of the number of links between node $i$'s neighbors over the total number of links that would be possible for this node $k_i(k_i-1)/2$. Thus, clearly, $0\le C_i(k_i)\le 1$. Hapax legomena, for example, mostly correspond to nodes with degree $k=2$, thus their clustering coefficient can only take the values 0 and 1 (degree $k=1$ is possible if the hapax appears followed and preceded by the same word, but these are rare occurrences). In general terms, the actual values of the clustering coefficients vary as a function of the size of the network BIBREF30, thus, in order to compare the clustering coefficients of networks corresponding to different texts, we have trimmed our texts so they all have approximately the same vocabulary size ($\simeq 11260$). In figure (FIGREF8) we show an example of the clustering coefficient as a function of $k$. There are many values $C(k)$ for each $k$ corresponding to the diverse nodes with the same degree. The red points in the graph denote the average clustering coefficient for each $k$, and the solid black line is the log-binning of this average.
In order to quantify differences between languages, for each text we define the quantity $\nu (C)$ as
In figure (FIGREF10) we show $\nu (C)$ vs $C$ for Don Quixote in six different languages. From the graph it is clear that $\nu (0)$ and $\nu (1)$ show the largest degree of variation between the various languages, thus, we propose to focus on these two numbers to characterize the various languages.
In figure (FIGREF11) we show a scatter plot of $\nu (1)$ vs $\nu (0)$ for the texts in every language presented here. Using maximum likelihood estimators, we fit correlated bi-variate Gaussian distributions to the scatter plots of each language, the contour plots of which are also shown in the graph. First and most importantly, we can see in the figure that there is a clear distinction between languages and random texts. Also, we can see that languages tend to cluster in a way that is consistent with the known relationships among the languages. For example, in the figure we note that the contours corresponding to French and Spanish show a strong overlap, which might have been expected as they are closely related languages BIBREF35. On the other hand, Russian is far from French and Spanish. This suggest that these curves may be used as a quantitative aid for the classification of languages into families. For example, French and Spanish which are both Romance languages, appear closer to each other than to Russian and Turkish, which have different origins.
In order to test the validity our results, we calculate $\nu (0)$ and $\nu (1)$ for another set of books, (see tables in the appendix (SECREF8)) and using the fitted Gaussian distributions for each language, we calculated the probability that a text in each language would have those values, which allows us to assign a likelihood that a text is written in one or another language.
In table TABREF12 we can see, for example, that it is most likely that Smásögur I (Short stories in Icelandic) are written in Icelandic than in any of the languages analyzed, or that they are a random text.
Not surprisingly, it is not so easy to tell if Voltaire in French, is really written in French or in Spanish, likewise, it is not easy to tell if Moby Dick in Spanish is written in Spanish or French, and in both cases the maximum likelihood prediction fails. Nevertheless, it is clear that these books are not written in any of the other languages presented here, nor do they correspond to a random text. On the other hand, Twenty thousand leagues under the sea in Spanish and Les Miserables in French, are correctly identified, as well as all the other texts analyzed, including the random texts.
To try to pinpoint the origin of the differentiation between different languages, we note that an inspection of the nodes with $C=0$ and 1 reveals that they mainly consist of hapax legomena (as noted before, hapax legomena only have $C$ values of 0 and 1). To measure the relative importance of these words, we calculate the ratio of hapax legomena to the total number of words with $C=0$ and 1, we call this number $\nu ^{\prime }_{H}(C)$.
In Table TABREF13, we show the fraction of hapax legomena of the words with $C=0,1$ for several texts in English. A value close to 1 indicates that most of the nodes that contribute to $\nu ^{\prime }_H(C)$ are words that appear only once in the document. This indicates that the local structure around those words, i.e, the way that they relate in the adjacency network, is particular to each language, and seems to be a key for language differentiation.
In the Table TABREF14 we see the average of $\nu ^{\prime }_H(C)$ for each of the languages studied here. Note that for example the values are clearly different for Spanish and Turkish, similar for Spanish and French, and very different for all languages and random.
Zipf's law is one of the most universal statistics of natural languages. However, it may be too universal. While it may not strictly apply to sequences of independent random symbols with random spacings BIBREF32, it appears to describe random texts that conserve most of the correlations between successive symbols, as accurately as it describes texts written in real languages. Further, Heaps-Herdan law and the degree distribution of the adjacency network, appear to be consequences of Zipf's law, and are, thus, as universal.
In this work we studied 91 texts in seven different languages, as well as random texts constructed by randomizing the spacings between words without altering the order of the letters in the text. We find that they are all well described by the universal laws. However, we also found that the distribution of clustering coefficients of the networks of each text appears to vary from one language to another, and to distinguish random texts from real languages. The nodes that vary the most among the distributions of $C(k)$ are those for which $C(k)$ is equal to 0 or 1. We fit the scatter plot of these nodes to bivariate Gaussian distributions, which allows us to define the likelihood that a text is written in each given language. This method was very successful identifying the languages in which test were written, only failing to distinguish a couple of texts, confusing texts french and spanish, which have a strong overlap. In Table (TABREF12) we present the evidence that we can use the statistics of clustering coefficient to measure a sort of distance between languages.
Though hapax legomena account for most of the value $\nu (C)$ for $C=0$ and 1, we found that the fraction $\nu ^{\prime }_H(C)$ of hapax to other words is similar for French and Spanish, and different for Spanish and, say, Turkish. Further, $\nu ^{\prime }_H(C)$ is different between random texts and the languages we study. These observations might give some clue to the mechanism by which the clustering coefficient, and in particular the local structure around hapax legomena, helps to differentiate languages.
Unlike the work presented by Gamallo et. al BIBREF27, which is Corpus-based, our work uses a relatively small amount of texts. Also as we can see in tables presented in Appendix (SECREF7), the length of the texts we use is not necessarily the length of the complete work. Texts were cut at the appropriate length for all of them to have approximately the same vocabulary ($\simeq 11260$). Thus, actual lengths ranged from 368076 words for the Jane Austen books in English, to 26347 words for the text we called Turkish I. This is important not only for computational reasons, it may also be important for studies of the relation between languages for which large corpora do not exist, something very common in the linguistic studies of the indigenous languages. The method proposed in this work can be useful in such cases, as small texts trimmed to fill some appropriate vocabulary size is the only necessary ingredient.
Diego Espitia acknowledges financial support through a doctoral scholarship from Consejo Nacional de Ciencia y Tecnología (CONACyT).
In this appendix we present tables of results for the data analyzed in this work. Here $\alpha _k$ and $\sigma _k$ represent the exponent and standard error of the power law for the degree distribution of the co-occurrence networks $p(k) \propto 1/k^{\alpha _k} $, for $k> k_{min}$, where $k_{min}$ is the smallest degree for which the power law holds. Similarly, $\alpha _Z$ and $\sigma _z$ represents the exponent and standard error of the distribution of frequencies $p(f)\propto 1/f^{\alpha _z}$; for $f > f_{min}$ where now $f_{min}$ is the smallest frequency for which the power law is satisfied. The values of the Heap's law $\beta $ and $\sigma _h$ were obtained via least square fitting.
For the estimation of the parameters we use the Maximum Likelihood Estimation (MLE) method for discerning and quantifying power-law behavior in empirical data BIBREF36. The MLE works as follows: assuming that the data fits a power law, we estimate $\alpha $ via
where $x_i > x_{min}^*$ for $i=1,...N$ and using as $x^*_{min}$ each element of the data set $\lbrace x\rbrace $. Then, using the Kolmogorov–Smirnov test we find the distance $D$ between the cumulative distribution of the data set and the cumulative distribution $P_{(x^*_{min},\alpha ^*)}(x)$. From these set of distances, we find the value which minimizes $D$, this $x_{min}$, is the smallest data for which the power law holds, and can be used to determine the parameter of the power law $\hat{\alpha }$. In order to perform a goodness of the fit test, we construct 1000 synthetic data, using the previous $\hat{\alpha }$ and $x_{min}$. Now we can count the fraction of the synthetic distances that are larger than the distance obtained from the data. This fraction is known as p-value If this p-value$>0.1$, then the difference between the data set and the model can be attributed to statistical fluctuations alone; if it is small, the model is not a plausible fit to the data.BIBREF36
Spanish
English
French
German
Turkish
Russian
Icelandic
Random
Here we present the text used in this work. The vast majority of the texts were obtained from the Gutemberg project, except for the texts in Russian, Turkish and Icelandic, which were obtained from other sources.
@ll@ 2cIcelandic
Torfhildi Hólm Brynjólfur Biskup Sveinsson
Sagas I
Sagas II
Sagas III
Sagas IV
Sagas V
Sagas VI
Sagas VII
Jón Trausti
Jón Thoroddsen Maður Og Kona
Þorgils Gjallanda
Smásögur I
Smásögur II
Source: All sagas were obtained from https://sagadb.org/. The other texts were obtained from https://www.snerpa.is/net/index.html

Figure and table captions:
Table 1: Averages for each language of the length, vocabulary size, maximum word frequency and number of hapax legomena of the texts studied in this work. Notice the large variations in text length required to achieve the same vocabulary size Ntot from one language to another.
Figure 1: Word frequency f(n) versus rank n illustrating Zipf’s Law f(n) ∼ 1/nα for single randomly chosen texts in each language: English, Russian, Turkish, French, German, Spanish and Icelandic, using Log-binned data (colored symbols). Black dots represent the random texts constructed as described in the text. The dashed line corresponds to α = 1. In the inset we show an example of rank vs frequency plot without log-binning. Note that words with f = 1 (hapax legomena) represent a large fraction of the vocabulary of the text
Figure 2: Cumulative of the frequency distribution P (f) ≡ ∫ ∞ f
Figure 3: The Herdan-Heap’s Law V (L) ∼ Lβ for single randomly chosen texts in each language: English, Russian, French, German, Spanish, Icelandic and Turkish. Black dots represent random texts. The dashed line corresponds to a power law with exponent β = 0.8, which is the average over all the texts we studied.
Figure 4: Cumulative of the degree distribution P(f) ≡ ∫ ∞ f p(ζ)dζ for single randomly chosen texts in each language: Spanish, English, French, German, Turkish, Russian, and Icelandic (colored symbols). As in figure 2, black dots represent a random text, and the dashed line corresponds to the behavior when the exponent in Zipf’s law is α = 1. Inset: Degree distribution of the Don Quixote in French, note that the first few odd degrees k = 1, 3, 5, 7 deviate from the power law behavior.
Figure 5: Clustering coefficient as function of the degree for Don Quixote (Spanish). The gray dots represents the C(k) for each node. Red circles are the average of C(k). The black line is the logarithmic binning of the average.
Figure 6: Fraction of nodes with same Clustering Coefficient for Don Quixote in English, Spanish, Turkish, Russian, French and German. Note that nodes with C = 0 and 1 present the largest variability between different languages
Figure 7: Bi-variate normal distribution for ν(0) and ν(1) for the different texts and random sequences. Note that differences in the distributions are clear for languages that are known to be part of different linguistic families, for example Turkish and English. Languages that belongs to the same family (Spanish and French) are essentially indistinguishable.
Table 2: Probability density function for different texts written in several languages, and random texts. Values less than 1× 10−8 are neglected.
Table 3: Fraction of hapax legomena with clustering coefficient equal to 0 or 1 for English texts
Table 4: Average values of ν′H(C) for Spanish, English, French, German, Turkish, Icelandic and Random texts.
Table 5: Source: Gutemberg Project
Table 8: Source: https://www.e-reading.club
Table 6: Source: Gutemberg Project
Table 10: Source: Gutemberg Project
Table 11: Source: All sagas were obtained from https://sagadb.org/. The other texts were obtained from https://www.snerpa.is/net/index.html

Questions about this paper:
How do Zipf and Herdan-Heap's laws differ?

Answers:
Zipf's law describes change of word frequency rate, while Heaps-Herdan describes different word number in large texts (assumed that Hepas-Herdan is consequence of Zipf's)