Кластеризация графов является одной из постоянно актуальных задач анализа данных. Существуют различные постановки данной задачи. Рассматривается задача поиска разбиения множества вершин на непересекающиеся подмножества таким образом, чтобы плотность связей между вершинами одного подмножества была выше, чем между вершинами различных подмножеств. Для решения данной задачи применяются различные подходы, многие из которых используют такую апостериорную оценку качества кластеризации, как модулярность. Функционал модулярности, принимая значение из [–1, 1], позволяет в формальном виде оценить качество кластеризации (разбиения на подмножества).

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

Описана жадная алгоритмическая схема кластеризации, а также AMVE (Algorithm based on Modularity Variation Estimation) - простейший жадный алгоритм на ее основе. На тестовом проблемсете произведен сравнительный анализ AMVE с эвристическими алгоритмами кластеризации, реализованными в современных пакетах анализа графов: демонстрируется сравнительное преимущество AMVE как по скорости, так и по качеству кластеризации.

Также приводятся сведения об использовании разработанного программного обеспечения для анализа данных в социологии и литературоведении. В этих исследованиях рассматривались графы, построенные на данных социальных сетей (в качестве ребер использовалось отношение «дружбы» в социальной сети между пользователями). Продемонстрировано небольшое превосходство AMVE по качеству кластеризации по сравнению с известными алгоритмами Louvain и Walktrap.

Мартынов Никита Николаевич, магистрант, Институт математики и информатики, Бурятский государственный университет, Российская Федерация, 670000, Республика Бурятия, г. Улан-Удэ, ул. Смолина, 24а, тел.: (+7914)6368355 e-mail: supercell666@mail.ru

Хандарова Ольга Владимировна, канд. фил. наук, младший научный сотрудник, Институт монголоведения, буддологии и тибетологии СО РАН, Российская Федерация, 670047, Республика Бурятия, Улан-Удэ, ул. Сахьяновой, 6, тел.: (+7924)7731409, e-mail: olga.khandarova@gmail.com

Хандаров Фёдор Владимирович, канд. техн. наук, старший преподаватель,Институт математики и информатики, Бурятский государственный университет, Российская Федерация, 670000, Республика Бурятия, г. Улан-Удэ, ул. Смолина, 24а, тел.: (+7924)4563112, e-mail: fedor.khandarov@gmail.com

1. Бадмацыренов Т. Б., Скворцов М. В., Хандаров Ф. В. Буддийские цифровые практики трансцендентности: VK-сообщество "Хамбо Лама Даши-Доржо Итигэлов"// Мониторинг общественного мнения: экономические и социальные перемены. 2018. № 2. С. 309–332. https://doi.org/10.14515/monitoring.2018.2.18

2. Писатели Бурятии в сети Facebook: литературные репутации в виртуальном пространстве / О. В. Хандарова, Ф. В. Хандаров, Н. Н. Мартынов, М. В. Скворцов // Медиафилософия. 2017. Т. 13. С. 212-226.

3. Fast unfolding of communities in large networks / V. D. Blondel [et al.] //Journal of statistical mechanics: theory and experiment. 2008. Vol. 2008, N 10. P. 10008. https://doi.org/10.1088/1742-5468/2008/10/P10008

4. Csardi G., Nepusz T. The igraph software package for complex network research //InterJournal, Complex Systems. 2006. Vol. 1695, N 5. P. 1-9.

5. Flake G. W., Lawrence S., Giles C. L. Efficient identification of web communities //Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2000. P. 150-160. https://doi.org/10.1145/347090.347121

6. Fortunato S. Community detection in graphs //Physics reports. 2010. Vol. 486, N. 3-5. P. 75-174. https://doi.org/10.1016/j.physrep.2009.11.002

7. Le Martelot E., Hankin C. Fast multi-scale detection of relevant communities in large-scale networks //The Computer Journal. 2013. Vol. 56, N 9. P. 1136-1150. https://doi.org/10.1093/comjnl/bxt002

8. Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters / J. Leskovec, K. J. Lang, A. Dasgupta, M. W. Mahoney //Internet Mathematics. 2009. Vol. 6. N 1. P. 29-123. https://doi.org/10.1080/15427951.2009.10129177

9. Leskovec J., Lang K. J., Mahoney M. Empirical comparison of algorithms for network community detection //Proceedings of the 19th international conference on World wide web. ACM, 2010. P. 631-640. https://doi.org/10.1145/1772690.1772755

10. Maulik U., Bandyopadhyay S. Genetic algorithm-based clustering technique //Pattern recognition. 2000. Vol. 33, N 9. P. 1455-1465. https://doi.org/10.1016/S0031-3203(99)00137-5

11. Newman M. E. J. Detecting community structure in networks //The European Physical Journal B. 2004. Vol. 38, N 2. P. 321-330. https://doi.org/10.1140/epjb/e2004-00124-y

12. Pizzuti C. A multiobjective genetic algorithm to find communities in complex networks // IEEE Transactions on Evolutionary Computation, 2012. Vol. 16, N 3. P. 418-430. https://doi.org/10.1109/TEVC.2011.2161090

13. Pons P., Latapy M. Computing communities in large networks using random walks // Journal of Graph Algorithms and Applications, 2006. Vol. 10, N 2. P. 191–218. https://doi.org/10.1007/11569596_31

14. Defining and identifying communities in networks / F. Radicchi, C. Castellano, F. Cecconi, V. Loreto, D. Parisi //Proceedings of the National Academy of Sciences. 2004. Vol. 101, N 9. P. 2658-2663. https://doi.org/10.1073/pnas.0400054101

15. Raghavan U. N., Albert R., Kumara S. Near linear time algorithm to detect community structures in large-scale networks //Physical review E. 2007. Vol. 76. N 3. P. 036106. https://doi.org/10.1103/PhysRevE.76.036106

16. Reichardt J., Bornholdt S. Statistical mechanics of community detection //Physical Review E. 2006. Vol. 74, N 1. P. 016110. https://doi.org/10.1103/PhysRevE.74.016110