A unified framework for spectral clustering in sparse graphs

• URL: http://arxiv.org/abs/2003.09198v2
• Date: Sun, 10 Oct 2021 15:02:44 GMT
• Title: A unified framework for spectral clustering in sparse graphs
• Authors: Lorenzo Dall'Amico, Romain Couillet, Nicolas Tremblay
• Abstract summary: 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.
• Score: 47.82639003096941
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: This article considers spectral community detection in the regime of sparse networks with heterogeneous degree distributions, for which we devise an algorithm to efficiently retrieve communities. Specifically, we demonstrate that a conveniently parametrized form of regularized Laplacian matrix can be used to perform spectral clustering in sparse networks, without suffering from its degree heterogeneity. Besides, we exhibit important connections between this proposed matrix and the now popular non-backtracking matrix, the Bethe-Hessian matrix, as well as the standard Laplacian matrix. Interestingly, as opposed to competitive methods, our proposed improved parametrization inherently accounts for the hardness of the classification problem. These findings are summarized under the form of an algorithm capable of both estimating the number of communities and achieving high-quality community reconstruction.

Related papers

• Community detection by spectral methods in multi-layer networks [0.0]
  Community detection in multi-layer networks is a crucial problem in network analysis. One algorithm is based on the sum of adjacency matrices, while the other utilizes the debiased sum of squared adjacency matrices. Numerical simulations confirm that our algorithm, employing the debiased sum of squared adjacency matrices, surpasses existing methods for community detection in multi-layer networks.
  arXiv  Detail & Related papers  (2024-03-19T08:29:47Z)
• 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)
• Clustering Ensemble Meets Low-rank Tensor Approximation [50.21581880045667]
  This paper explores the problem of clustering ensemble, which aims to combine multiple base clusterings to produce better performance than that of the individual one. We propose a novel low-rank tensor approximation-based method to solve the problem from a global perspective. Experimental results over 7 benchmark data sets show that the proposed model achieves a breakthrough in clustering performance, compared with 12 state-of-the-art methods.
  arXiv  Detail & Related papers  (2020-12-16T13:01:37Z)
• 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)
• 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)
• 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)
• Refining Similarity Matrices to Cluster Attributed Networks Accurately [0.0]
  This paper aims to increase the accuracy by refining the similarity matrices before applying spectral clustering to them. We verify the practicability of our proposed method by comparing the accuracy of spectral clustering with similarity matrices before and after refining them.
  arXiv  Detail & Related papers  (2020-10-14T07:43:36Z)
• Multi-View Spectral Clustering with High-Order Optimal Neighborhood Laplacian Matrix [57.11971786407279]
  Multi-view spectral clustering can effectively reveal the intrinsic cluster structure among data. This paper proposes a multi-view spectral clustering algorithm that learns a high-order optimal neighborhood Laplacian matrix. Our proposed algorithm generates the optimal Laplacian matrix by searching the neighborhood of the linear combination of both the first-order and high-order base.
  arXiv  Detail & Related papers  (2020-08-31T12:28:40Z)
• Community detection in sparse time-evolving graphs with a dynamical Bethe-Hessian [47.82639003096941]
  This article considers the problem of community detection in sparse dynamical graphs in which the community structure evolves over time. A fast spectral algorithm based on an extension of the Bethe-Hessian matrix is proposed, which benefits from the positive correlation in the class labels and in their temporal evolution.
  arXiv  Detail & Related papers  (2020-06-03T11:44:19Z)

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.