Search

An inherent limitation of many popular community detection methods, such as the walktrap and spin glass algorithms, is that they do not allow vertices to have membership in more than one community. Clique percolation remedies this limitation by allowing overlapping communities but does not necessarily produce solutions in accordance with the standard definition of 'community' (i.e., a dense subgraph of the network), often fails to assign all vertices to at least one community and presents formidable model selection challenges. In this paper, we propose a set-covering approach to overlapping community detection that enables overlapping communities to be assembled from maximal cliques, or from candidate communities formed from k-1 adjacent cliques. The promise of this new approach is demonstrated via comparison to clique percolation in a simulation experiment, as well as through application to an empirical psychological network. [ABSTRACT FROM AUTHOR]

The modularity index (Q) is an important criterion for many community detection heuristics used in network psychometrics and its subareas (e.g., exploratory graph analysis). Some heuristics seek to directly maximize Q, whereas others, such as the walktrap algorithm, only use the modularity index post hoc to determine the number of communities. Researchers in network psychometrics have typically not employed methods that are guaranteed to find a partition that maximizes Q, perhaps because of the complexity of the underlying mathematical programming problem. In this paper, for networks of the size commonly encountered in network psychometrics, we explore the utility of finding the partition that maximizes Q via formulation and solution of a clique partitioning problem (CPP). A key benefit of the CPP is that the number of communities is naturally determined by its solution and, therefore, need not be prespecified in advance. The results of two simulation studies comparing maximization of Q to two other methods that seek to maximize modularity (fast greedy and Louvain), as well as one popular method that does not (walktrap algorithm), provide interesting insights as to the relative performances of the methods with respect to identification of the correct number of communities and the recovery of underlying community structure. [ABSTRACT FROM AUTHOR]

The Ising model has received significant attention in network psychometrics during the past decade. A popular estimation procedure is IsingFit, which uses nodewise l1-regularized logistic regression along with the extended Bayesian information criterion to establish the edge weights for the network. In this paper, we report the results of a simulation study comparing IsingFit to two alternative approaches: (1) a nonregularized nodewise stepwise logistic regression method, and (2) a recently proposed global l1-regularized logistic regression method that estimates all edge weights in a single stage, thus circumventing the need for nodewise estimation. MATLAB scripts for the methods are provided as supplemental material. The global l1-regularized logistic regression method generally provided greater accuracy and sensitivity than IsingFit, at the expense of lower specificity and much greater computation time. The stepwise approach showed considerable promise. Relative to the l1-regularized approaches, the stepwise method provided better average specificity for all experimental conditions, as well as comparable accuracy and sensitivity at the largest sample size. [ABSTRACT FROM AUTHOR]

Common outputs of software programs for network estimation include association matrices containing the edge weights between pairs of symptoms and a plot of the symptom network. Although such outputs are useful, it is sometimes difficult to ascertain structural relationships among symptoms from these types of output alone. We propose that matrix permutation provides a simple, yet effective, approach for clarifying the order relationships among the symptoms based on the edge weights of the network. For directed symptom networks, we use a permutation criterion that has classic applications in electrical circuit theory and economics. This criterion can be used to place symptoms that strongly predict other symptoms at the beginning of the ordering, and symptoms that are strongly predicted by other symptoms at the end. For undirected symptom networks, we recommend a permutation criterion that is based on location theory in the field of operations research. When using this criterion, symptoms with many strong ties tend to be placed centrally in the ordering, whereas weakly-tied symptoms are placed at the ends. The permutation optimization problems are solved using dynamic programming. We also make use of branch-search algorithms for extracting maximum cardinality subsets of symptoms that have perfect structure with respect to a selected criterion. Software for implementing the dynamic programming algorithms is available in MATLAB and R. Two networks from the literature are used to demonstrate the matrix permutation algorithms. [ABSTRACT FROM AUTHOR]

Nonnegative matrix factorization (NMF) has become a popular method for establishing a low-dimensional approximation of a two-mode (nonnegative) data matrix and, in some instances, to also establish partitions for the objects associated with the two modes of the matrix. Although similar to singular-value-decomposition, as its name implies, NMF requires nonnegative elements for the factors and this assures a 'sum of the parts' fit to the data. There are a variety of alternative objective functions and heuristic methods for NMF. Using both simulated and real-world two-mode data, we demonstrate that a multiple restart (multistart) heuristic for NMF commonly fails to produce optimal objective function values. A new variable neighborhood search (VNS) heuristic is shown to outperform the multistart approach with respect to both solution quality and computation time. Although the objective function value improvements associated with VNS are often small (on a percentage basis), such improvements can sometimes lead to differences in the partitions obtained for the row and column objects. Application to two well-known microarray datasets is used to support the merits of the proposed VNS heuristic. [ABSTRACT FROM AUTHOR]

This article develops a class of models called sender/receiver finite mixture exponential random graph models (SRFM-ERGMs). This class of models extends the existing exponential random graph modeling framework to allow analysts to model unobserved heterogeneity in the effects of nodal covariates and network features without a block structure. An empirical example regarding substance use among adolescents is presented. Simulations across a variety of conditions are used to evaluate the performance of this technique. We conclude that unobserved heterogeneity in effects of nodal covariates can be a major cause of misfit in network models, and the SRFM-ERGM approach can alleviate this misfit. Implications for the analysis of social networks in psychological science are discussed. [ABSTRACT FROM AUTHOR]

This article addresses the issue of assigning items to different test dimensions (e.g., determining which dimension an item belongs to) with cluster analysis. Previously, hierarchical methods have been used (Roussos et al. 1997); however, the findings here suggest that an iterative reallocation partitioning (IRP) algorithm provides interpretively similar solutions and statistically better solutions to the problem. More importantly, it is shown that the inherent nature of locally optimal solutions in the IRP algorithm leads to a method that aids in determining the appropriateness of performing a cluster analysis—a feature that is lacking in the standard hierarchical methods currently in the literature. [ABSTRACT FROM AUTHOR]

An introduction is presented in which the editor discusses articles in the issue on topics including optimal clustering; intuitionistic fuzzy sets; and ultrametrics and symbolic maps.

The problem of comparing the agreement of two n × n matrices has a variety of applications in experimental psychology. A well-known index of agreement is based on the sum of the element-wise products of the matrices. Although less familiar to many researchers, measures of agreement based on within-row and/or within-column gradients can also be useful. We provide a suite of MATLAB programs for computing agreement indices and performing matrix permutation tests of those indices. Programs for computing exact p-values are available for small matrices, whereas resampling programs for approximate p-values are provided for larger matrices. [ABSTRACT FROM AUTHOR]

An introduction is presented in which the editor discusses articles in the issue on topics including traditional Dendritic Cell Algorithm (DCA), missing data in affine subspaces, and potential mislabeled group data.

An introduction is presented in which the editor discusses various articles in the issue on topics including Bayesian techniques, support vector machine (SVM), and hierarchical clustering.

Mixture modeling is a popular technique for identifying unobserved subpopulations (e.g., components) within a data set, with Gaussian (normal) mixture modeling being the form most widely used. Generally, the parameters of these Gaussian mixtures cannot be estimated in closed form, so estimates are typically obtained via an iterative process. The most common estimation procedure is maximum likelihood via the expectation-maximization (EM) algorithm. Like many approaches for identifying subpopulations, finite mixture modeling can suffer from locally optimal solutions, and the final parameter estimates are dependent on the initial starting values of the EM algorithm. Initial values have been shown to significantly impact the quality of the solution, and researchers have proposed several approaches for selecting the set of starting values. Five techniques for obtaining starting values that are implemented in popular software packages are compared. Their performances are assessed in terms of the following four measures: (1) the ability to find the best observed solution, (2) settling on a solution that classifies observations correctly, (3) the number of local solutions found by each technique, and (4) the speed at which the start values are obtained. On the basis of these results, a set of recommendations is provided to the user. [ABSTRACT FROM AUTHOR]

An introduction is presented in which the editor discusses various reports within the issue including the model-based clustering, the development of a regression mixture approach and the advancement of regression model-based clustering.

An asymmetric one-mode data matrix has rows and columns that correspond to the same set of objects. However, the roles of the objects frequently differ for the rows and the columns. For example, in a visual alphabetic confusion matrix from an experimental psychology study, both the rows and columns pertain to letters of the alphabet. Yet the rows correspond to the presented stimulus letter, whereas the columns refer to the letter provided as the response. Other examples abound in psychology, including applications related to interpersonal interactions (friendship, trust, information sharing) in social and developmental psychology, brand switching in consumer psychology, journal citation analysis in any discipline (including quantitative psychology), and free association tasks in any subarea of psychology. When seeking to establish a partition of the objects in such applications, it is overly restrictive to require the partitions of the row and column objects to be identical, or even the numbers of clusters for the row and column objects to be the same. This suggests the need for a biclustering approach that simultaneously establishes separate partitions of the row and column objects. We present and compare several approaches for the biclustering of one-mode matrices using data sets from the empirical literature. A suite of MATLAB m-files for implementing the procedures is provided as a Web supplement with this article. [ABSTRACT FROM AUTHOR]

The monotone homogeneity model (MHM-also known as the unidimensional monotone latent variable model) is a nonparametric IRT formulation that provides the underpinning for partitioning a collection of dichotomous items to form scales. Ellis (Psychometrika 79:303-316, , doi:) has recently derived inequalities that are implied by the MHM, yet require only the bivariate (inter-item) correlations. In this paper, we incorporate these inequalities within a mathematical programming formulation for partitioning a set of dichotomous scale items. The objective criterion of the partitioning model is to produce clusters of maximum cardinality. The formulation is a binary integer linear program that can be solved exactly using commercial mathematical programming software. However, we have also developed a standalone branch-and-bound algorithm that produces globally optimal solutions. Simulation results and a numerical example are provided to demonstrate the proposed method. [ABSTRACT FROM AUTHOR]

One of the most important distinctions that must be made in clustering research is the difference between models (or problems) and the methods for solving those problems. Nowhere is this more evident than with the evaluation of the popular affinity propagation algorithm (apcluster.m), which is a MATLAB implementation of a neural clustering method that has received significant attention in the biological sciences and other disciplines. Several authors have undertaken comparisons of apcluster.m with methods designed for models that fall within the class of uncapacitated facility location problems (UFLPs). These comparative models include the p-center (or K-center) model and, more importantly, the p-median (or K-median) model. The results across studies are conflicting and clouded by the fact that, although similar, the optimization model underlying apcluster.m is slightly different from the p-median model and appreciably different from the pcenter model. In this paper, we clarify that apcluster.m is actually a heuristic for a 'maximization version' of another model in the class of UFLPs, which is known as the simple plant location problem (SPLP). An exact method for the SPLP is described, and the apcluster.m program is compared to a fast heuristic procedure (sasplp.m) in both a simulation experiment and across numerous datasets from the literature. Although the exact method is the preferred approach when computationally feasible, both apcluster.m and sasplp.m are efficient and effective heuristic approaches, with the latter slightly outperforming the former in most instances. [ABSTRACT FROM AUTHOR]

Because of its deterministic nature, K-means does not yield confidence information about centroids and estimated cluster memberships, although this could be useful for inferential purposes. In this paper we propose to arrive at such information by means of a non-parametric bootstrap procedure, the performance of which is tested in an extensive simulation study. Results show that the coverage of hyper-ellipsoid bootstrap confidence regions for the centroids is in general close to the nominal coverage probability. For the cluster memberships, we found that probabilistic membership information derived from the bootstrap analysis can be used to improve the cluster assignment of individual objects, albeit only in the case of a very large number of clusters. However, in the case of smaller numbers of clusters, the probabilistic membership information still appeared to be useful as it indicates for which objects the cluster assignment resulting from the analysis of the original data is likely to be correct; hence, this information can be used to construct a partial clustering in which the latter objects only are assigned to clusters. [ABSTRACT FROM AUTHOR]

Building on Brusco and Steinley (2008), a computationally efficient stepwise optimal heuristic is provided for maximizing the adjusted Rand index (Hubert and Arabie 1985). The proposed algorithm is different than other methods for estimating the maximum value for the adjusted Rand index (e.g., Messatfa 1992) in that it does not rely on mathematical programming; consequently, problems of much larger size can be handled. Using the proposed method, various characteristics of the adjusted Rand index are explored and presented. [ABSTRACT FROM AUTHOR]

Although socializing effects of friends' drinking on adolescent drinking behavior have been firmly established in previous literature, study results on the importance of gender, as well as the specific role that gender may play in peer socialization, are very mixed. Given the increasing importance of gender in friendships (particularly opposite-sex friendships) during adolescence, it is necessary to better understand the nuanced roles that gender can play in peer socialization effects on alcohol use. In addition, previous studies focusing on the interplay between individual gender and friends' gender have been largely dyadic; less is known about potential gendered effects of broader social networks. The current study sought to further investigate potential effects of gender on friends' influence on adolescent drinking behavior with particular emphasis on the number of same-sex and opposite-sex friends within one's friendship network, as well as closeness to these friends. Using Waves I and II of the saturated sample of the National Longitudinal Study of Adolescent Health (Add Health), adolescent friendship networks were used to calculate the mean drinking behaviors of adolescent friends. Multi-level models estimated the effects of individual drinking behaviors, friend drinking behaviors, and school-level drinking behaviors on adolescent drinking 1 year later, as well as moderating effects of gender composition of friendship groups and male and female friend closeness on the relationship between friends' drinking behaviors and adolescent drinking behavior. Results documented that gender composition of friendship groups did not influence the effect of friends' drinking on individual drinking 1 year later. However, closeness to friends did influence this relationship. As closeness to male friends decreased, the influence of their drinking behavior increased, for both boys and girls. A similar effect was found for female friends, but only for boys. Female friend closeness did not affect the relationship between peer alcohol socialization and girls' alcohol use. The findings indicate that the role of gender on alcohol socialization may be more complex than previously thought, particularly when examining the potential role that alcohol use may play as a mechanism for social bonding within opposite-sex friendships and same-sex male friendships. [ABSTRACT FROM AUTHOR]

One-dimensional bin-packing problems require the assignment of a collection of items to bins with the goal of optimizing some criterion related to the number of bins used or the 'weights' of the items assigned to the bins. In many instances, the number of bins is fixed and the goal is to assign the items such that the sums of the item weights for each bin are approximately equal. Among the possible applications of one-dimensional bin-packing in the field of psychology are the assignment of subjects to treatments and the allocation of students to groups. An especially important application in the psychometric literature pertains to splitting of a set of test items to create distinct subtests, each containing the same number of items, such that the maximum sum of item weights across all bins is minimized. In this context, the weights typically correspond to item statistics derived from difficulty and discrimination indices. We present a mixed zero-one integer linear programming (MZOILP) formulation of this one-dimensional minimax bin-packing problem and develop an approximate procedure for its solution that is based on the simulated annealing algorithm. In two comparisons that focused on 34 practically-sized test problems (up to 6000 items and 300 bins), the simulated annealing heuristic generally provided better solutions than were obtained when using a commercial mathematical programming software package to solve the MZOILP formulation directly. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

The selection of a subset of variables from a pool of candidates is an important problem in several areas of multivariate statistics. Within the context of principal component analysis (PCA), a number of authors have argued that subset selection is crucial for identifying those variables that are required for correct interpretation of the components. In this paper, we adapt the variable neighborhood search (VNS) paradigm to develop two heuristics for variable selection in PCA. The performances of these heuristics were compared to those obtained by a branch-and-bound algorithm, as well as forward stepwise, backward stepwise, and tabu search heuristics. In the first experiment, which considered candidate pools of 18 to 30 variables, the VNS heuristics matched the optimal subset obtained by the branch-and-bound algorithm more frequently than their competitors. In the second experiment, which considered candidate pools of 54 to 90 variables, the VNS heuristics provided better solutions than their competitors for a large percentage of the test problems. An application to a real-world data set is provided to demonstrate the importance of variable selection in the context of PCA. [ABSTRACT FROM AUTHOR]

This paper proposes an order-constrained K-means cluster analysis strategy, and implements that strategy through an auxiliary quadratic assignment optimization heuristic that identifies an initial object order. A subsequent dynamic programming recursion is applied to optimally subdivide the object set subject to the order constraint. We show that although the usual K-means sum-of-squared-error criterion is not guaranteed to be minimal, a true underlying cluster structure may be more accurately recovered. Also, substantive interpretability seems generally improved when constrained solutions are considered. We illustrate the procedure with several data sets from the literature. [ABSTRACT FROM AUTHOR]

This research note focuses on a problem where the cluster sizes for two partitions of the same object set are assumed known; however, the actual assignments of objects to clusters are unknown for one or both partitions. The objective is to find a contingency table that produces maximum possible agreement between the two partitions, subject to constraints that the row and column marginal frequencies for the table correspond exactly to the cluster sizes for the partitions. This problem was described by H. Messatfa ( Journal of Classification, 1992, pp. 5–15), who provided a heuristic procedure based on the linear transportation problem. We present an exact solution procedure using binary integer programming. We demonstrate that our proposed method efficiently obtains optimal solutions for problems of practical size. [ABSTRACT FROM AUTHOR]

Eight different variable selection techniques for model-based and non-model-based clustering are evaluated across a wide range of cluster structures. It is shown that several methods have difficulties when non-informative variables (i.e., random noise) are included in the model. Furthermore, the distribution of the random noise greatly impacts the performance of nearly all of the variable selection procedures. Overall, a variable selection technique based on a variance-to-range weighting procedure coupled with the largest decreases in within-cluster sums of squares error performed the best. On the other hand, variable selection methods used in conjunction with finite mixture models performed the worst. [ABSTRACT FROM AUTHOR]

Perhaps the most common criterion for partitioning a data set is the minimization of the within-cluster sums of squared deviation from cluster centroids. Although optimal solution procedures for within-cluster sums of squares (WCSS) partitioning are computationally feasible for small data sets, heuristic procedures are required for most practical applications in the behavioral sciences. We compared the performances of nine prominent heuristic procedures for WCSS partitioning across 324 simulated data sets representative of a broad spectrum of test conditions. Performance comparisons focused on both percentage deviation from the "best-found" WCSS values, as well as recovery of true cluster structure. A real-coded genetic algorithm and variable neighborhood search heuristic were the most effective methods; however, a straightforward two-stage heuristic algorithm, HK-means, also yielded exceptional performance. A follow-up experiment using 13 empirical data sets from the clustering literature generally supported the results of the experiment using simulated data. Our findings have important implications for behavioral science researchers, whose theoretical conclusions could be adversely affected by poor algorithmic performances. [ABSTRACT FROM AUTHOR]

Given that a minor condition holds (e.g., the number of variables is greater than the number of clusters), a nontrivial lower bound for the sum of squares error criterion in K -means clustering is derived. By calculating the lower bound for several different situations, a method is developed to determine the adequacy of cluster solution based on the observed sum-of squares error as compared to the minimum sum-of-squares error. [ABSTRACT FROM AUTHOR]

K-means clustering is arguably the most popular technique for partitioning data. Unfortunately, K-means suffers from the well-known problem of locally optimal solutions. Furthermore, the final partition is dependent upon the initial configuration, making the choice of starting partitions all the more important. This paper evaluates 12 procedures proposed in the literature and provides recommendations for best practices. [ABSTRACT FROM AUTHOR]

An introduction is presented in which discusses several articles in the issue on topics including a latent structural model (LSM) for polytomous attributes; the important topic of cluster validation; and cognitive diagnosis modelling.

The primary method for validating cluster analysis techniques is through Monte Carlo simulations that rely on generating data with known cluster structure (e.g., Milligan 1996). This paper defines two kinds of data generation mechanisms with cluster overlap, marginal and joint; current cluster generation methods are framed within these definitions. An algorithm generating overlapping clusters based on shared densities from several different multivariate distributions is proposed and shown to lead to an easily understandable notion of cluster overlap. Besides outlining the advantages of generating clusters within this framework, a discussion is given of how the proposed data generation technique can be used to augment research into current classification techniques such as finite mixture modeling, classification algorithm robustness, and latent profile analysis. [ABSTRACT FROM AUTHOR]

An introduction is presented in which the editor discusses articles in the issue on topics including growth mixture modeling; mixture model for a new set of distributions, a multiple scaled generalized hyperbolic distributions; and the traditional cluster analysis.

An introduction is presented in which the editor discusses various reports within the issue on topics including K-means clustering, effect of model misspecification on determining the number of classes in growth mixture modeling and clustering functional data.

An introduction is presented in which the editor discusses various reports within the issue on topics including the fractionally-supervised classification method for unsupervised and supervised learning, semi-definite programming (SDP) method for anlyzing data, and exact algorithm for clustering.