A Foundational Perspective for Partitional Clustering on Networks

• URL: http://arxiv.org/abs/2607.25144v1
• Date: Mon, 27 Jul 2026 23:42:20 GMT
• Title: A Foundational Perspective for Partitional Clustering on Networks
• Abstract summary: This study presents a theoretical analysis of partitional clustering on networks.<n>We examine four key models: P-Median (PMP) and Sum of Squares Clustering (SSC) under hard assignment, and Probabilistic Distance Clustering (PDC) and Fuzzy C-Means (FCM) under soft assignment.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This study presents a theoretical analysis of partitional clustering on networks, analyzing both hard and soft assignment schemes with different objective functions. Cluster centers are not restricted to vertices but can also be located along the edges. We examine four key models: P-Median (PMP) and Sum of Squares Clustering (SSC) under hard assignment, and Probabilistic Distance Clustering (PDC) and Fuzzy C-Means (FCM) under soft assignment. Through mathematical analysis, we uncover structural properties that differentiate these models, such as the significance of assignment bottleneck points and the role of vertex-restricted solutions in determining optimal cluster centers. Our findings reveal that, while SSC and FCM can yield optimal centers along edges, PMP and PDC inherently favor vertex placement, leading to insights into clustering behavior on networks. These insights offer new directions for designing efficient algorithms and have implications ranging from facility location and network design to clustering on the embedding graphs that power similarity search in modern retrieval systems.

Related papers

• When Fireflies Cluster; Enhancing Automatic Clustering via Centroid-Guided Firefly Optimization [2.929391519312015]
  This work presents a novel variant of the Firefly Algorithm (FA) for data clustering.<n>It addresses limitations of traditional methods like K-Means that struggle with non-uniform cluster shapes, densities, and the need for pre-defining the number of clusters.<n>Experiments show improved clustering quality and reduced intra-cluster path distances compared to K-Means.
  arXiv  Detail & Related papers  (2026-05-18T14:22:13Z)
• A Holistic Method for Superquadric Fitting Using Unsupervised Clustering Analysis [10.759776164959208]
  We present a novel method for fitting superquadrics to point clouds under the contamination of noise and outliers.<n>Our method redefines the problem from a new unsupervised clustering perspective.<n>We provide a theoretical certificate of convergence analysis and demonstrate that the clustering-inspired fitting method can escape local minima.
  arXiv  Detail & Related papers  (2026-05-16T03:20:33Z)
• MacNet: An End-to-End Manifold-Constrained Adaptive Clustering Network for Interpretable Whole Slide Image Classification [9.952997875404634]
  Clustering-based approaches can provide explainable decision-making process but suffer from high dimension features and semantically ambiguous centroids.<n>We propose an end-to-end MIL framework that integrates Grassmann re-embedding and manifold adaptive clustering.<n> Experiments on multicentre WSI datasets demonstrate that: 1) our cluster-incorporated model achieves superior performance in both grading accuracy and interpretability; 2) end-to-end learning refines better feature representations and it requires acceptable resources.
  arXiv  Detail & Related papers  (2026-02-16T06:43:36Z)
• Deep Incomplete Multi-View Clustering via Hierarchical Imputation and Alignment [15.396375506151102]
  We propose a novel deep IMVC framework that integrates hierarchical imputation and alignment with four key components.<n> Experiments on benchmarks demonstrate that our framework achieves superior performance under varying levels of missingness.
  arXiv  Detail & Related papers  (2026-01-14T00:46:00Z)
• 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)
• Fuzzy K-Means Clustering without Cluster Centroids [21.256564324236333]
  Fuzzy K-Means clustering is a critical technique in unsupervised data analysis. This paper proposes a novel Fuzzy textitK-Means clustering algorithm that entirely eliminates the reliance on cluster centroids.
  arXiv  Detail & Related papers  (2024-04-07T12:25:03Z)
• 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)
• Multi-View Clustering via Semi-non-negative Tensor Factorization [120.87318230985653]
  We develop a novel multi-view clustering based on semi-non-negative tensor factorization (Semi-NTF) Our model directly considers the between-view relationship and exploits the between-view complementary information. In addition, we provide an optimization algorithm for the proposed method and prove mathematically that the algorithm always converges to the stationary KKT point.
  arXiv  Detail & Related papers  (2023-03-29T14:54:19Z)
• Local Sample-weighted Multiple Kernel Clustering with Consensus Discriminative Graph [73.68184322526338]
  Multiple kernel clustering (MKC) is committed to achieving optimal information fusion from a set of base kernels. This paper proposes a novel local sample-weighted multiple kernel clustering model. Experimental results demonstrate that our LSWMKC possesses better local manifold representation and outperforms existing kernel or graph-based clustering algo-rithms.
  arXiv  Detail & Related papers  (2022-07-05T05:00:38Z)
• A Modular Framework for Centrality and Clustering in Complex Networks [0.6423239719448168]
  In this paper, we study two important such network analysis techniques, namely, centrality and clustering. An information-flow based model is adopted for clustering, which itself builds upon an information theoretic measure for computing centrality. Our clustering naturally inherits the flexibility to accommodate edge directionality, as well as different interpretations and interplay between edge weights and node degrees.
  arXiv  Detail & Related papers  (2021-11-23T03:01:29Z)
• 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)
• Learning to Cluster Faces via Confidence and Connectivity Estimation [136.5291151775236]
  We propose a fully learnable clustering framework without requiring a large number of overlapped subgraphs. Our method significantly improves clustering accuracy and thus performance of the recognition models trained on top, yet it is an order of magnitude more efficient than existing supervised methods.
  arXiv  Detail & Related papers  (2020-04-01T13:39: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.