研究网络聚类中中心点位置对结果的影响，发现部分模型天然偏向顶点。
A Foundational Perspective for Partitional Clustering on Networks
- 允许聚类中心位于边而非仅限顶点，拓展传统聚类思路
- 软聚类方法（SSC/FCM）可得边上的最优中心，硬聚类（PMP/PDC）则倾向顶点
- 为网络聚类算法设计提供理论依据，适合图学习与信息检索研究者
本研究从理论角度分析网络上的分部聚类问题，考察了硬分配与软分配两种方案下不同目标函数的表现。聚类中心不再局限于顶点，也可位于边上。研究涵盖四种关键模型：硬分配下的P-Median（PMP）与最小平方聚类（SSC），以及软分配下的概率距离聚类（PDC）与模糊C均值（FCM）。通过数学分析，揭示了各模型的结构性差异，如分配瓶颈点的重要性，以及顶点受限解在决定最优中心中的作用。结果表明，尽管SSC和FCM可在边上获得最优中心，但PMP和PDC本质上更倾向于将中心置于顶点，从而揭示了网络聚类行为的本质特征。这些发现为高效算法设计提供了新方向，对设施选址、网络设计及现代检索系统中嵌入图的聚类具有重要启示。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。