Extracting Unidimensional Chains from Multidimensional Datasets: A Graph Theory Approach

摘要

Reynolds (1976) described an order-analysis procedure for extracting unidimensional chains of items (or persons) from multidimensional datasets. It is an exhaustive method, using one of Cliff's consistency indices to extract all possible chains which maintain a given level of consistency. A practical problem with this method is that the number of computer calculations needed for chain extraction can become very high. This paper outlines a procedure which uses graph theory to extract nonredundant chains efficiently, rather than exhaustively generating all chains, as with Reynold's procedure. It also uses chain consistency as a criterion for chain membership. The dominance matrix can be reconsidered as a labelled digraph. From this digraph, all subgroups with perfect consistency are generated, and these in turn are used as starting points in the chain extraction process. The original dominance digraph is then reduced until the chain is found from each subgraph. This graph-theoretic algorithm may be carried out using a series of matrix manipulations performed on the dominance matrix. (Author)