A Comparison of Spectral Clustering and the Walktrap Algorithm for Community Detection in Network Psychometrics

Spectral clustering is a well-known method for clustering the vertices of an undirected network. Although its use in network psychometrics has been limited, spectral clustering has a close relationship to the commonly used walktrap algorithm. In this article, we report results from simulation experiments designed to evaluate the ability of spectral clustering and the walktrap algorithm to recover underlying cluster (or community) structure in networks. The salient findings include: (a) the recovery performance of the walktrap algorithm can be improved by using K-means clustering instead of hierarchical clustering; (b) K-means and K-median clustering led to comparable recovery performance when used to cluster vertices based on the eigenvectors of Laplacian matrices in spectral clustering; (c) spectral clustering using the unnormalized Laplacian matrix generally yielded inferior cluster recovery in comparison to the other methods; (d) when the correct number of clusters was provided for the methods, spectral clustering using the normalized Laplacian matrix led to better recovery than the walktrap algorithm; and (e) when the correct number of clusters was not provided, the walktrap algorithm using the Q(w) modularity index was better than spectral clustering using the eigengap heuristic at determining the appropriate number of clusters. Overall, both the walktrap algorithm and spectral clustering of the normalized Laplacian matrix are effective for partitioning the vertices of undirected networks, with the latter performing better in most instances. Translational Abstract The walktrap algorithm has often been used in network psychometrics to identify communities (clusters) of variables. We show that the walktrap algorithm can often be improved by using multistart K-means to group the variables instead of Ward's hierarchical method. We also propose spectral clustering as an alternative approach to community detection and compare it to the walktrap algorithm. Spectral clustering provided better recovery of known underlying cluster structure when the correct number of clusters is provided for the methods. However, when the correct number of clusters was unknown, the walktrap algorithm using modularity to choose the number of clusters outperformed spectral clustering using the eigengap heuristic to choose the number of clusters. Therefore, it seems advantageous to consider using the walktrap algorithm to choose the number of clusters and spectral clustering to actually obtain the communities of items for that selected number of clusters.