Implementation, efficiency analysis and quality evaluation of clustering algorithms for graph models of social networks

M. S. Ionkin ; M. V. Ogneva

Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, Tome 17 (2017) no. 4, pp. 441-451.

Résumé

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.

Bibliographie

[1] Aggarwal C. C., Charu C., Reddy C. K., Data clustering. Algorithms and applications, CRC Press, N. Y., 2014, 652 pp. | MR | Zbl

[2] Jain A. K., Murty M. N., Flynn P. J., “Data clustering: a review”, ACM Computing Surveys, 31:3 (1999), 264–323 | DOI

[3] Newman M. E. J., “Detecting community structure in networks”, The European Physical Journal B — Condensed Matter and Complex Systems, 38:2 (2004), 321–330 | DOI

[4] Leskovec J., Rajaraman A., Ullman J., Mining of massive datasets, 2nd ed., Cambridge Univ. Press, 2014, 511 pp. | MR

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

[6] Information and analytical resource dedicated to machine learning, pattern recognition and intelligent data analysis (in Russian) (accessed 12 February, 2017)

[7] Rosvall M., Axelsson D., Bergstrom C. T., “The map equation”, The European Physical Journal — Special Topics, 178:1 (2009), 13–23 | DOI

[8] Pons P., Latapy M., “Computing communities in large networks using random walks”, Computer and Information Sciences, ISCIS 2005, 2005, 284–293 | DOI | MR

[9] Raghavan U. N., Albert R., Kumara S., “Near linear time algorithm to detect community structures in large-scale networks”, Phys. Rev. E, 76:3 (2007), 036106 | DOI

[10] Clauset A., Newman M. E. J., Moore C., “Finding community structure in very large networks”, Phys. Rev. E, 70:6 (2004), 066111 | DOI | MR

[11] Girvan M., Newman M. E. J., “Community structure in social and biological networks”, Proc. National Academy of Sciences, 99:12 (2002), 7821–7826 | DOI | MR | Zbl

[12] Blondel V. D., Guillaume J., Lambiotte R., Lefebvre E., “Fast unfolding of communities in large networks”, Journal of Statistical Mechanics : Theory and Experiment, 2008:10 (2008), P10008 | DOI

[13] Waltman L., Eck N. J., “A smart local moving algorithm for large-scale modularity-based community detection”, The European Physical Journal B, 86:11 (2013), 471 | DOI

[14] Romano S., Bailey J., Nguyen V., Verspoor K., “Standardized mutual information for clustering comparisons: one step further in adjustment for chance”, Proc. 31st Intern. Conf. on Machine Learning (Beijing, China, 2014), PMLR, 32, no. 2, 2014, 1143–1151 (accessed 25 April, 2017) http://proceedings.mlr.press/v32/romano14.pdf

[15] Haykin S., Neural Networks: A Comprehensive Foundation, Pearson Education (Singapore) Pte Ltd., Singapore, 1998, 842 pp.

[16] Fortunato S., Barthelemy M., “Resolution limit in community detection”, Proc. National Academy of Sciences, 104 (2007), 36–41 | DOI | MR

[17] Traag V. A., Dooren P. V., Nesterov Y., “Narrow scope for resolution-limit-free community detection”, Phys. Rev. E, 84:1 (2011), 016114 | DOI

[18] Stanford Large Network Dataset Collection, (accessed 25 April, 2017) https://snap.stanford.edu/data