An improved spectral clustering method for community detection under the degree-corrected stochastic blockmodel

• URL: http://arxiv.org/abs/2011.06374v1
• Date: Thu, 12 Nov 2020 13:35:11 GMT
• Title: An improved spectral clustering method for community detection under the degree-corrected stochastic blockmodel
• Authors: Huan Qing and Jingli Wang
• Abstract summary: We propose an improved spectral clustering (ISC) approach under the degree corrected block model (SBM) ISC provides a significant improvement on two weak signal networks Simmons and Caltech, with error rates of 121/1137 and 96/590, respectively.
• Score: 1.0965065178451106
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: For community detection problem, spectral clustering is a widely used method for detecting clusters in networks. In this paper, we propose an improved spectral clustering (ISC) approach under the degree corrected stochastic block model (DCSBM). ISC is designed based on the k-means clustering algorithm on the weighted leading K + 1 eigenvectors of a regularized Laplacian matrix where the weights are their corresponding eigenvalues. Theoretical analysis of ISC shows that under mild conditions the ISC yields stable consistent community detection. Numerical results show that ISC outperforms classical spectral clustering methods for community detection on both simulated and eight empirical networks. Especially, ISC provides a significant improvement on two weak signal networks Simmons and Caltech, with error rates of 121/1137 and 96/590, respectively.

Related papers

• Self-Supervised Graph Embedding Clustering [70.36328717683297]
  K-means one-step dimensionality reduction clustering method has made some progress in addressing the curse of dimensionality in clustering tasks. We propose a unified framework that integrates manifold learning with K-means, resulting in the self-supervised graph embedding framework.
  arXiv  Detail & Related papers  (2024-09-24T08:59:51Z)
• Rethinking Clustered Federated Learning in NOMA Enhanced Wireless Networks [60.09912912343705]
  This study explores the benefits of integrating the novel clustered federated learning (CFL) approach with non-independent and identically distributed (non-IID) datasets. A detailed theoretical analysis of the generalization gap that measures the degree of non-IID in the data distribution is presented. Solutions to address the challenges posed by non-IID conditions are proposed with the analysis of the properties.
  arXiv  Detail & Related papers  (2024-03-05T17:49:09Z)
• Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [79.46465138631592]
  We devise an efficient algorithm that recovers clusters using the observed labels. We present Instance-Adaptive Clustering (IAC), the first algorithm whose performance matches these lower bounds both in expectation and with high probability.
  arXiv  Detail & Related papers  (2023-06-18T08:46:06Z)
• Perfect Spectral Clustering with Discrete Covariates [68.8204255655161]
  We propose a spectral algorithm that achieves perfect clustering with high probability on a class of large, sparse networks. Our method is the first to offer a guarantee of consistent latent structure recovery using spectral clustering.
  arXiv  Detail & Related papers  (2022-05-17T01:41:06Z)
• Spectral clustering via adaptive layer aggregation for multi-layer networks [6.0073653636512585]
  We propose integrative spectral clustering approaches based on effective convex layer aggregations. We show that our methods are remarkably competitive compared to several popularly used methods.
  arXiv  Detail & Related papers  (2020-12-07T21:58:18Z)
• Consistency of regularized spectral clustering in degree-corrected mixed membership model [1.0965065178451106]
  We propose an efficient approach called mixed regularized spectral clustering (Mixed-RSC for short) based on the regularized Laplacian matrix. Mixed-RSC is designed based on an ideal cone structure of the variant for the eigen-decomposition of the population regularized Laplacian matrix. We show that the algorithm is consistent under mild conditions by providing error bounds for the inferred membership vector of each node.
  arXiv  Detail & Related papers  (2020-11-23T02:30:53Z)
• Dual regularized Laplacian spectral clustering methods on community detection [1.0965065178451106]
  We propose a dual regularized graph Laplacian matrix and employ it to three classical spectral clustering approaches under the degree-corrected block model. Three improved spectral clustering methods are dual regularized spectral clustering (DRSC) method, dual regularized spectral clustering on Ratios-of-eigenvectors (DRSCORE) method, and dual regularized symmetrized Laplacian inverse matrix (DRSLIM) method.
  arXiv  Detail & Related papers  (2020-11-09T12:49:25Z)
• Randomized spectral co-clustering for large-scale directed networks [15.486507430729052]
  Co-clustering aims to cluster the senders and receivers of directed networks simultaneously. We leverage sketching techniques and derive two randomized spectral co-clustering algorithms. We establish their approximation error rates and misclustering error rates, indicating better bounds than the state-of-the-art results of co-clustering literature.
  arXiv  Detail & Related papers  (2020-04-25T15:00:55Z)
• A unified framework for spectral clustering in sparse graphs [47.82639003096941]
  We show that a conveniently parametrized form of regularized Laplacian matrix can be used to perform spectral clustering in sparse networks. We also exhibit important connections between this proposed matrix and the now popular non-backtracking matrix, the Bethe-Hessian matrix.
  arXiv  Detail & Related papers  (2020-03-20T10:58:37Z)
• Clustering Binary Data by Application of Combinatorial Optimization Heuristics [52.77024349608834]
  We study clustering methods for binary data, first defining aggregation criteria that measure the compactness of clusters. Five new and original methods are introduced, using neighborhoods and population behavior optimization metaheuristics. From a set of 16 data tables generated by a quasi-Monte Carlo experiment, a comparison is performed for one of the aggregations using L1 dissimilarity, with hierarchical clustering, and a version of k-means: partitioning around medoids or PAM.
  arXiv  Detail & Related papers  (2020-01-06T23:33:31Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.