Structural traversal
From InterSciWiki
Structural traversal sets are the sociological and graph theory conception [1][2] and measurement of cohesion for maximal social group or graphical boundaries where all pairs of related nodes in a graph have a certain minimal number k of edges or paths connecting them, where the paths have no intermediate nodes in common. It is clear that if two nodes in a graph can be disconnected by removal of k nodes, there can be no more than k node independent paths (structural k-traversals; the node pair is k-traversable) between them. The converse requires proof, and the proof is considered one of the deepest in graph theory.
The vertex-cut version of Menger's theorem proves that a set of elements where [one pair/all pairs] are structurally k-traversable cannot be disconnected except by removal this same minimal number k of nodes, the k-connectivity number. Every subgraph (set of nodes plus their edges) of a graph has a unique k-connectivity number, which defines its level of structural cohesion, and is contained in a unique maximal subgraph (k-component) with this number k. Such maximal subgraphs define the boundaries of structural cohesion. The vertex-cut version of Menger's theorem proves that maximal subgraphs with structural cohesion k, or k-components, are always identitical to those with structural traversal k. It is useful to know that k-components are always a subgraph of a k-core, in which every pair of nodes has at least k edges, although a k-core is not always a k-component. Although a k-core is a subgraph in which all nodes have at least k neighbors, it need not even be connected.
[edit] Examples
Some illustrative examples are presented in the gallery below:
 The 6-node ring in the graph has connectivity-2 or a level 2 of structural traversal because every pair of nodes is connected by two independent paths. The removal of two nodes is also needed to disconnect it. |
 The 6-node component (1-connected) has an embedded 2-component, nodes 1-5 |
 A 6-node clique is a 5-component, structural traversal 5 and structural cohesion 5 |
[edit] See also
[edit] References
[Category:Sociology]
[Category:Social networks]
