Geodesic
Implementation, efficiency analysis and quality evaluation of clustering algorithms for graph models of social networks
Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, Tome 17 (2017) no. 4, pp. 441-451

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

The article deals with the community detection problem (the clustering problem) for undirected graphs. The clustering (grouping together of similar objects) is one of the fundamental tasks in the data analysis. This task is applied in a wide range of areas: image segmentation, marketing, anti-fraud, forecasting, text analysis and much more. At the moment, there is no universal and effective solution of this problem. There are several dozens of methods and there are many modifications of them which group objects that are as similar as possible to each other. The article describes algorithms for solving this task, presents their asymptotic complexity estimates, traditional metrics and quality functionals needed to evaluate the results of their work. The authors propose a solution to the problem which is the opposite of the resolution limit problem (algorithms find communities that are quite small in relation to the entire graph). The authors implemented the Smart Local Moving algorithm which is an improvement of the well-known Louvain algorithm. Performed an experimental comparison of the considered algorithms efficiency on large sparse graphs containing several hundreds of thousands of vertices and edges which corresponding to real data from YouTube, Amazon, Live Journal. The comparative analysis was performed on these three “impersonal” data sets with a previously known division into communities (ground-truth communities), as well as on a data set with all available information about the vertices (users) from the social network “Vkontakte”. The communities found by different algorithms on the same data set were also compared with each other. The authors examined such characteristics as the execution time of algorithms, values of modularity and normalized mutual information. 
@article{ISU_2017_17_4_a6,
     author = {M. S. Ionkin and M. V. Ogneva},
     title = {Implementation, efficiency analysis and quality evaluation of clustering algorithms for graph models of social networks},
     journal = {Izvestiya of Saratov University. Mathematics. Mechanics. Informatics},
     pages = {441--451},
     publisher = {mathdoc},
     volume = {17},
     number = {4},
     year = {2017},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ISU_2017_17_4_a6/}
}
TY  - JOUR
AU  - M. S. Ionkin
AU  - M. V. Ogneva
TI  - Implementation, efficiency analysis and quality evaluation of clustering algorithms for graph models of social networks
JO  - Izvestiya of Saratov University. Mathematics. Mechanics. Informatics
PY  - 2017
SP  - 441
EP  - 451
VL  - 17
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/ISU_2017_17_4_a6/
LA  - ru
ID  - ISU_2017_17_4_a6
ER  - 
%0 Journal Article
%A M. S. Ionkin
%A M. V. Ogneva
%T Implementation, efficiency analysis and quality evaluation of clustering algorithms for graph models of social networks
%J Izvestiya of Saratov University. Mathematics. Mechanics. Informatics
%D 2017
%P 441-451
%V 17
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/ISU_2017_17_4_a6/
%G ru
%F ISU_2017_17_4_a6
M. S. Ionkin; M. V. Ogneva. Implementation, efficiency analysis and quality evaluation of clustering algorithms for graph models of social networks. Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, Tome 17 (2017) no. 4, pp. 441-451. http://geodesic.mathdoc.fr/item/ISU_2017_17_4_a6/