Graph-theoretic representations for proximity matrices through strongly-anti-Robinson or circular strongly-anti-Robinson matrices

There are various optimization strategies for approximating, through the minimization of a least-squares loss function, a given symmetric proximity matrix by a sum of matrices each subject to some collection of order constraints on its entries. We extend these approaches to include components in the approximating sum that satisfy what are called the strongly-anti-Robinson (SAR) or circular strongly-anti-Robinson (CSAR) restrictions. A matrix that is SAR or CSAR is representable by a particular graph-theoretic structure, where each matrix entry is reproducible from certain minimum path lengths in the graph. One published proximity matrix is used extensively to illustrate the types of approximation that ensue when the SAR or CSAR constraints are imposed.The authors are indebted to Boris Mirkin who first noted in a personal communication to one of us (LH, April 22, 1996) that the optimization method for fitting anti-Robinson matrices in Hubert and Arabie (1994) should be extendable to the fitting of strongly anti-Robinson matrices as well.     

Note on matrices of random numbers

The statistical and structural characteristics of 13 matrices of random numbers in which both the cells and the entries were randomly chosen are discussed. Each matrix was explored considering row means, standard deviations, and correlations as well as column means, standard deviations, and correlations. A study concerning the sequential arrangement of digits was performed by finding out in tables of random numbers how many times the values 0 to 9 are followed by any other digit. Analyses indicate clear factor structures when factor analyzing correlations of rows and of columns and when examining sequential arrangements, concluding that for a given set of digits it is possible to assert both randomness and nonrandomness depending on how the data are examined.     

Inducing a blockmodel structure of two-mode binary data using seriation procedures

We show that seriation of the rows and columns of a two-mode, binary matrix can be an effective method for producing a reordering of the matrix that reveals a blockmodel structure of the data. The objective criterion of the seriation process is based on Robinson patterning of matrix elements. The key advantages of the proposed method are: (a) it can be used in conjunction with existing two-mode blockmodeling algorithms by facilitating selection of the number of classes for the rows and columns of the matrix and the appropriate types of ideal blocks; (b) the model uses a well-grounded index based on Robinson structure, (c) guaranteed optimal solutions can be obtained for problems of practical size, and (d) the seriation method is frequently capable of producing a solution that has a substantive interpretation with respect to the orderings of the row objects and column items.     

Matrices with a given number of violations of Regular Minimality

A row (or column) of an n×n matrix complies with Regular Minimality (RM) if it has a unique minimum entry which is also a unique minimum entry in its column (respectively, row). The number of violations of RM in a matrix is defined as the number of rows (equivalently, columns) that do not comply with RM. We derive a formula for the proportion of n×n matrices with a given number of violations of RM among all n×n matrices with no tied entries. The proportion of matrices with no more than a given number of violations can be treated as the p-value of a permutation test whose null hypothesis states that all permutations of the entries of a matrix without ties are equiprobable, and the alternative hypothesis states that RM violations occur with lower probability than predicted by the null hypothesis. A matrix with ties is treated as being represented by all matrices without ties that have the same set of strict inequalities among their entries.     

A branch-and-bound algorithm for fitting anti-robinson structures to symmetric dissimilarity matrices

The seriation of proximity matrices is an important problem in combinatorial data analysis and can be conducted using a variety of objective criteria. Some of the most popular criteria for evaluating an ordering of objects are based on (anti-) Robinson forms, which reflect the pattern of elements within each row and/or column of the reordered matrix when moving away from the main diagonal. This paper presents a branch-and-bound algorithm that can be used to seriate a symmetric dissimilarity matrix by identifying a reordering of rows and columns of the matrix optimizing an anti-Robinson criterion. Computational results are provided for several proximity matrices from the literature using four different anti-Robinson criteria. The results suggest that with respect to computational efficiency, the branch-and-bound algorithm is generally competitive with dynamic programming. Further, because it requires much less storage than dynamic programming, the branch-and-bound algorithm can provide guaranteed optimal solutions for matrices that are too large for dynamic programming implementations.     

Simultaneous analysis of coupled data matrices subject to different amounts of noise

In many areas of science, research questions imply the analysis of a set of coupled data blocks, with, for instance, each block being an experimental unit by variable matrix, and the variables being the same in all matrices. To obtain an overall picture of the mechanisms that play a role in the different data matrices, the information in these matrices needs to be integrated. This may be achieved by applying a data‐analytic strategy in which a global model is fitted to all data matrices simultaneously, as in some forms of simultaneous component analysis (SCA). Since such a strategy implies that all data entries, regardless the matrix they belong to, contribute equally to the analysis, it may obfuscate the overall picture of the mechanisms underlying the data when the different data matrices are subject to different amounts of noise. One way out is to downweight entries from noisy data matrices in favour of entries from less noisy matrices. Information regarding the amount of noise that is present in each matrix, however, is, in most cases, not available. To deal with these problems, in this paper a novel maximum‐likelihood‐based simultaneous component analysis method, referred to as MxLSCA, is proposed. Being a stochastic extension of SCA, in MxLSCA the amount of noise in each data matrix is estimated and entries from noisy data matrices are downweighted. Both in an extensive simulation study and in an application to data stemming from cross‐cultural emotion psychology, it is shown that the novel MxLSCA strategy outperforms the SCA strategy with respect to disclosing the mechanisms underlying the coupled data.     

A variable neighborhood search method for generalized blockmodeling of two-mode binary matrices

The clustering of two-mode proximity matrices is a challenging combinatorial optimization problem that has important applications in the quantitative social sciences. We focus on one particular type of problem related to the clustering of a two-mode binary matrix, which is relevant to the establishment of generalized blockmodels for social networks. In this context, clusters for the rows of the two-mode matrix intersect with clusters of the columns to form blocks, which should ideally be either complete (all 1s) or null (all 0s). A new procedure based on variable neighborhood search is presented and compared to an existing two-mode K-means clustering algorithm. The new procedure generally provided slightly greater explained variation; however, both methods yielded exceptional recovery of cluster structure.     

The rowwise correlation between two proximity matrices and the partial rowwise correlation

This paper discusses rowwise matrix correlation, based on the weighted sum of correlations between all pairs of corresponding rows of two proximity matrices, which may both be square (symmetric or asymmetric) or rectangular. Using the correlation coefficients usually associated with Pearson, Spearman, and Kendall, three different rowwise test statistics and their normalized coefficients are discussed, and subsequently compared with their nonrowwise alternatives like Mantel'sZ. It is shown that the rowwise matrix correlation coefficient between two matricesX andY is the partial correlation between the entries ofX andY controlled for the nominal variable that has the row objects as categories. Given this fact, partial rowwise correlations (as well as multiple regression extensions in the case of Pearson's approach) can be easily developed.The author wishes to thank the Editor, two referees, Jan van Hooff, and Ruud Derix for their useful comments, and E. J. Dietz for a copy of the algorithm of the Mantel permutation test.     

A Tabu-Search Heuristic for Deterministic Two-Mode Blockmodeling of Binary Network Matrices

Two-mode binary data matrices arise in a variety of social network contexts, such as the attendance or non-attendance of individuals at events, the participation or lack of participation of groups in projects, and the votes of judges on cases. A popular method for analyzing such data is two-mode blockmodeling based on structural equivalence, where the goal is to identify partitions for the row and column objects such that the clusters of the row and column objects form blocks that are either complete (all 1s) or null (all 0s) to the greatest extent possible. Multiple restarts of an object relocation heuristic that seeks to minimize the number of inconsistencies (i.e., 1s in null blocks and 0s in complete blocks) with ideal block structure is the predominant approach for tackling this problem. As an alternative, we propose a fast and effective implementation of tabu search. Computational comparisons across a set of 48 large network matrices revealed that the new tabu-search heuristic always provided objective function values that were better than those of the relocation heuristic when the two methods were constrained to the same amount of computation time.     

Constrained multidimensional unfolding of confusion matrices: Goal point and slide vector models

Two constrained multidimensional unfolding models, the goal point and slide vector models, are proposed for analyzing confusion matrices. In both models, the row and column stimuli are expressed as two sets of points in a low-dimensional space, where the difference vector connecting a column point to the corresponding row point indicates the change in the stimulus representation through a cognitive process. The difference vector is constrained by the hypothesis that the trend in the representational change is invariant across stimuli: the goal point model constrains all difference vectors to point toward a single point, and the slide vector model constrains all difference vectors to be parallel to each other. In both models the coordinates of points are estimated by the maximum-likelihood method. Examples illustrate that the two models allow us to examine hypotheses about invariant trends in representational changes and to grasp such trends from the resulting configurations.     

Generalized constrained multiple correspondence analysis

A comprehensive approach for imposing both row and column constraints on multivariate discrete data is proposed that may be called generalized constrained multiple correspondence analysis (GCMCA). In this method each set of discrete data is first decomposed into several submatrices according to its row and column constraints, and then multiple correspondence analysis (MCA) is applied to the decomposed submatrices to explore relationships among them. This method subsumes existing constrained and unconstrained MCA methods as special cases and also generalizes various kinds of linearly constrained correspondence analysis methods. An example is given to illustrate the proposed method.Heungsun Hwang is now at Claes Fornell International Group. The work reported in this paper was supported by Grant A6394 from the Natural Sciences and Engineering Research Council of Canada to the second author.     

A Quasi-Metric Approach to Multidimensional Unfolding for Reducing the Occurrence of Degenerate Solutions

In multidimensional unfolding (MDU), one typically deals with two-way, two-mode dominance data in estimating a joint space representation of row and column objects in a derived Euclidean space. Unfortunately, most unfolding procedures, especially nonmetric ones, are prone to yielding degenerate solutions where the two sets of points (row and column objects) are disjointed or separated in the derived joint space, providing very little insight as to the structure of the input data. We present a new approach to multidimensional unfolding which reduces the occurrence of degenerate solutions. We first describe the technical details of the proposed method. We then conduct a Monte Carlo simulation to demonstrate the superior performance of the proposed model compared to two non-metric procedures, namely, ALSCAL and KYST. Finally, we evaluate the performance of alternative models in two applications. The first application deals with student rank-order preferences (nonmetric data) for attending various graduate business (MBA) programs. Here, we compare the performance of our model with those of KYST and ALSCAL. The second application concerns student preference ratings (metric data) for a number of popular brands of analgesics. Here, we compare the performance of the proposed model with those of two metric procedures, namely, SMACOF-3 and GENFOLD 3. Finally, we provide some directions for future research.     

Correspondence analysis and association models constrained by a conditional independence graph

The manner in which the conditional independence graph of a multiway contingency table effects the fitting and interpretation of the Goodman association model (RC) and of correspondence analysis (CA) is considered.Estimation of the row and column scores is presented in this context by developing a unified framework that includes both models. Incorporation of the conditional independence constraints inherent in the graph may lead to equal or additive scores for the corresponding marginal tables, depending on the topology of the graph. An example of doubly additive scores in the analysis of a Burt subtable is given.Thanks are due to anonymous referees who substantially improved the original draft of this paper.     

A nonmetric variety of linear factor analysis

The numbers in each column of ann ×m matrix of multivariate data are interpreted as giving the measured values of alln of the objects studied on one ofm different variables. Except for random error, the rank order of the numbers in such a column is assumed to be determined by a linear rule of combination of latent quantities characterizing each row object with respect to a small number of underlying factors. An approximation to the linear structure assumed to underlie the ordinal properties of the data is obtained by iterative adjustment to minimize an index of over-all departure from monotonicity. The method is “nonmetric” in that the obtained structure in invariant under monotone transformations of the data within each column. Except in certain degenerate cases, the structure is nevertheless determined essentially up to an affine transformation. Tests show (a) that, when the assumed monotone relationships are strictly linear, the recovered structure tends closely to approximate that obtained by standard (metric) factor analysis but (b) that, when these relationships are severely nonlinear, the nonmetric method avoids the inherent tendency of the metric method to yield additional, spurious factors. From the practical standpoint, however, the usefulness of the nonmetric method is limited by its greater computational cost, vulnerability to degeneracy, and sensitivity to error variance.     

A method of determining unbiased distribution in the latin square

The paper describes a method of constructing Latin-square designs in which treatment sequences are unbiased with regard to serial order as well as position of treatment. The procedure is useful for those Latin squares in which the number of cells in each column (or row) is an even number, which, when written in ascending and descending series, contain corresponding ordered numbers prime to each other. Such numbers are 2, 4, 6, 10, 12, 16, 18, 22, 28, 30, 36, etc.     

Integer programs for one- and two-mode blockmodeling based on prespecified image matrices for structural and regular equivalence

Establishing blockmodels for one- and two-mode binary network matrices has typically been accomplished using multiple restarts of heuristic algorithms that minimize functions of inconsistency with an ideal block structure. Although these algorithms likely yield exceptional performance, they are not assured to provide blockmodels that optimize the functional indices. In this paper, we present integer programming models that, for a prespecified image matrix, can produce guaranteed optimal solutions for matrices of nontrivial size. Accordingly, analysts performing a confirmatory analysis of a prespecified blockmodel structure can apply our models directly to obtain an optimal solution. In exploratory cases where a blockmodel structure is not prespecified, we recommend a two-stage procedure, where a heuristic method is first used to identify an image matrix and the integer program is subsequently formulated and solved to identify the optimal solution for that image matrix. Although best suited for ideal block structures associated with structural equivalence, the integer programming models have the flexibility to accommodate functional indices pertaining to regular equivalence. Computational results are reported for a variety of one- and two-mode matrices from the blockmodeling literature.     

The problem of the missing wavelet.

A block face was generated by dividing a drawn face into a matrix of rectangular cells and then making the brightness of each cell equal to the average of the brightnesses within the facial area circumscribed by a cell. A wavelet analysis was performed on the numbers representing the brightnesses of the cells in each row of the matrix, and from each row, the wavelet was deleted which corresponded to the fundamental or the lowest frequency sine wave of a complex wave. The appearance of the block face was not substantially altered by the deletion of the wavelet corresponding to the fundamental.     

Some functional measurement procedures for determining the psychophysical law

Various statistical procedures are ieveloped for determining the psychophysical law within the context of a functional measurement approach to studying stimulus integration in perception. The specific results are limited to additive or multiplicative psychological laws, but the generalization to alternative cognitive algebras is evident. Estimation of parameters of the hypothesized psychophysical law and test of the hypothesis that the row psychophysical law is the same as the column psychophysical law in a two-factor stimulus design is considered for various possible psychophysicaldaws, including linear, polynomial, and power laws.