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

Анализ точности актуальных алгоритмов определения сообществ в сетях при работе с графовыми базами данных

Авторы: Казакова Е.Д.¹
Учреждения:
1. Финансовый университет при Правительстве Российской Федерации
Выпуск: Том 10, № 1 (2023)
Страницы: 49-59
Раздел: МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ, ЧИСЛЕННЫЕ МЕТОДЫ И КОМПЛЕКСЫ ПРОГРАММ
URL: https://bakhtiniada.ru/2313-223X/article/view/250552
DOI: https://doi.org/10.33693/2313-223X-2023-10-1-49-59
ID: 250552

Цитировать

Полный текст

Открытый доступ
Доступ закрыт

Доступ предоставлен
Доступ закрыт

Только для подписчиков

Аннотация
Полный текст
Об авторах
Список литературы
Дополнительные файлы
Статистика

Аннотация

В данной работе рассмотрены методы выделения сообществ в сетях с помощью различных алгоритмов. Были представлены алгоритмы Girvan-Newman, Louvain, Walktrap и Leiden, и проанализированы результаты их применения на графе Википедии. Были использованы различные метрики для оценки качества выделенных сообществ, и были сохранены результаты в графовой базе данных Neo4j. Результаты показали, что алгоритмы Лейдена и Лувена с разрешающей способностью равной единице показали наилучшие результаты по сравнению с другими алгоритмами.

Ключевые слова

сетевой анализ, алгоритмы определения сообществ, графовые базы данных

Полный текст

Открыть статью на сайте журнала

Об авторах

Екатерина Даниловна Казакова

Финансовый университет при Правительстве Российской Федерации

Автор, ответственный за переписку.
Email: 191841@edu.fa.ru

студентка бакалавриата факультета информационных технологий и анализа больших данных Финансового университета при Правительстве Российской Федерации

Россия, Москва

Список литературы

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.