Dual regularized Laplacian spectral clustering methods on community detection

• URL: http://arxiv.org/abs/2011.04392v1
• Date: Mon, 9 Nov 2020 12:49:25 GMT
• Title: Dual regularized Laplacian spectral clustering methods on community detection
• Authors: Huan Qing and Jingli Wang
• Abstract summary: 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.
• Score: 1.0965065178451106
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Spectral clustering methods are widely used for detecting clusters in networks for community detection, while a small change on the graph Laplacian matrix could bring a dramatic improvement. In this paper, we propose a dual regularized graph Laplacian matrix and then employ it to three classical spectral clustering approaches under the degree-corrected stochastic block model. If the number of communities is known as $K$, we consider more than $K$ leading eigenvectors and weight them by their corresponding eigenvalues in the spectral clustering procedure to improve the performance. 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. Theoretical analysis of DRSC and DRSLIM show that under mild conditions DRSC and DRSLIM yield stable consistent community detection, moreover, DRSCORE returns perfect clustering under the ideal case. We compare the performances of DRSC, DRSCORE and DRSLIM with several spectral methods by substantial simulated networks and eight real-world networks.

Related papers

• 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)
• Semi-Supervised Subspace Clustering via Tensor Low-Rank Representation [64.49871502193477]
  We propose a novel semi-supervised subspace clustering method, which is able to simultaneously augment the initial supervisory information and construct a discriminative affinity matrix. Comprehensive experimental results on six commonly-used benchmark datasets demonstrate the superiority of our method over state-of-the-art methods.
  arXiv  Detail & Related papers  (2022-05-21T01:47:17Z)
• 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)
• An improved spectral clustering method for community detection under the degree-corrected stochastic blockmodel [1.0965065178451106]
  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.
  arXiv  Detail & Related papers  (2020-11-12T13:35:11Z)
• Spectral clustering on spherical coordinates under the degree-corrected stochastic blockmodel [5.156484100374058]
  A novel spectral clustering algorithm is proposed for community detection under the degree-corrected blockmodel. Results show improved performance over competing methods in representing computer networks.
  arXiv  Detail & Related papers  (2020-11-09T16:55:38Z)
• Scalable Hierarchical Agglomerative Clustering [65.66407726145619]
  Existing scalable hierarchical clustering methods sacrifice quality for speed. We present a scalable, agglomerative method for hierarchical clustering that does not sacrifice quality and scales to billions of data points.
  arXiv  Detail & Related papers  (2020-10-22T15:58:35Z)
• Local Graph Clustering with Network Lasso [90.66817876491052]
  We study the statistical and computational properties of a network Lasso method for local graph clustering. The clusters delivered by nLasso can be characterized elegantly via network flows between cluster boundary and seed nodes.
  arXiv  Detail & Related papers  (2020-04-25T17:52:05Z)
• 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)

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.