Analysis of Complex Networks

8.3 Semiotic Systems as Conceptual Graphs

So far we have gained several novel subclasses of the class of GTs. It was Dehmer's [15] task – who first and, up to that time, most comprehensively formalized GTs – to define a similarity measure for classifying given sets of GTs. That is, for a triple of GTs Dehmer [15] determines the most similar pair of GTs. In this chapter we have taken one step back in order to approach an answer to the following question: Given a single graph, which of the GTs derivable from it satisfies which topologically and semiotically founded constraints? Following this line of research we have introduced the notion of a minimum spanning generalized tree (MSGT), of a generalized shortest path tree (GSPT), and of a generalized shortest paths tree (GPST). Especially by the subclass of GPSTs we have gained a detailed semantics of kernel, vertical, reflexive, and lateral edges where the latter have further been divided into the subset of cross-reference and shortcut edges. In Section 8.2.6 we have given a functional semantics of kernel edges as search facilities, of vertical edges as abridging facilities, of shortcut edges as association facilities (in support of large cluster values), and of cross-reference edges as randomization facilities (in support of short average geodesic distances). GTs are a class of graphs that impose functional restrictions on the typing of their edges, which locate this class in between the class of trees and general graphs. In this ...