Graph Theory - Computational Linguistics and Talking Robots - page 169

9. Graph Theory

The binary nature of semantic relations in DBS makes them ideal for a graph-
theoretical analysis: elementary signatures like N

N, etc. may be
represented uniformly as two uninterpreted nodes (vertices) connected by an
uninterpreted line (edge). In this way, the linguistically motivated distinctions
between different parts of speech (nodes) and different kinds of semantic re-
lations (lines) may be abstracted away from. What is focused on instead is the
branching structure and the accessibility of nodes.

/ V, N \ V, A |

9.1 Content Analysis as Undirected and Directed Graphs

Central notions of graph theory are the degree of a node and the degree se-
quence of a graph. Consider, for example, the n=4 (four-node) graph known
as K 4 .K 4 is graph-theoretically complete because each node is connected to
all the other nodes in the graph:

9.1.1 T HE “ COMPLETE ”

N =4 GRAPH K 4

K1 K2

K3 K4

The degree sequence of this graph is 3333 because each of the four nodes is of
degree 3 (i.e., connects three lines). The linguistically motivated signatures of
7.4.1, 7.4.4, and 7.4.5, in contrast, are incomplete. For example, disregarding
any arc 0 line, the degree sequence of the signature in 7.4.1 is 2211, in 7.4.4 is
322111, and in 7.4.5 is 211. 1

1 The order of digits in a degree sequence begins with the highest degree, followed by the next highest
degree, all the way down to the lowest degree nodes in the graph.