TITLE:
A Study of Triangle Inequality Violations in Social Network Clustering
AUTHORS:
Sanjit Kumar Saha, Tapashi Gosswami
KEYWORDS:
Clustering; Triangle Inequality Violations, Traditional Clustering, Graph Clustering
JOURNAL NAME:
Journal of Computer and Communications,
Vol.12 No.1,
January
15,
2024
ABSTRACT: Clustering a social network is a process of grouping social actors into clusters where intra-cluster similarities among actors are higher than inter-cluster similarities. Clustering approaches, i.e. , k-medoids or hierarchical, use the distance function to measure the dissimilarities among actors. These distance functions need to fulfill various properties, including the triangle inequality (TI). However, in some cases, the triangle inequality might be violated, impacting the quality of the resulting clusters. With experiments, this paper explains how TI violates while performing traditional clustering techniques: k-medoids, hierarchical, DENGRAPH, and spectral clustering on social networks and how the violation of TI affects the quality of the resulting clusters.