Premium
An algorithm for extracting maximum cardinality subsets with perfect dominance or anti‐Robinson structures
Author(s) -
Brusco Michael J.,
Stahl Stephanie
Publication year - 2007
Publication title -
british journal of mathematical and statistical psychology
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 3.157
H-Index - 51
eISSN - 2044-8317
pISSN - 0007-1102
DOI - 10.1348/000711006x107872
Subject(s) - cardinality (data modeling) , mathematics , seriation (archaeology) , maximization , fibonacci number , row , combinatorics , dominance (genetics) , algorithm , matrix (chemical analysis) , discrete mathematics , mathematical optimization , computer science , data mining , biochemistry , chemistry , materials science , archaeology , database , gene , composite material , history
A common criterion for seriation of asymmetric matrices is the maximization of the dominance index, which sums the elements above the main diagonal of a reordered matrix. Similarly, a popular seriation criterion for symmetric matrices is the maximization of an anti‐Robinson gradient index, which is associated with the patterning of elements in the rows and columns of a reordered matrix. Although perfect dominance and perfect anti‐Robinson structure are rarely achievable for empirical matrices, we can often identify a sizable subset of objects for which a perfect structure is realized. We present and demonstrate an algorithm for obtaining a maximum cardinality (i.e. the largest number of objects) subset of objects such that the seriation of the proximity matrix corresponding to the subset will have perfect structure. MATLAB implementations of the algorithm are available for dominance, anti‐Robinson and strongly anti‐Robinson structures.