Analysis of the Modern Algorithms’ Accuracy for Communities Identification on Networks when Working with Graph Databases
- Autores: Kazakova E.D.1
-
Afiliações:
- Financial University under the Government of the Russian Federation
- Edição: Volume 10, Nº 1 (2023)
- Páginas: 49-59
- Seção: 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
Citar
Acesso aberto
Acesso está concedido
Resumo
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.
Palavras-chave
Texto integral
Sobre autores
Ekaterina Kazakova
Financial University under the Government of the Russian Federation
Autor responsável pela correspondência
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
Rússia, MoscowBibliografia
- 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.
Arquivos suplementares
Arquivos suplementares
Ação
1.
JATS XML
2.
Fig. 1. Example of the simple graph
Baixar (21KB)
3.
Fig. 2. Graph retained from the networkx
Baixar (250KB)
4.
Fig. 3. Complete database
Baixar (171KB)
5.
Fig. 4. Node centrality graph
Baixar (51KB)
6.
Fig. 5. Identification of communities by the Girvan-Newman algorithm
Baixar (236KB)
7.
Fig. 6. Identification of communities by the Louvain algorithm
Baixar (230KB)
8.
Fig. 7. Identification of communities by the Leiden algorithm
Baixar (233KB)
9.
Fig. 8. Identification of communities by the Walktrap algorithm
Baixar (227KB)
10.
Algorithm quality metrics
Baixar (542KB)
11.
Fig. 9. Friedman rank test
Baixar (48KB)
12.
Fig. 10. Similarity matrix for random walk and Leiden algorithms
Baixar (37KB)
