# From Discourse Relations to Network Edges: A Network Theory Approach to Discourse Analysis
## 4 Networks and Connectivity
### Key Network Indices and Their Relevance to Discourse  
Graphs can be either undirected or directed. A directed graph, also called a digraph, is a graph in which the edges have a direction. Pictorially, this is indicated with an arrow on the edge. If \(v\) and \(w\) are vertices, an edge is an unordered pair \([v,w]\), while a directed edge is an ordered pair, \((v,w)\) or \((w,v)\). The directed edge \((v,w)\) is drawn as an arrow from \(v\) to \(w\). Of course, it is possible to treat a digraph as a nondirected network and still obtain valuable information. Our graphs are unweighted, i.e., all edges are treated as equal, and contain no multilinks or self-loops. There are several quantities of interest in the study of networks. Some of them are meaningful for directed as well as for undirected networks, while others are defined for directed graphs only. Thus, typically, the study of a directed network starts by treating it as undirected. When the basic properties of the undirected graph are calculated, then one proceeds by examining the quantities of interest that are associated with the directionality of the graph links. This is the approach that we follow here. When we treat discourse networks as undirected graphs, we are interested in the following quantities:  
1. The number of nodes _nsize_ and the number of edges _nedge_ of the network. In terms of discourse networks, these two indices indicate the size of the network. 2. The fraction of edges \(f_{e}\), which is the ratio of the number of edges _nedge_ to the maximum possible number of edges \(ne_{max}\), i.e., \[f_{e}=\frac{nedge}{ne_{max}}=\frac{nedge}{\frac{(nsize)(nsize-1)}{2}}\] (1) where we use the fact that the max number of undirected edges in a network of _nsize_ nodes is \(ne_{max}=\frac{(nsize)(nsize-1)}{2}\). The fraction \(f_{e}\) is a number between zero and one. In terms of discourse graphs, if \(f_{e}\) is closer to 0, it can be interpreted as an indicator of low connectivity, while in the opposite case, the discourse graph can be considered to have a highly connected structure. 3. The degree centrality of a node is a non-negative integer denoting the number of edges emanating from a node. In our case, utterance labels with a high node degree can be interpreted as having high significance for the discourse evolvement. Here, we study the maximum, minimum and average degree of a network's nodes \(k_{max}\), \(k_{min}\) and \(k_{av}\), respectively, as well as the standard deviation of the degree distribution \(k_{std}\). 4. The mean clustering coefficient \(C\). The (local) clustering coefficient of a node \(i\) in a network is defined as \[C(k_{i})=\frac{t_{i}}{[k_{i}(k_{i}-1)/2]}\] (2) where \(t_{i}\) is the number of triangles (loops of length 3) attached to this node divided by the maximum possible number of such loops ([49]). Here, we compute the average of the local clustering coefficients. It is a number in the range \(0\leq C\leq 1\). Clustering coefficient values \(C\simeq 1\) indicate that two nodes connected to a third common node have a high probability of also being connected to each other. Social networks are typically networks with a high clustering coefficient, since it is probable that individuals that have a common acquaintance know each other as well ([48; 59; 62]). * The degree assortativity coefficient \(r\) ([63]). A network is assortative when nodes of high degree tend to connect to nodes with high degree. It is disassortative when nodes of high degree tend to connect to nodes with low degree. The assortativity coefficient \(r\) lies in the range \(-1\leq r\leq 1\), with \(r=1\) indicating perfect assortativity and \(r=-1\) indicating perfect disassortativity. To be more formal, the assortativity coefficient \(r\) is defined as \[r=\frac{\sum_{jk}jk(e_{jk}-q_{j}q_{k})}{\sigma_{q}^{2}}\] (3) The term \(q_{k}\) is the distribution of the remaining degree, i.e., the number of edges leaving the node, other than the one that connects the pair.