Graph-theoretic Properties of the Class of Phonological Neighbourhood Networks (2021)

Abstract: This paper concerns the structure of phonological neighbourhood networks, which are a graph-theoretic representation of the phonological lexicon. These networks represent each word as a node and links are placed between words which are phonological neighbours, usually defined as a string edit distance of one. Phonological neighbourhood networks have been used to study many aspects of the mental lexicon and psycholinguistic theories of speech production and perception. This paper offers preliminary graph-theoretic observations about phonological neighbourhood networks considered as a class. To aid this exploration, this paper introduces the concept of the hyperlexicon, the network consisting of all possible words for a given symbol set and their neighbourhood relations. The construction of the hyperlexicon is discussed, and basic properties are derived. This work is among the first to directly address the nature of phonological neighbourhood networks from an analytic perspective.

## motivation recent work in phonological psycholinguistics has investigated the structure of the lexicon through the use of phonological neighbourhood networks @xcite @xcite @xcite . a phonological neighbourhood network is a representation of the lexicon where each word is treated as a node and a link is placed between nodes if and only if those two nodes are phonological neighbours. two words are neighbours if their string edit distance, in terms of phonological representation, is one. in other words, the neighbours of a word w are all the words that can be formed by the addition, deletion, or substitution of a single phoneme from w. the neighbourhood relation is symmetric (if w is a neighbour of w , then w is necessarily a neighbour of w), intransitive (if w is a neighbour of w , and w is a neighbour of w , it is not necessarily the case that w is a neighbour of w ), and anti-reflexive (w cannot be a neighbour of itself). figure 1 shows an abbreviated phonological neighbourhood network for some words of english. one advantage of this representation is that it permits analysis with the methods of network science and graph theory, and work so far has shown a good deal of promise in modeling psycholinguistic properties of the lexicon with these methods @xcite . a common analysis technique within network science is to compare a given network with a randomly generated one that has the same number of nodes and links. notable features of the target network relative to the random network are likely due to intrinsic properties of the target network, rather than chance. from this structure one can then infer details about the organising principles that generated the network originally. for phonological neighbourhood networks, however, this method is often inappropriate, as many logically possible network structures are not possible phonological neighbourhood networks. this fact is because the links between nodes-the neighbourhood relations-are intrinsic to the definitions of the nodes themselves. changing a link between nodes necessarily means changing the content of a node, which then could entail other changes to other links. this problem was highlighted by turnbull and peperkamp (2017), foot_0 who instead chose to randomly generate lexicons and derive networks from those lexicons. however, randomly generated lexicons do not guarantee the same number of links will be present in the resulting network, making it difficult to compare like with like. for this reason, studying phonological neighbourhood networks as a class, and discovering their defining characteristics, is an important methodological goal for psycholinguists. this research therefore seeks to answer the following broad questions: what are the distinctive characteristics of phonological neighbourhood networks, including their definitions in terms of edge sets and vertex sets, their extremal properties, and characterization of forbidden subgraphs? is there an effective and efficient method by which phonological neighbourhood graphs can be distinguished from other graphs? the present paper lays the mathematical foundations for future investigations of both of these questions. ## preliminaries this section briefly defines the basic mathematical definitions and operations used in the remainder of the paper. the reader is referred to standard textbooks in graph theory, such as @xcite or @xcite , for more details. as mathematical terminology and notation can vary between subfields, alternative names and characterizations of some objects are mentioned in the ensuing sections, but they are not strictly necessary to understand the arguments of this paper. networks can be modeled as mathematical objects known as graphs, which consist of vertices (nodes) and edges (links). let g be an undirected graph with no self-loops with vertex set v (g) and edge set e(g). let k n denote the complete graph with n vertices and all possible edges. in other words, an induced subgraph can be obtained by the process of removing vertices (and any incident edges) from a graph, but not removing edges on their own. figure 2 provides illustrative examples. the diamond is k 4 with one edge removed. a circle c k has the set of nodes {1, 2, ..., k} and edge set {{1, 2}, {2, 3}, ..., {(k -1), k}, {k, 1}}. (circle graphs that are induced subgraphs of a larger graph are also known as k-holes.) figure 3 depicts the diamond and c 5 . a star s k is a graph with one central vertex which is connected to k other unique vertices. no other vertices or edges exist. figure 4 depicts the stars s 3 (also known as a claw), s 4 , and s 6 . the cartesian product a × b of two sets a and b is defined as the cartesian product g h of two graphs g and h has the vertex set a given vertex (a, x) is linked with another vertex (b, y) if @xmath0, y} ∈ e(h) (the second elements are linked in h), or if @xmath1, b} ∈ e(g) (the first elements are linked in g). to aid understanding, figure 5 depicts an example of the cartesian product of two graphs, g and and h can be seen in g h as two orthogonal dimensions. note also that the total number of vertices in g h is equal to the product of the number of vertices in g and h. we further denote the cartesian exponent of a graph g as s 3 s 4 s 6 figure 4: star graphs s 3 , s 4 , and s 6 . a b c x y (a, x) (b, x) (c, x) (c, y) (b, y) (a, y) g h g h that is, the cartesian product of g with itself n -1 times. figure 6 depicts the graphs k 2 and k foot_1 2 . it can be seen that k 2 2 is a square, k 3 2 is a cube, and k n 2 is an n-dimensional hypercube. 2 likewise, the vertex labels of k n m are equivalent to all strings of length n drawn from an alphabet of m symbols. the edges of k n m are equivalent to the neighbourhood relations of such strings. these facts establish the basis upon which we can use these tools to model phonological neighbourhood networks. ## the hyperlexicon in this paper we introduce the concept of the hyperlexicon. a hyperlexicon h(φ, l) is defined as the phonological neighbourhood network generated from all possible string sequences of lengths {ℓ 1 , . . . ℓ n } for ℓ ∈ l over an alphabet of length φ. figure 7 depicts the hyperlexicon of all 'words' of length 1, 2, and 3, over the alphabet of 0 and 1. @xcite observed that the set of all possible phoneme sequences (i.e. the hyperlexicon) is composed of multiple 'layers', each corresponding to a distinct member of l. this layered struc-2 more generally, k n m is an m × m rook's graph in n dimensions. indeed, phonological neighbourhood networks are necessarily induced subgraphs of the hyperlexicon. for example, the english lexicon consists of strings of varying lengths, with the set of english phonemes as its 'alphabet'. there are some strings of english phonemes which are not part of the english lexicon-i.e. nonwords such as blick and pmisgkr. the set of words in the english lexicon, then, is a subset of the set of all logically possible strings of english phonemes. a hyperlexicon corresponds to the neighbourhood network derived from a set of all logically possible strings of length l, given some set of phonemes of length φ. any subset of this set of strings will correspond to an induced subgraph of the hyperlexicon. any phonological neighbourhood network, then, with words of lengths in l constituted from φ distinct phonemes, is necessarily an induced subgraph of the hyperlexicon h(φ, l). studying properties of the hyperlexicon therefore gives us insight into the possible structures of phonological neighbourhood networks. if l is contiguous, h(φ, l) is necessarily connected (i.e. there is exactly one connected component); if l is not contiguous, 4 then h(φ, l) has multiple connected components. ## the edges between the layers of the hyperlexicon defining the edge set of h(φ, l) is less straightforward than the vertex set and is not fully solved. within each layer, the edges are the same as in the graph k ℓ φ . between the layers the situation is considerably more complex. to begin, we first determine the number of possible unique neighbours for any word. for a word of length ℓ in a language 4 such a scenario is plausible for languages with strict phonotactics requiring an obligatory onset and forbidding codas, i.e. all syllables must be cv. for such languages, @xmath2, 4, 6, 8, . . . }. hua @xcite and senufo @xcite have been reported to have this kind of syllable structure. with φ distinct phonemes, neighbours are generated through the addition, deletion, or substitution of a single phoneme. the number of possible neighbours can be shown to depend upon word length ℓ, alphabet size φ, and the number of pairs of adjacent identical phonemes, described below. ## forbidden subgraphs finally, we begin to attempt to characterize the class of hyperlexicons in terms of forbidden subgraphs. a forbidden subgraph of g is any graph which is not isomorphic to any induced subgraph of g. for example, there is no induced subgraph of k 5 which is isomorphic to c 4 . this fact is illustrated in figure 9 . c 4 is therefore a forbidden subgraph of k 5 . graph structures which are impossible within a hyperlexicon are also impossible within real phonological networks, because real phonological networks are induced subgraphs of a hyperlexicon. understanding the forbidden subgraphs of a hyperlexicon therefore allows us to understand possible natural language networks. ## conclusion this paper has reviewed the basic structure of hyperlexicon graphs. induced subgraphs of hyperlexicon graphs typify the class of phonological neighbourhood networks. it is hoped that the preliminary results presented here will spur further work on the networks, as all known natural languages possess considerably more than 3 phonemes. ab bc babc abc figure 12: s 5 as an induced subgraph of a hyperlexicon with max(l) = 4.