Mixed-Order Spectral Clustering for Networks
Clustering is fundamental for gaining insights from complex networks, and spectral clustering (SC) is a popular approach. Conventional SC focuses on second-order structures (e.g., edges connecting two nodes) without direct consideration of higher-order structures (e.g., triangles and cliques). This has motivated SC extensions that directly consider higher-order structures. However, both approaches are limited to considering a single order. This paper proposes a new Mixed-Order Spectral Clustering (MOSC) approach to model both second-order and third-order structures simultaneously, with two MOSC methods developed based on Graph Laplacian (GL) and Random Walks (RW). MOSC-GL combines edge and triangle adjacency matrices, with theoretical performance guarantee. MOSC-RW combines first-order and second-order random walks for a probabilistic interpretation. We automatically determine the mixing parameter based on cut criteria or triangle density, and construct new structure-aware error metrics for performance evaluation. Experiments on real-world networks show 1) the superior performance of two MOSC methods over existing SC methods, 2) the effectiveness of the mixing parameter determination strategy, and 3) insights offered by the structure-aware error metrics.
Code (1)
Tasks
ClusteringMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Consistency of regularized spectral clustering in degree-corrected mixed membership model
Community detection in network analysis is an attractive research area recently. Here, under the degree-corrected mixed membership (DCMM) model, we propose an efficient approach called mixed regularized spectral clusteri…
ClusteringCommunity DetectionUnsupervised Diffusion and Volume Maximization-Based Clustering of Hyperspectral Images
Hyperspectral images taken from aircraft or satellites contain information from hundreds of spectral bands, within which lie latent lower-dimensional structures that can be exploited for classifying vegetation and other …
ClusteringImage ClusteringHierarchical Sparse Subspace Clustering (HESSC): An Automatic Approach for Hyperspectral Image Analysis
Hyperspectral imaging techniques are becoming one of the most important tools to remotely acquire fine spectral information on different objects. However, hyperspectral images (HSIs) require dedicated processing for most…
BIG-bench Machine LearningClusteringHyperspectral image analysisSparse subspace-based clusteringSpectral Clustering of Categorical and Mixed-type Data via Extra Graph Nodes
Clustering data objects into homogeneous groups is one of the most important tasks in data mining. Spectral clustering is arguably one of the most important algorithms for clustering, as it is appealing for its theoretic…
ClusteringHigher-Order Spectral Clustering for Geometric Graphs
The present paper is devoted to clustering geometric graphs. While the standard spectral clustering is often not effective for geometric graphs, we present an effective generalization, which we call higher-order spectral…
Clustering