Analysis of the Modern Algorithms’ Accuracy for Communities Identification on Networks when Working with Graph Databases

Ekaterina D. Kazakova; Казакова Екатерина Даниловна

doi:10.33693/2313-223X-2023-10-1-49-59

Analysis of the Modern Algorithms’ Accuracy for Communities Identification on Networks when Working with Graph Databases

Авторлар: Kazakova E.D.¹
Мекемелер:
1. Financial University under the Government of the Russian Federation
Шығарылым: Том 10, № 1 (2023)
Беттер: 49-59
Бөлім: MATHEMATICAL MODELING, NUMERICAL METHODS AND COMPLEX PROGRAMS
URL: https://journals.eco-vector.com/2313-223X/article/view/545838
DOI: https://doi.org/10.33693/2313-223X-2023-10-1-49-59
ID: 545838

Дәйексөз келтіру

Толық мәтін

Ашық рұқсат
Рұқсат жабық

Рұқсат берілді
Рұқсат жабық

Тек жазылушылар үшін

Аннотация
Толық мәтін
Авторлар туралы
Әдебиет тізімі
Қосымша файлдар
Статистика

Аннотация

In this paper, we consider methods for extracting communities in networksusing various algorithms. The Girvan-Newman, Louvain, Walktrap and Leiden algorithms were presented and the results of their application on the Wikipedia graph were analyzed. Various metrics were used to assess the quality of the isolated communities, and the results were stored in the Neo4j graph database. The results showed that the Leiden and Louvain algorithms with a resolution equal to one showed the best results compared to other algorithms.

Негізгі сөздер

network analysis, community detection algorithms, graph databases

Толық мәтін

Авторлар туралы

Ekaterina Kazakova

Financial University under the Government of the Russian Federation

Хат алмасуға жауапты Автор.
Email: 191841@edu.fa.ru

student at the Faculty of Information Technology and Big Data Analysis of the Financial University under the Government of the Russian Federation

Ресей, Moscow

Әдебиет тізімі

Barabasi A.-L., Albert R. Emergence of scaling in Random networks. Science. 1999. No. 286. Pp. 509–512. doi: 10.1126/science.286.5439.509.
Blondel V.D., Guillaume J.-L., Lambiotte R., Lefebvre E. Fast unfolding of communities in large networks. Journal of Statistical Mechanics Theory and Experiment. 2008. doi: 10.1088/1742-5468/2008/10/P10008.
Bruna J., Li Xiang. Community detection with graph neural networks. 2017.
Circulo library. URL: http://lab41.github.io/Circulo/
Clauset A., Newman M.E.J., Moore C. Finding community structure in very large networks. Physical Review E. 2004. URL: http:// arxiv.org/abs/cond-mat/0408187
Coscia M., Rossetti G., Giannotti F., Pedreschi D. Demon: A local-first discovery method for overlapping communities. KDD. 2012. URL: http://www. michelecoscia.com/wp-content/uploads/2012/08/cosciakdd12.pdf
Blondel V.D., Guillaume J.-L., Lambiotte R., Lefebvre E. Fast unfolding of communities in large networks. J. Stat. Mech. 2008. URL: http://arxiv.org/abs/0803.0476
Fortunato S. Community detection in graphs. Physics Reports. 2009. URL: http://arxiv.org/abs/0906.0612
Girvan M., Newman M.E.J. Community structure in social and biological networks. Proceedings of the National Academy of Sciences. 2001. URL: http://arxiv.org/abs/cond-mat/0112110
Gregory S. An algorithm to find overlapping community structure in networks. Proceeding PKDD 2007 Proceedings of the 11th European Conference on Principles and Practice of Knowledge Discovery in Databases. 2007. URL: http://www.cs.bris.ac.uk/Publications/Papers/2000689.pdf
Girvan M., Newman M.G.M., Newman M.E.J. Community structure in social and biological networks. Proceedings of the National Academy of Sciences of the United States of America. 2002. No. 99. Pp. 7821–7826. doi: 10.1073/pnas.122653799.
Hamilton W.L., Ying R., Leskovec J. Representation learning on graphs: Methods and applications. 2017.
Nikhil M., Carin L., Rai P. Stochastic block models meet graph neural networks. 2019.
Pons P., Latapy M. Computing communities in large networks using random walks. J. Graph Algorithms Appl. 2006. No. 10. Pp. 191–218. doi: 10.7155/jgaa.00124.