Relations Between Adjacency and Modularity Graph Partitioning

• URL: http://arxiv.org/abs/1505.03481v3
• Date: Wed, 27 Sep 2023 21:18:47 GMT
• Title: Relations Between Adjacency and Modularity Graph Partitioning
• Authors: Hansi Jiang and Carl Meyer
• Abstract summary: This paper develops the exact linear relationship between the leading eigenvector of the unnormalized modularity matrix and the eigenvectors of the adjacency matrix. There is also a complete proof of the equivalence between normalized adjacency clustering and normalized modularity clustering.
• Score: 0.3916094706589679
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper develops the exact linear relationship between the leading eigenvector of the unnormalized modularity matrix and the eigenvectors of the adjacency matrix. We propose a method for approximating the leading eigenvector of the modularity matrix, and we derive the error of the approximation. There is also a complete proof of the equivalence between normalized adjacency clustering and normalized modularity clustering. Numerical experiments show that normalized adjacency clustering can be as twice efficient as normalized modularity clustering.

Related papers

• Asymptotic Theory of Eigenvectors for Latent Embeddings with Generalized Laplacian Matrices [8.874743539416825]
  dependency is a major bottleneck of new random matrix theory developments. We suggest a new framework of eigenvectors for latent embeddings with generalized Laplacian matrices (ATE-GL) We discuss some applications of the suggested ATE-GL framework and showcase its validity through some numerical examples.
  arXiv  Detail & Related papers  (2025-03-01T22:22:42Z)
• Understanding Matrix Function Normalizations in Covariance Pooling through the Lens of Riemannian Geometry [63.694184882697435]
  Global Covariance Pooling (GCP) has been demonstrated to improve the performance of Deep Neural Networks (DNNs) by exploiting second-order statistics of high-level representations.
  arXiv  Detail & Related papers  (2024-07-15T07:11:44Z)
• A Copula Graphical Model for Multi-Attribute Data using Optimal Transport [9.817170209575346]
  We introduce a novel semiparametric multi-attribute graphical model based on a new copula named Cyclically Monotone Copula. For the setting with high-dimensional attributes, a Projected Cyclically Monotone Copula model is proposed to address the curse of dimensionality issue.
  arXiv  Detail & Related papers  (2024-04-10T04:49:00Z)
• Synergistic eigenanalysis of covariance and Hessian matrices for enhanced binary classification [72.77513633290056]
  We present a novel approach that combines the eigenanalysis of a covariance matrix evaluated on a training set with a Hessian matrix evaluated on a deep learning model. Our method captures intricate patterns and relationships, enhancing classification performance.
  arXiv  Detail & Related papers  (2024-02-14T16:10:42Z)
• Clustering Three-Way Data with Outliers [1.0435741631709405]
  An approach for clustering matrix-variate normal data with outliers is discussed. The approach, which uses the distribution of subset log-likelihoods, extends the OCLUST algorithm and uses an iterative approach to detect and trim outliers.
  arXiv  Detail & Related papers  (2023-10-08T21:27:29Z)
• Learning Graphical Factor Models with Riemannian Optimization [70.13748170371889]
  This paper proposes a flexible algorithmic framework for graph learning under low-rank structural constraints. The problem is expressed as penalized maximum likelihood estimation of an elliptical distribution. We leverage geometries of positive definite matrices and positive semi-definite matrices of fixed rank that are well suited to elliptical models.
  arXiv  Detail & Related papers  (2022-10-21T13:19:45Z)
• 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)
• Near optimal sample complexity for matrix and tensor normal models via geodesic convexity [5.191641077435773]
  We show nonasymptotic bounds for the error achieved by the maximum likelihood estimator (MLE) in several natural metrics. In the same regimes as our sample complexity bounds, we show that an iterative procedure to compute the MLE known as the flip-flop algorithm converges linearly with high probability.
  arXiv  Detail & Related papers  (2021-10-14T17:47:00Z)
• A simpler spectral approach for clustering in directed networks [1.52292571922932]
  We show that using the eigenvalue/eigenvector decomposition of the adjacency matrix is simpler than all common methods. We provide numerical evidence for the superiority of the Gaussian Mixture clustering over the widely used k-means algorithm.
  arXiv  Detail & Related papers  (2021-02-05T14:16:45Z)
• 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)
• Understanding Implicit Regularization in Over-Parameterized Single Index Model [55.41685740015095]
  We design regularization-free algorithms for the high-dimensional single index model. We provide theoretical guarantees for the induced implicit regularization phenomenon.
  arXiv  Detail & Related papers  (2020-07-16T13:27:47Z)
• Multi-Objective Matrix Normalization for Fine-grained Visual Recognition [153.49014114484424]
  Bilinear pooling achieves great success in fine-grained visual recognition (FGVC) Recent methods have shown that the matrix power normalization can stabilize the second-order information in bilinear features. We propose an efficient Multi-Objective Matrix Normalization (MOMN) method that can simultaneously normalize a bilinear representation.
  arXiv  Detail & Related papers  (2020-03-30T08:40:35Z)

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.