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.     

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.     

Constructing blockmodels: How and why

Blockmodel approaches to network analysis as developed by Harrison White are shown to fall in a broader class of established data analysis methods based on matrix permutations (e.g., clique detection, seriation, permutation algorithms for sparse matrices). Blockmodels are seen as an important generalization of these earlier methods since they permit the data to characterize their own structure, instead of seeking to manifest some preconceived structure which is imposed by the investigator (e.g., cliques, hierarchies, or structural balance). General algorithms for the inductive construction of blockmodels thus occupy a central position in the development of the area. We discuss theoretical and practical aspects of the blockmodel search procedure which has been most widely used (CONCOR algorithm). It is proposed that the distinctive and advantageous feature of CONCOR is that it solves what is initially presented as a combinatorial problem (permutations of matrices to reveal zeroblocks) by representing the problem as a continuous one (analysis of correlation matrices). When this representation strategy receives further development, it is predicted that the fairly crude empirical approach of CONCOR will be supplanted by more powerful procedures within this same class.     

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.     

Multiobjective Blockmodeling for Social Network Analysis

To date, most methods for direct blockmodeling of social network data have focused on the optimization of a single objective function. However, there are a variety of social network applications where it is advantageous to consider two or more objectives simultaneously. These applications can broadly be placed into two categories: (1) simultaneous optimization of multiple criteria for fitting a blockmodel based on a single network matrix and (2) simultaneous optimization of multiple criteria for fitting a blockmodel based on two or more network matrices, where the matrices being fit can take the form of multiple indicators for an underlying relationship, or multiple matrices for a set of objects measured at two or more different points in time. A multiobjective tabu search procedure is proposed for estimating the set of Pareto efficient blockmodels. This procedure is used in three examples that demonstrate possible applications of the multiobjective blockmodeling paradigm.     

Heuristic Implementation of Dynamic Programming for Matrix Permutation Problems in Combinatorial Data Analysis

Dynamic programming methods for matrix permutation problems in combinatorial data analysis can produce globally-optimal solutions for matrices up to size 30×30, but are computationally infeasible for larger matrices because of enormous computer memory requirements. Branch-and-bound methods also guarantee globally-optimal solutions, but computation time considerations generally limit their applicability to matrix sizes no greater than 35×35. Accordingly, a variety of heuristic methods have been proposed for larger matrices, including iterative quadratic assignment, tabu search, simulated annealing, and variable neighborhood search. Although these heuristics can produce exceptional results, they are prone to converge to local optima where the permutation is difficult to dislodge via traditional neighborhood moves (e.g., pairwise interchanges, object-block relocations, object-block reversals, etc.). We show that a heuristic implementation of dynamic programming yields an efficient procedure for escaping local optima. Specifically, we propose applying dynamic programming to reasonably-sized subsequences of consecutive objects in the locally-optimal permutation, identified by simulated annealing, to further improve the value of the objective function. Experimental results are provided for three classic matrix permutation problems in the combinatorial data analysis literature: (a) maximizing a dominance index for an asymmetric proximity matrix; (b) least-squares unidimensional scaling of a symmetric dissimilarity matrix; and (c) approximating an anti-Robinson structure for a symmetric dissimilarity matrix. We are extremely grateful to the Associate Editor and two anonymous reviewers for helpful suggestions and corrections.     

Optimal Least-Squares Unidimensional Scaling: Improved Branch-and-Bound Procedures and Comparison to Dynamic Programming

There are two well-known methods for obtaining a guaranteed globally optimal solution to the problem of least-squares unidimensional scaling of a symmetric dissimilarity matrix: (a) dynamic programming, and (b) branch-and-bound. Dynamic programming is generally more efficient than branch-and-bound, but the former is limited to matrices with approximately 26 or fewer objects because of computer memory limitations. We present some new branch-and-bound procedures that improve computational efficiency, and enable guaranteed globally optimal solutions to be obtained for matrices with up to 35 objects. Experimental tests were conducted to compare the relative performances of the new procedures, a previously published branch-and-bound algorithm, and a dynamic programming solution strategy. These experiments, which included both synthetic and empirical dissimilarity matrices, yielded the following findings: (a) the new branch-and-bound procedures were often drastically more efficient than the previously published branch-and-bound algorithm, (b) when computationally feasible, the dynamic programming approach was more efficient than each of the branch-and-bound procedures, and (c) the new branch-and-bound procedures require minimal computer memory and can provide optimal solutions for matrices that are too large for dynamic programming implementation.The authors gratefully acknowledge the helpful comments of three anonymous reviewers and the Editor. We especially thank Larry Hubert and one of the reviewers for providing us with the MATLAB files for optimal and heuristic least-squares unidimensional scaling methods.This revised article was published online in June 2005 with all corrections incorporated.     

Models for ordinal hierarchical classes analysis

This paper proposes an ordinal generalization of the hierarchical classes model originally proposed by De Boeck and Rosenberg (1998). Any hierarchical classes model implies a decomposition of a two-way two-mode binary arrayM into two component matrices, called bundle matrices, which represent the association relation and the set-theoretical relations among the elements of both modes inM. Whereas the original model restricts the bundle matrices to be binary, the ordinal hierarchical classes model assumes that the bundles are ordinal variables with a prespecified number of values. This generalization results in a classification model with classes ordered along ordinal dimensions. The ordinal hierarchical classes model is shown to subsume Coombs and Kao's (1955) model for nonmetric factor analysis. An algorithm is described to fit the model to a given data set and is subsequently evaluated in an extensive simulation study. An application of the model to student housing data is discussed.     

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.     

Compact integer-programming models for extracting subsets of stimuli from confusion matrices

This paper presents an integer linear programming formulation for the problem of extracting a subset of stimuli from a confusion matrix. The objective is to select stimuli such that total confusion among the stimuli is minimized for a particular subset size. This formulation provides a drastic reduction in the number of variables and constraints relative to a previously proposed formulation for the same problem. An extension of the formulation is provided for a biobjective problem that considers both confusion and recognition in the objective function. Demonstrations using an empirical interletter confusion matrix from the psychological literature revealed that a commercial branch-and-bound integer programming code was always able to identify optimal solutions for both the single-objective and biobjective formulations within a matter of seconds. A further extension and demonstration of the model is provided for the extraction of multiple subsets of stimuli, wherein the objectives are to maximize similarity within subsets and minimize similarity between subsets.     

Techniques for rotating two or more loading matrices to optimal agreement and simple structure: A comparison and some technical details

Matrices of factor loadings are often rotated to simple structure. When more than one loading matrix is available for the same variables, the loading matrices can be compared after rotating them all (separately) to simple structure. An alternative procedure is to rotate them to optimal agreement, and then compare them. In the present paper techniques are described that combine these two procedures. Specifically, five techniques that combine the ideals of rotation to optimal agreement and rotation to simple structure are compared on the basis of contrived and empirical data. For the contrived data, it is assessed to what extent the rotations recover the underlying common structure. For both the contrived and the empirical data it is studied to what extent the techniques give well matching rotated matrices, to what extent these have a simple structure, and to what extent the most prominent parts of the different loading matrices agree. It was found that the simple procedure of combining a Generalized Procrustes Analysis (GPA) with Varimax on the mean of the matched loading matrices performs very well on all criteria, and, for most purposes, offers an attractive compromise of rotation to agreement and simple structure. In addition to this comparison, some technical improvements are proposed for Bloxom's rotation to simple structure and maximum similarity.This research has been made possible by a fellowship from the Royal Netherlands Academy of Arts and Sciences to the author. The author is obliged to René van der Heijden for assistance in programming the procedures in the simulation study reported in this paper, and to Jos ten Berge, three anonymous reviewers and an associate editor for helpful comments on an earlier version of this paper.     

The approximation of two-mode proximity matrices by sums of order-constrained matrices

A least-squares strategy is proposed for representing a two-mode proximity matrix as an approximate sum of a small number of matrices that satisfy certain simple order constraints on their entries. The primary class of constraints considered define Q-forms (or anti-Q-forms) for a two-mode matrix, where after suitable and separate row and column reorderings, the entries within each row and within each column are nondecreasing (or nonincreasing) to a maximum (or minimum) and thereafter nonincreasing (or nondecreasing). Several other types of order constraints are also mentioned to show how alternative structures can be considered using the same computational strategy.     

Connection-Driven Inductive Theorem Proving

We present a method for integrating rippling-based rewriting into matrix-based theorem proving as a means for automating inductive specification proofs. The selection of connections in an inductive matrix proof is guided by symmetries between induction hypothesis and induction conclusion. Unification is extended by decision procedures and a rippling/reverse-rippling heuristic. Conditional substitutions are generated whenever a uniform substitution is impossible. We illustrate the integrated method by discussing several inductive proofs for the integer square root problem as well as the algorithms extracted from these proofs.     

On Nonequivalence of Several Procedures of Structural Equation Modeling

The normal theory based maximum likelihood procedure is widely used in structural equation modeling. Three alternatives are: the normal theory based generalized least squares, the normal theory based iteratively reweighted least squares, and the asymptotically distribution-free procedure. When data are normally distributed and the model structure is correctly specified, the four procedures are asymptotically equivalent. However, this equivalence is often used when models are not correctly specified. This short paper clarifies conditions under which these procedures are not asymptotically equivalent. Analytical results indicate that, when a model is not correct, two factors contribute to the nonequivalence of the different procedures. One is that the estimated covariance matrices by different procedures are different, the other is that they use different scales to measure the distance between the sample covariance matrix and the estimated covariance matrix. The results are illustrated using real as well as simulated data. Implication of the results to model fit indices is also discussed using the comparative fit index as an example. The work described in this paper was supported by a grant from the Research Grants Council of Hong Kong Special Administrative Region (Project No. CUHK 4170/99M) and by NSF grant DMS04-37167.     

Divergence Behaviour of the Successive Geometric Mean Method of Pairwise Comparison Matrix Generation for a Multiple Stage,Multiple Objective Optimization Problem

This paper focuses on the divergence behaviour of the successive geometric mean (SGM) method used to generate pairwise comparison matrices while solving a multiple stage, multiple objective (MSMO) optimization problem. The SGM method can be used in the matrix generation phase of our three‐phase methodology to obtain pairwise comparison matrix at each stage of an MSMO optimization problem, which can be subsequently used to obtain the weight vector at the corresponding stage. The weight vectors across the stages can be used to convert an MSMO problem into a multiple stage, single objective (MSSO) problem, which can be solved using dynamic programming‐based approaches. To obtain a practical set of non‐dominated solutions (also referred to as Pareto optimal solutions) to the MSMO optimization problem, it is important to use a solution approach that has the potential to allow for a better exploration of the Pareto optimal solution space. To accomplish a more exhaustive exploration of the Pareto optimal solution space, the weight vectors that are used to scalarize the MSMO optimization problem into its corresponding MSSO optimization problem should vary across the stages. Distinct weight vectors across the stages are tied directly with distinct pairwise comparison matrices across the stages. A pairwise comparison matrix generation method is said to diverge if it can generate distinct pairwise comparison matrices across the stages of an MSMO optimization problem. In this paper, we demonstrate the SGM method's divergence behaviour when the three‐phase methodology is used in conjunction with an augmented high‐dimensional, continuous‐state stochastic dynamic programming method to solve a large‐scale MSMO optimization problem. Copyright © 2013 John Wiley & Sons, Ltd.     

Confirmatory factor analysis of single- and multiple-factor competing models of the dissociative experiences scale in a nonclinical sample

Previous research on the Dissociative Experiences Scale (DES) has demonstrated that (a) dissociation is quantifiable in both clinical and nonclinical samples and (b) a three-factor structure (amnesia, depersonalization, and absorption) is tenable for clinical samples. The factor structurefor nonclinical samples is less clear, with one- and multiple-factor solutions proposed. To clarify the DESfactor structure in nonclinical samples, confirmatory factor analyses were conducted on (a) one-, two-, three-, and four-factorfirst-order models and (b) two bifactor (hierarchical) models of DES scoresfor two samples of nonclinical university students. Results of delta(chi2) and goodness-of-fit indices support the three-factor (first-order) model as bestfitting of the datafor these samples. The utility of this DES model for screening both dissociative pathology and elevated normal dissociative behavior in clinical and nonclinical populations is discussed.     

Identifying a Reordering of Rows and Columns for Multiple Proximity Matrices Using Multiobjective Programming

This paper is concerned with a problem where K (n×n) proximity matrices are available for a set of n objects. The goal is to identify a single permutation of the n objects that provides an adequate structural fit, as measured by an appropriate index, for each of the K matrices. A multiobjective programming approach for this problem, which seeks to optimize a weighted function of the K indices, is proposed, and illustrative examples are provided using a set of proximity matrices from the psychological literature. These examples show that, by solving the multiobjective programming model under different weighting schemes, the quantitative analyst can uncover information about the relationships among the matrices and often identify one or more permutations that provide good to excellent index values for all matrices.     

Factor analysis of the Beck Scale for Suicide Ideation with female suicide attempters

A sample of 119 female suicide attempters completed the Beck Scale for Suicide Ideation (BSS). Although confirmatory common factor analyses of BSS items failed to support previously hypothesized one-, two-, or three-factor models, confirmatory principal components analyses substantiated hypothesized one- and two-dimensional models. Heuristics for the number of factors converged on two latent dimensions and exploratory principal components analyses verified the presence of two previously hypothesized suicide ideation factors: motivation and preparation. Scales based on this two-dimensional model demonstrated convergent validity with other suicide indices.     

Inferring the structure of latent class

Present optimization techniques in latent class analysis apply the expectation maximization algorithm or the Newton-Raphson algorithm for optimizing the parameter values of a prespecified model. These techniques can be used to find maximum likelihood estimates of the parameters, given the specified structure of the model, which is defined by the number of classes and, possibly, fixation and equality constraints. The model structure is usually chosen on theoretical grounds. A large variety of structurally different latent class models can be compared using goodness-of-fit indices of the chi-square family, Akaike’s information criterion, the Bayesian information criterion, and various other statistics. However, finding the optimal structure for a given goodness-of-fit index often requires a lengthy search in which all kinds of model structures are tested. Moreover, solutions may depend on the choice of initial values for the parameters. This article presents a new method by which one can simultaneously infer the model structure from the data and optimize the parameter values. The method consists of a genetic algorithm in which any goodness-of-fit index can be used as a fitness criterion. In a number of test cases in which data sets from the literature were used, it is shown that this method provides models that fit equally well as or better than the models suggested in the original articles.     

The LMPCA program: A graphical user interface for fitting the linked-mode PARAFAC-PCA model to coupled real-valued data

In behavioral research, PARAFAC analysis, a three-mode generalization of standard principal component analysis (PCA), is often used to disclose the structure of three-way three-mode data. To get insight into the underlying mechanisms, one often wants to relate the component matrices resulting from such a PARAFAC analysis to external (two-way two-mode) information, regarding one of the modes of the three-way data. To this end, linked-mode PARAFAC-PCA analysis can be used, in which the three-way and the two-way data set, which have one mode in common, are simultaneously analyzed. More specifically, a PARAFAC and a PCA model are fitted to the three-way and the two-way data, respectively, restricting the component matrix for the common mode to be equal in both models. Until now, however, no software program has been publicly available to perform such an analysis. Therefore, in this article, the LMPCA program, a free and easy-to-use MATLAB graphical user interface, is presented to perform a linked-mode PARAFAC-PCA analysis. The LMPCA software can be obtained from the authors at http://ppw.kuleuven.be/okp/software/LMPCA. For users who do not have access to MATLAB, a stand-alone version is provided.