Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This study conducts a theoretical analysis of partitional clustering on networks, focusing on both hard and soft assignment schemes with various objective functions. It reveals that while Sum of Squares Clustering (SSC) and Fuzzy C-Means (FCM) can achieve optimal cluster centers along edges, P-Median (PMP) and Probabilistic Distance Clustering (PDC) are constrained to vertex placements. The analysis uncovers critical structural properties, such as assignment bottleneck points, which inform the design of more efficient clustering algorithms applicable to diverse fields like facility location and network design.
Clustering on networks isn't just about vertices—optimal centers can lie along edges, reshaping our understanding of network-based clustering methods.
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.