Modeling the average shortest-path length in growth of word-adjacency networks

We investigate properties of evolving linguistic networks defined by the word-adjacency relation. Such networks belong to the category of networks with accelerated growth but their shortest-path length appears to reveal the network size dependence of different functional form than the ones known so far. We thus compare the networks created from literary texts with their artificial substitutes based on different variants of the Dorogovtsev-Mendes model and observe that none of them is able to properly simulate the novel asymptotics of the shortest-path length. Then, we identify the local chainlike linear growth induced by grammar and style as a missing element in this model and extend it by incorporating such effects. It is in this way that a satisfactory agreement with the empirical result is obtained.

Figure 1

Growing word-adjacency networks for sample literary texts: Ulysses by J. Joyce (English, left) and Lalka by B. Prus (Polish, right). Each picture represents a different stage of the network's development. (a) and (d) An initial phase with few or even no repeated words $\left(N=40\right)$; (b) and (e) a phase in which hubs start to be distinguishable $\left(N=100\right)$; (c) and (f) a phase in which old words are used more often than new ones $\left(N=1000\right)$. The words that play a role of network hubs in (b) and (e) are distinguished in all panels by larger size and different color [green (light gray)].

Figure 2

Evolution of the average shortest-path length $L\left(N\right)$ for growing word-adjacency networks created from sample literary texts: (a) Ulysses by J. Joyce (written in English), (b) La Comédie humaine by H. de Balzac (French), (c) Der Zauberberg by T. Mann (German), (d) Trylogia by H. Sienkiewicz (Polish), (e) Anna Karenina by L. Tolstoy (Russian), and (f) Don Quijote by M. de Cervantes (Spanish). Each text was divided into a number of pieces in order to obtain an ensemble of samples. Results for these pieces are shown denoted by different lines in each panel, as well as their average behavior (thick line).

Figure 3

Evolution of the average shortest-path length $L\left(N\right)$ for growing word-adjacency networks created from opening pieces of sample literary texts representing different European languages: (a) English (23 texts), (b) French (14 texts), (c) Polish (17 texts), and (d) Russian (12 texts). Thin lines correspond to individual texts, while thick lines denote the average over the texts written in the same language. The texts with peculiar behavior of $L\left(N\right)$ are denoted by acronyms: VoB, The Voyage of the Beagle by C. Darwin; FW, Finnegans Wake by J. Joyce; MH, Mémoires d'Hadrien by M. Yourcenar; PT, Pan Tadeusz by A. Mickiewicz; TD, Tikhiy Don by M. Sholokhov; and $P$, Peterburg by A. Bely.

Figure 4

Evolution of the average shortest-path length $L\left(N\right)$ for growing word-adjacency networks created from the original (black) and randomly reshuffled (red) literary texts (the same ones as in Fig. 2). The curves representing $L\left(N\right)$ for the original texts were averaged over 22–30 different pieces of each text (depending on a text's length), while for the surrogate texts they were averaged over 20 independent realizations of text reshuffling. Error bars denote standard error of the mean. Note that the qualitatively similar shape of the curves for both kinds of data is by no means surprising: The word-frequency statistics is one of the key factors that exert influence on topology of the word-adjacency networks and this statistics is invariant under text randomization.

Figure 5

Evolution of the average shortest-path length $L\left(N\right)$ for networks with accelerated growth simulated according to the Dorogovtsev-Mendes model. The networks are characterized by three parameters: $m,\alpha ,c_0$ [see Eq. (5)], one of which is varied $[\alpha$ in (a) and $c_0$ in (b)], while the other two are fixed. In both panels vertical axes have the same range as in Figs. 2 and 3 in order to facilitate comparison. Only the results for $N>15$ are shown, because for smaller $N$ the particular choice of the initial condition as a chain of $n_0=7$ nodes distorts the behavior of ASPL. The legends describe the lines as they appear from top $(\alpha =0.5$ or $c_0=0.0005)$ to bottom $(\alpha =1.0$ or $c_0=0.1)$.

Figure 6

Visualization of a typical network constructed according to the DM model $(c_0=0.01,\alpha =0.8,m=2$, with a network seed being a chain of $n_0=7$ nodes). Three snapshots of the network development are shown with the same values of $N$ as in Fig. 1: $N=40$ (a), 100 (b), and 1000 (c).

Figure 7

Visualization of a network constructed according to the Simon-Heaps model with $p_0=1.0$ and $\mu =0.075$. Three snapshots of the network development are shown: $N=40$ (a), 100 (b), and 1000 (c). The earliest developed hubs are distinguished by larger symbols [green (light gray)].

Figure 8

Different realizations of the average shortest-path length $L\left(N\right)$ for sample networks constructed according to the Simon-Heaps algorithm with $p_0=1.0$ and $\mu =0.075$ (thin lines) together with the respective average of all the individual realizations (thick line).

Figure 9

Average shortest-path length $L\left(N\right)$ for sample networks constructed according to the Simon-Heaps model with the parameters $p_0=1.0$ and $\mu =0.05$ and with nonlinear preference expressed by the parameters $c_1=12.0$ and $\eta =0.25$. Different realizations of the model are denoted by thin lines, while the average is denoted by the thick line.

Figure 10

Visualization of a network constructed according to the nonlinear Simon-Heaps model with the same parameter values as in Fig. 9. Three snapshots of the network development are shown: $N=40$ (a), 100 (b), and 1000 (c). The earliest developed hubs are distinguished by larger symbols [green (light gray)].

Figure 11

Average shortest-path length $L\left(N\right)$ for networks constructed according to the hybrid model with $m=2,c_0=0.05,\alpha =1.0,p_0=1.0$, and $\mu =0.075$. Different realizations are represented by thin lines, while the average is denoted by the thick line.

Figure 12

Visualization of a network constructed according to the hybrid model $\left(c_0=0.01,\alpha =1.0,m=2,\mu =0.075\right)$. Three snapshots of the network development are shown with the same values of $N$ as in Fig. 1: $N=40$ (a), 100 (b), and 1000 (c). The earliest developed hubs are distinguished by larger symbols [green (light gray)].