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.
References
[1]
Elkan, C. (2003) Using the Triangle Inequality to Accelerate k-Means, In: Proceedings of the Twentieth International Conference on International Conference on Machine Learning (ICML’03). AAAI Press, Washington DC, 147-153.
[2]
Kryszkiewicz, M. and Lasek, P. (2010) TI-DBSCAN: Clustering with DBSCAN by Means of the Triangle Inequality, In: Szczuka, M., Kryszkiewicz, M., Ramanna, S., Jensen, R., Hu, Q., Eds., RSCTC 2010, LNCS, Vol. 6086, Springer, Heidelberg, 60-69. https://doi.org/10.1007/978-3-642-13529-3_8
[3]
Kaufman, L. and Rousseeuw, P.J. (1990) Finding Groups in Data: An Introduction to Cluster Analysis. John Wiley & Sons, New York. https://doi.org/10.1002/9780470316801
[4]
Jain, A. and Dubes, R. (1988) Algorithms for Clustering Data. Prentice-Hall, Englewood Cliffs, NJ.
[5]
Falkowski, T., Barth, A. and Spiliopoulou, M. (2007) DENGRAPH: A Density-Based Community Detection Algorithm. IEEE/WIC/ACM International Conference on Web Intelligence (WI’07), Fremont, CA, 2-5 November 2007, 112-115. https://doi.org/10.1109/WI.2007.74
[6]
von Luxburg, U. (2007) A Tutorial on Spectral Clustering. Statistics and Computing, 17, 395-416. https://doi.org/10.1007/s11222-007-9033-z
[7]
Fruchterman, T.M.J. and Reingold, E.M. (1991) Graph Drawing by Force-Directed Placement. Software: Practice and Experience, 21, 1129-1164. https://doi.org/10.1002/spe.4380211102