# Graph theory and corpus linguistics

This short post is the first of a series on network graphs for corpus linguistics. Because of the COVID19 pandemic, such graphs have been in the spotlight in the last few months for their ability to illustrate and explain how and how fast an infection spreads across a population. Because I am not an epidemiologist, I will merely show to what extent network graphs can prove useful to corpus linguists, starting with collocation networks.

I became interested in networks after I read Albert-László Barabási’s popular science book *Linked: The New Science of Networks* (2002). Because corpus linguistics is arguably the study of the distribution of words, and because I had read about the networks of words and constructions ‘in the mind’ before, I found that network graphs had a major role to play in my field.

## Graph theory: where it all started

The origin of network science is graph theory, whose origin dates back to 1736, when mathematician Leonhard Euler solved a famous problem: the Seven Bridges of Königsberg. Fig. 1 is a map of Königsberg in 1736.

The Pregel River partitions the city into four parts:

- Kneiphof Island (B)
- 3 districts (A, C, and D).

These parts are connected by 7 bridges (numbered from 1 to 7).

The problem is to devise a route around the city that would cross each of those bridges once and only once. Euler diagrammed the city in such a way that each of the four districts was a node and each bridge an edge (Fig. 2).

Thanks to this graph, Euler showed that such a route does not exist. The nodes which are connected to an odd number of edges can only be starting points or end points. An uninterrupted walk from start to finish crossing all bridges can only have one starting point and one finish point. For that reason, this walk cannot be plotted on a graph with more than two nodes that are connected to an odd number of edges. Because the graph in Fig. 2 has four nodes connected to an odd number of edges (7), the route does not exist.

In 1875, a new bridge was built between A and C. This reduced the number of nodes linked to an uneven number of edges to two. It became possible to solve the problem of the Seven Bridges of Königsbergand. What we still ignore to this day is whether the bridge was built to allow for the problem’s resolution.

## The small world of language phenomena

Arguably, the most influent offshoot of Graph Theory is the Erdős–Rényi random-graph model (Erdős & Rényi, 1959). In a random graph, all the nodes are equally likely to be connected by edges. Their distribution is random (Fig. 3) and likely to follow a bell-curve (Fig. 4).

If you are familiar with language-related phenomena, you already know that such a random distribution is unlikely to happen because « language is never, ever, ever, random » (Kilgarriff 2005).^{1} Indeed, words do not occur in a sentence or a text in a random fashion.

The distribution of words in natural languages is characterized by Zipf’s law (Zipf, 1949). It holds that in a corpus of naturally-occurring utterances, the frequency of any word is inversely proportional to its rank in the frequency table, according to the power law, which it derives from. A Zipfian distribution is characterized by a large number of rare units.

By way of illustration of Zipf’s law, Fig. 5 displays the distribution of words for each of the eight text types found in the British National Corpus. The shape of each curve is Zipfian.

Words have been found to co-occur along the lines laid out by ‘small world’ networks (Cancho & Solé 2001). As observed by biologists, physicists, and social-network experts, and summarized by Watts & Strogatz (1998), ‘small-world’ networks have two distinctive features :

- they are very dense;
- the average distance between two nodes is short.

Fig. 6. shows what a typical ‘small-world’ network looks like.

The above has been verified with lexical behavior (Drieger, 2013). To put it simply, words interact in a dense fashion with their (close) environment.

In a future post, I will show how graph theory can be used to provide a graph-based representation of collocation networks. In more concrete terms, I will show how to plot network graphs in R using the `igraph`

and `ggplot2`

packages.

### Words and infections (short addendum)

In *Linked*, Barabasi explains how a disease (just like fads) spreads in a network in a small-world. How fast an infection spreads depends on the presence of ‘hubs’, i.e. members of a network that have a number of connections to other nodes that is highly above average. In epidemiology, these are known as ‘super spreaders’ (e.g. Gaëtan Dugas in the case of AIDS in the early 1980s).

### References

Cancho, Ramon Ferrer i & Ricard V. Solé (2001). « The Small World of Human Language ». In: *Proceedings of The Royal Society of London*. Series B, Biological Sciences 268, p. 2261–2265.

Desagulier, G. (2017). *Corpus Linguistics and Statistics with R*. New York: Springer.

Erdős, P & Rényi, A. (1959). « On Random Graphs. I« . *Publicationes Mathematicae 6*: 290–297.

Kilgarriff, Adam (2005). « Language is never, ever, ever, random ». *Corpus Linguistics and Linguistic Theory 1*.2, p. 263–276.

Watts, Duncan J. et Steven H. Strogatz (1998). « Collective dynamics of ’small-world’ networks ». In : Nature 393, p. 440–442 (cf. p. 100).

Zipf, George K. (1949). *Human Behavior and the Principle of Least Effort*. Cambridge : Addison-Wesley

*Around the word*, 13/05/2020, https://corpling.hypotheses.org/3265.

- Recent distribution semantic models such as
`word2vec`

rely on a bag-of-word approach. Although NLP engineers are ok with this, linguists find it questionable. [↩]