Analysis of Complex Networks

8.1 Introduction

In this chapter we introduce a class of tree-like graphs that combines the efficiency of tree-like structures with the expressiveness of general graphs. Our starting point is the notion of a generalized tree (GT)*, that is, a graph with a kernel hierarchical skeleton in conjunction with graph-inducing peripheral edges [17]. We combine this notion with the theory of network optimization problems (NOPs) [60] in order to introduce generalized shortest pathS trees (GPST) as a subclass of the class of GTs. One advantage of this novel class is that it provides a functional semantics of the different types of edges of GTs. Another is that it naturally gives rise to combining graph modeling with conceptual spaces [28] and, thus, with cognitive or, more generally, semiotic modeling. This chapter provides three examples in support of this combination.

The graph model presented in this chapter focuses on structure formation in semiotic networks. Its background is the rising interest in network models due to the renaissance of, so to speak, functionalist models of networking in a wide range of scientific disciplines starting from the famous work of [45] in social psychology and extending into the area of physics [1], quantitative biology [3, 23], quantitative sociology [6, 66], quantitative linguistics [26, 41], and information science [48], to name only a few. See [21, 40, 47] for surveys of this research in the area of the natural sciences and the humanities.

What all these ...