A Study of Triangle Inequality Violations in Social Network Clustering  

作　　者：Sanjit Kumar Saha Tapashi Gosswami Sanjit Kumar Saha;Tapashi Gosswami(Department of Computer Science and Engineering, Jahangirnagar University, Dhaka, Bangladesh;Brandenburg University of Technology Cottbus-Senftenberg, Cottbus, Germany)

机构地区：[1]Department of Computer Science and Engineering, Jahangirnagar University, Dhaka, Bangladesh [2]Brandenburg University of Technology Cottbus-Senftenberg, Cottbus, Germany

出　　处：《Journal of Computer and Communications》2024年第1期67-76,共10页电脑和通信（英文）

摘　　要：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.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.

关 键 词：CLUSTERING Triangle Inequality Violations Traditional Clustering Graph Clustering 

分 类 号：O17[理学—数学]