Н.В. Гринева1, С.С. Михайлова2, А.А. Вилкул3

1–3 Финансовый университет при Правительстве РФ (Москва, Россия)

Постановка проблемы. Кластеризация на практике широко используется для анализа биологических, экономических, дорожных, социальных и многих других сетей. При этом выделить сообщества в графе можно различными способами, основываясь на таких свойствах графа как плотность, модулярность, эксцентриситет точки и т.д. С этим связано многообразие методов кластеризации их видов. Вместе с тем не существует общепринятого алгоритма тестирования и оценки качества работы алгоритмов выделения сообществ графа. Множество научных трудов описывают работу графов на реальных сетях, сравнивая их производительность и точность. Представляется возможным сравнить несколько методов кластеризации с использованием синтетического графа.

Цель. Оценить производительность одних из наиболее популярных алгоритмов кластеризации графовых данных и выбрать оптимальный из них с помощью построения набора синтетических графов Lancichinetti–Fortunato–Radicchi.

Результаты. Определены понятия кластеризации, синтетического графа Lancichinetti–Fortunato–Radicchi, методов кластеризации графовых данных. Подробно исследованы пять методов кластеризации графовых данных, а именно: метод Лувена, метод K-средних, метод спектральной кластеризации, метод распространения меток и метод агломеративной кластеризации. Показан процесс применения методов. Проведен анализ основных метрик качества кластеризации: скорректированный индекс Ранда и нормализированная взаимная информация. При выполнении алгоритмов было зафиксировано время выполнения для анализа производительности и скорости работы. Для решения этих задач был использован язык программирования Python и его пакеты netwokrx, generators.community, sklearn.metrics, numpy, time, sklearn.cluster. Выявлен оптимальный алгоритм для обработки больших графовых данных.

Практическая значимость. Результаты исследования возможностей существующих методов кластеризации и особенностей их работы на конкретных примерах позволяют осуществить выбор из них оптимального для кластеризации большого количества данных.

Гринева Н.В., Михайлова С.С., Вилкул А.А. Сравнительный анализ методов кластеризации для графовых данных // Нейрокомпьютеры: разработка, применение. 2023. T. 25. № 4. С. 32-44. DOI: https://doi.org/10.18127/j19998554-202304-05

1. Driver H.E., Kroeber A.L. Quantitative Expression of Cultural Relationships // University of California Publications in American Archeology and Ethnology. 1932. V. 31. P. 211–256.
2. Доан Д.Х., Жулева С.Ю., Крошилин А.В., Крошилина С.В., Тишкина В.В. Формирование наборов вариантов течения болезни методом нечеткой кластеризации в системах поддержки принятия медицинских решений // Биомедицинская радиоэлектроника. 2017. № 7. С. 60–66.
3. Грос С.А., Онуфриева Т.А. Особенности применения кластеризации в системе мониторинга транспорта // Информационно-измерительные и управляющие системы. 2020. Т. 18. № 2. С. 44–50. DOI 10.18127/j20700814-202002-07.
4. Lancichinetti A., Fortunato S. Community detection algorithms: a comparative analysis // Physical Review E – Statistical, Nonlinear and Soft Matter Physics. 2009. V. 80. № 5. P. 056117. DOI 10.1103/PhysRevE.80.056117.
5. 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. V.2008. № 10. P. 10008. DOI 10.1088/1742-5468/2008/10/P10008.
6. Von Luxburg U. Clustering stability: An overview // Foundations and Trends in Machine Learning. 2010. V. 2. № 3. P. 235–274. DOI 10.1561/2200000008.
7. Von Luxburg U. A tutorial on spectral clustering // Statistics and Computing. 2007. V. 17. № 4. P. 395–416. DOI 10.1007/s11222-007-9033-z.
8. Zhang X.-K., Ren J., Song C., Jia J., Zhang Q. Label propagation algorithm for community detection based on node importance and label influence // Physics Letters A. 2017. V. 381. № . 2017. V. 381. № 3. P. 2691–2698. DOI 10.1016/j.physleta.2017.06.018.
9. Zachary W.W. An Information Flow Model for Conflict and Fission in Small Groups // Journal of Anthropological Research. 1977. V. 33. № 4. P. 452–473. DOI 10.1086/jar.33.4.3629752.
10. Girvan 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. V. 99. № 12. P. 7821–7826. DOI 10.1073/pnas.122653799.
11. Shen H.-W. Community Structure of Complex Networks. Springer Science & Business Media. 2013. DOI 10.1007/978-3-642-31821-4.
12. Vinh N.X., Epps J., Bailey J. Information Theoretic Measures for Clusterings Comparison: Variants, Properties, Normalization and Correction for Chance // Journal of Machine Learning Research. 2010. V. 11. P. 2837–2854.
13. Danon L., Duch, J., Diaz-Guilera A., Arenas A. Comparing community structure identification // Journal of Statistical Mechanics: Theory and Experiment. 2005. №. 9. P. 09008. DOI 10.1088/1742-5468/2005/09/P09008.
14. Strehl A., Ghosh J. Cluster Ensembles – A Knowledge Reuse Framework for Combining Multiple Partitions // Journal of Machine Learning Research. 2002. V. 3. P. 583–617.
15. Rand W.M. Objective criteria for the evaluation of clustering methods // Journal of the American Statistical Association. 1971. V. 66. P. 846–850.
16. Koufos N., Martin B. K-Means & Other Clustering Algorithms: A Quick Intro with Python. 2023.