| Abstract: | Any finite graph (nondirected, no loops) can be coupled with its complementary graph producing what we term a completed graph. This paper studies completed graphs in the context of a structural concept called stratification that is motivated by theoretical work in social psychology and sociology. A completed graph is stratified in case its node (vertex) set can be divided into two nonempty subsets with exactly one of the two types of ties holding between every pair of nodes from distinct sets. A completed graph is totally stratified in case every one of its nontrivial completed subgraphs is stratified. The first part of the paper relates the concept of stratification to the familiar graph property of connectedness. In particular, a completed graph is totally stratified if and only if it does not have a four point completed subgraph that is connected in both the original graph relation and its complementary relation. Using the concept of stratification, completed graphs can be decomposed uniquely into taxonomic structures, that is, nested sets of partitions. An algorithm for the decomposition based on the work with the concept of stratification is developed. The relationship between the notion of stratification and the ideas in balance theory is examined, and stratification is viewed as a generalization of Davis' notion of clustering. It turns out that the concepts of clique, status, and structural equivalence used throughout the social networks literature can be defined in an interesting way for completed graphs. Cliques are sets of nodes with similar internal links and statuses are sets of nodes with similar external links. Structurally equivalent sets are both cliques and statuses. The concepts of status and structural equivalence are closely related to the decomposition algorithm. In particular, for any totally stratified completed graph, the set of all statuses and the set of all maximal structurally equivalent sets can be generated by mathematical operations performed on the taxonomic decomposition of the completed graph. Finally some of our resuls are informally related to the blockmodeling approach to analyzing social network data discussed in several previous Journal of Mathematical Psychology articles. |
