Для цитирования:
Ионкин М. С., Огнева М. В. Программная реализация, анализ эффективности и оценка качества алгоритмов кластеризации графовых моделей социальных сетей // Известия Саратовского университета. Новая серия. Серия : Математика. Механика. Информатика. 2017. Т. 17, вып. 4. С. 441-451. DOI: 10.18500/1816-9791-2017-17-4-441-451, EDN: ZXJPOD
Программная реализация, анализ эффективности и оценка качества алгоритмов кластеризации графовых моделей социальных сетей
Рассматривается задача поиска сообществ (кластеров) в неориентированных графах (задача кластеризации). Кластеризация - объединение в группы схожих объектов- является одной из фундаментальных задач в области анализа данных. Список прикладных областей, где она применяется, широк: сегментация изображений, маркетинг, борьба с мошенничеством, прогнозирование, анализ текстов и многие другие. На сегодняшний момент не существует универсального эффективного решения данной задачи. Число методов объединения в группы, максимально похожих друг на друга объектов, довольно велико - несколько десятков алгоритмов и еще больше их модификаций. В статье описаны алгоритмы решения данной задачи, приведены оценки их асимптотической сложности, традиционные метрики и функционалы качества, необходимые для оценки результатов их работы. Предложен вариант решения проблемы, противоположной проблеме resolution limit, - нахождение мелких относительно всего графа сообществ. Выполнена программная реализация алгоритма Smart Local Moving, который является улучшением известного алгоритма Louvain. Приведено экспериментальное сравнение эффективности рассмотренных алгоритмов для больших разреженных графов, содержащих несколько сотен тысяч вершин и ребер и соответствующих реальным данным сайтов YouTube, Amazon, Live Journal. Сравнительный анализ выполнялся на этих трех <<обезличенных>> наборах данных с заранее известным разделением на сообщества, а также на наборе данных со всей доступной информацией о вершинах (пользователях) из социальной сети Вконтакте. Выполнялось сравнение друг с другом сообществ, найденных разными алгоритмами на одном и том же наборе данных. Оценивались такие характеристики, как время выполнения алгоритмов, показатели модулярности и нормализованной взаимной информации.
- Aggarwal C. C., Charu C., Reddy C. K. Data clustering. Algorithms and applications. N.Y. : CRC Press, 2014. 652 p.
- Jain A. K., Murty M. N., Flynn P. J. Data clustering: a review // ACM Computing Surveys. 1999. Vol. 31, iss. 3. P. 264–323. DOI: https://doi.org/10.1145/331499.331504.
- Newman M. E. J. Detecting community structure in networks // The European Physical Journal B – Condensed Matter and Complex Systems. 2004. Vol. 38, iss. 2. P. 321–330. DOI: https://doi.org/10.1140/epjb/e2004-00124-y.
- Leskovec J., Rajaraman A., Ullman J. Mining of massive datasets. 2nd ed. Cambridge Univ. Press, 2014. 511 p.
- Fortunato S. Community detection in graphs // Phys. Rep. 2010. Vol. 486, iss. 3–5. P. 75– 174. DOI: https://doi.org/10.1016/j.physrep.2009.11.002.
- Информационно-аналитический ресурс, посвященный машинному обучению, распознаванию образов и интеллектуальному анализу данных. URL: http://www.machinelearning.ru (дата обращения: 12.02.2017).
- Rosvall M., Axelsson D., Bergstrom C. T. The map equation // The European Physical Journal – Special Topics. 2009. Vol. 178, iss. 1. P. 13–23. DOI: https://doi.org/10.1140/epjst/e2010-01179-1.
- Pons P., Latapy M. Computing communities in large networks using random walks // Computer and Information Sciences – ISCIS 2005. 2005. P. 284–293. DOI: https://doi.org/10.1007/11569596_31.
- Raghavan U. N., Albert R., Kumara S. Near linear time algorithm to detect community structures in large-scale networks // Phys. Rev. E. 2007. Vol. 76, iss. 3. P. 036106. DOI: https://doi.org/10.1103/PhysRevE.76.036106.
- Clauset A., Newman M. E. J., Moore C. Finding community structure in very large networks // Phys. Rev. E. 2004. Vol. 70, iss. 6. P. 066111. DOI: https://doi.org/10.1103/PhysRevE.70.066111.
- Girvan M., Newman M. E. J. Community structure in social and biological networks // Proc. National Academy of Sciences. 2002. Vol. 99, № 12. P. 7821–7826. DOI: https://doi.org/10.1073/pnas.122653799.
- Blondel V. D., Guillaume J., Lambiotte R., Lefebvre E. Fast unfolding of communities in large networks // Journal of Statistical Mechanics : Theory and Experiment. 2008. Vol. 2008, № 10. P. P10008. DOI: https://doi.org/10.1088/1742-5468/2008/10/P10008.
- Waltman L., Eck N. J. A smart local moving algorithm for large–scale modularity–based community detection // The European Physical Journal B. 2013. Vol. 86, iss. 11. P. 471. DOI: https://doi.org/10.1140/epjb/e2013-40829-0.
- Romano S., Bailey J., Nguyen V., Verspoor K. Standardized mutual information for clustering comparisons: one step further in adjustment for chance // Proc. 31st Intern. Conf. on Machine Learning. Beijing, China : PMLR, 2014. Vol. 32, № 2. P. 1143–1151. URL: http://proceedings.mlr.press/v32/romano14.pdf (дата обращения: 25.04.2017).
- Хайкин C. Нейронные сети : полный курс. М. : ИД «Вильямс», 2006. 1104 с.
- Fortunato S., Barthelemy M. Resolution limit in community detection // Proc. National Academy of Sciences. 2007. № 104. P. 36–41. DOI: https://doi.org/10.1073/pnas.0605965104.449
- Traag V. A., Dooren P. V., Nesterov Y. Narrow scope for resolution-limit-free community detection // Phys. Rev. E. 2011. Vol. 84, iss. 1. P. 016114. DOI: https://doi.org/10.1103/PhysRevE.84.016114.
- Stanford Large Network Dataset Collection. URL: https://snap.stanford.edu/data (дата обращения: 25.04.2017).
- 948 просмотров