Geodesic
Fast algorithm of cluster analysis $k$-medoids
Prikladnaâ diskretnaâ matematika, no. 1 (2018), pp. 116-127.

Voir la notice de l'article provenant de la source Math-Net.Ru

The algorithm $k$-medoids (KM) is widely used for clustering graphs. The following modifications of it by adding some procedures have been researched in a computer experiments: CKM=KM+CLARA (Cluster LARge Application), LSKM=KM+L-SPAR (Local SPARsification), BKM=KM+CLARA+L-SPAR, NKM=KM+NH (New Heuristic choosing cluster center), CNKM=NKM+CLARA, LSNKM=NKM+L-SPAR, FKM=NKM+CLARA+L-SPAR. The experiment results show that L-SPAR procedure allows to decrease the average running time for LSKM by 5.3 %, BKM by 6.1 %, LSNKM by 8.1 %, FKM by 8.3 % and to improve the clustering quality by 2 %, 2.1 %, 3 %, 3.3 % respectively. Besides, the number of iterations in NKM is twice more than in KM, but the running time of NKM is an order less than of KM, the running time of CKM is two thirds of the running time of KM, the computer complexity of CNKM linearly depends on the graph size, and the application of CLARA does not diminish it appreciably. NH allows 16 times decreasing the computer complexity of KM without loosing the clustering quality. The experiments were conducted on data arrays that represented graphs of social networks YouTube, Live Journal, and the shop Amazon.
Keywords: fast algorithm of cluster analysis, PAM, Local Graph Sparsification.
Mots-clés : CLARA 
@article{PDM_2018_1_a10,
     author = {I. N. Dmitriev},
     title = {Fast algorithm of cluster analysis $k$-medoids},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {116--127},
     publisher = {mathdoc},
     number = {1},
     year = {2018},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2018_1_a10/}
}
TY  - JOUR
AU  - I. N. Dmitriev
TI  - Fast algorithm of cluster analysis $k$-medoids
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2018
SP  - 116
EP  - 127
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2018_1_a10/
LA  - ru
ID  - PDM_2018_1_a10
ER  - 
%0 Journal Article
%A I. N. Dmitriev
%T Fast algorithm of cluster analysis $k$-medoids
%J Prikladnaâ diskretnaâ matematika
%D 2018
%P 116-127
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2018_1_a10/
%G ru
%F PDM_2018_1_a10
I. N. Dmitriev. Fast algorithm of cluster analysis $k$-medoids. Prikladnaâ diskretnaâ matematika, no. 1 (2018), pp. 116-127. http://geodesic.mathdoc.fr/item/PDM_2018_1_a10/

[1] Fortunato S., “Community detection in graphs”, Physics Reports, 486:3–5 (2010), 75–174 | DOI | MR

[2] Kaufman L., Rousseeuw P. J., Finding Groups in Data: An Introduction to Cluster Analysis, Hoboken, New Jersey, 2005 | MR

[3] Newman M. J., “Modularity and community structure in networks”, Proc. of the National Academy of Sciences of the USA, 103:23 (2006), 8577–8582 | DOI

[4] Satuluri V. M., Scalable Clustering of Modern Networks, Ohio State University, Columbus, OH, USA, 2012

[5] Ovelgönne M., Scalable Algorithms for Community Detection in Very Large Graphs, Karlsruhe, 2011, 146 pp.

[6] Stanford Large Network Dataset Collection, , 2017 http://snap.stanford.edu/data/