A Foundational Perspective for Partitional Clustering on Networks

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.

Optimization and Control (math.OC); Machine Learning (cs.LG)

arXiv:2607.25144 [math.OC]

(or arXiv:2607.25144v1 [math.OC] for this version)

https://doi.org/10.48550/arXiv.2607.25144 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.