# From Discourse Relations to Network Edges: A Network Theory Approach to Discourse Analysis
## 4 Networks and Connectivity
### Network Motifs and Discourse Structure  
The most famous nontrivial quantity of interest characterizing directed networks is the existence or absence of network motifs ([50; 64]). The basic premise behind network motifs is that networks are made of repeating occurrences of simple patterns. Thus, a network is scanned for specific n-node subgraphs (here \(n=3\)). We refer to these three-node subgraphs as patterns and denote them with the letter \(S\), followed by an index number; see Figure 5. The number of occurrences of these patterns in a graph is compared with the number of subgraphs found in appropriately randomized networks, and z-scores are calculated so that one can estimate how likely a particular subgraph is to appear by chance. Z-scores higher than 2 indicate that a particular pattern is frequently present in the actual network, and it is unlikely that this is due to pure chance, since it is infrequent in the randomized graphs. Such a pattern is then termed a network motif. It is equally important to locate patterns that are missing from the original network while they appear in the randomized graphs. Such an absence would indicate that there is a mechanism prohibiting their appearance. We identify them when their associated z-score is less than \(-2\). Such patterns are termed antimotifs, i.e., patterns that are rarer than at random, and may be equally important for revealing aspects of the discourse structure. Thus, we must emphasize the difference between a pattern and a motif. For a pattern to be termed a network motif, it is required that it appears much more often or rarely than it would, on average, appear in random networks. Higher-order patterns (i.e., \(n\geq 4\)) can in principle be studied, but such a task becomes prohibitively difficult in practical cases. There are 199 possible 4-node subgraphs, 9364 5-node subgraphs and so on ([65]). Moreover, to count the number of a specific 4-node subgraph occurrences in a graph of 1600 nodes, the \((^{1600}_{4})\) combinations of nodes should be checked. This is a number on the order of \(10^{11}\), i.e., the computational task quickly becomes unfeasible. Thus, the vast majority of research is conducted consider  
Figure 5: The basic patterns for three-node network motifs. ing the existence of three-node motifs and has been proven a rather fruitful, especially in biological networks ([64; 66; 67; 68; 69; 70; 71]). Figure 5 shows the five three-node subgraphs (patterns) that are possible with two of three directed edges, while no bidirectional edges are allowed. It was a celebrated result in biological networks that the feed-forward loop (\(S2\) in Figure 5) is a network motif of the Transcriptional Regulatory Network (TRN) of the bacterium _E. coli_ ([65]). These subgraphs cannot not be directly mapped to the discourse graphs based on the annotation principles set by both C58 and STAC. Recall that discourse graphs admit two different types of directional edges depending on the type of discourse relation between the two related nodes, namely coordinating vs subordinating ones, and are drawn horizontally or vertically, respectively. Moreover, as mentioned in Section 2.1, our network analysis aims to offer a deep insight to principles of discourse evolvement and to contribute to the discussion as to what dictates the distinction between coordinating and subordinating relations. Between the five possible three-node subgraphs in Figure 5, S3 is excluded, since discourse structure graphs are not allowed to include loops that could relate a node back to itself. Naturally, discourse advancement forbids this type of subgraph and, thus, \(S3\) is excluded from our analysis (although it is not analyzed, we included it in the graphs in Section 5 and in Table 10 with the mean pattern values; see the discussion below).