Extracting Unidimensional Chains from Multidimensional Datasets: A Graph Theory Approach.

Abstract

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)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Feb 01, 1980
Accession Number
ADA091693

Entities

Organizations

  • University of Illinois Urbana–Champaign

Tags

Communities of Interest

  • Biomedical

DTIC Thesaurus Topics

  • Air Force
  • Algorithms
  • Applied Psychology
  • Cognition
  • Computer Programming
  • Computer Programs
  • Computer Science
  • Educational Psychology
  • Educational Technology
  • Graph Theory
  • Manpower Utilization
  • Military Research
  • Personnel Management
  • Psychology
  • Schools
  • Social Sciences
  • United States

Readers

  • Computer Vision.
  • Graph Algorithms and Convex Optimization.
  • Regression Analysis.