Рубрика: 
УДК: 
519.17, 519.237
Язык публикации: 
русский

ПРОГРАММНАЯ РЕАЛИЗАЦИЯ, АНАЛИЗ ЭФФЕКТИВНОСТИ И ОЦЕНКА КАЧЕСТВА АЛГОРИТМОВ КЛАСТЕРИЗАЦИИ ГРАФОВЫХ МОДЕЛЕЙ СОЦИАЛЬНЫХ СЕТЕЙ

Аннотация: 

Рассматривается задача поиска сообществ (кластеров) в неориентированных графах (задача кластеризации). Кластеризация - объединение в группы схожих объектов- является одной из фундаментальных задач в области анализа данных. Список прикладных областей, где она применяется, широк: сегментация изображений, маркетинг, борьба с мошенничеством, прогнозирование, анализ текстов и многие другие. На сегодняшний момент не существует универсального эффективного решения данной задачи. Число методов объединения в группы, максимально похожих друг на друга объектов, довольно велико --- несколько десятков алгоритмов и еще больше их модификаций. В статье описаны алгоритмы решения данной задачи, приведены оценки их асимптотической сложности, традиционные метрики и функционалы качества, необходимые для оценки результатов их работы. Предложен вариант решения проблемы, противоположной проблеме resolution limit, - нахождение мелких относительно всего графа сообществ. Выполнена программная реализация алгоритма Smart Local Moving, который является улучшением известного алгоритма Louvain. Приведено экспериментальное сравнение эффективности рассмотренных алгоритмов для больших разреженных графов, содержащих несколько сотен тысяч вершин и ребер и соответствующих реальным данным сайтов YouTube, Amazon, Live Journal. Сравнительный анализ выполнялся на этих трех <<обезличенных>> наборах данных с заранее известным разделением на сообщества, а также на наборе данных со всей доступной информацией о вершинах (пользователях) из социальной сети Вконтакте. Выполнялось
сравнение друг с другом сообществ, найденных разными алгоритмами на одном и том же наборе данных. Оценивались такие характеристики, как время выполнения алгоритмов, показатели модулярности и нормализованной взаимной информации.

Библиографический список

1. Aggarwal C. C., Charu C., Reddy C. K. Data clustering. Algorithms and applications. N.Y. : CRC Press, 2014. 652 p.
2. 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: 10.1145/331499.331504.
3. 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: 10.1140/epjb/e2004-00124-y.
4. Leskovec J., Rajaraman A., Ullman J. Mining of massive datasets. 2nd ed. Cambridge Univ. Press, 2014. 511 p.
5. Fortunato S. Community detection in graphs // Phys. Rep. 2010. Vol. 486, iss. 3–5. P. 75– 174. DOI: 10.1016/j.physrep.2009.11.002.
6. Информационно-аналитический ресурс, посвященный машинному обучению, распознаванию образов и интеллектуальному анализу данных. URL: http://www.machinelearning.ru (дата обращения: 12.02.2017).
7. 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: 10.1140/epjst/e2010-01179-1.
8. Pons P., Latapy M. Computing communities in large networks using random walks // Computer and Information Sciences – ISCIS 2005. 2005. P. 284–293. DOI: 10.1007/11569596_31.
9. 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:
10.1103/PhysRevE.76.036106.
10. 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: 10.1103/PhysRevE. 70.066111.
11. 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:10.1073/pnas.122653799.
12. 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: 10.1088/1742-5468/2008/10/P10008.
13. 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: 10.1140/epjb/e2013-40829-0.
14. 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).
15. Хайкин C. Нейронные сети : полный курс. М. : ИД «Вильямс», 2006. 1104 с.
16. Fortunato S., Barthelemy M. Resolution limit in community detection // Proc. National Academy of Sciences. 2007. № 104. P. 36–41. DOI: 10.1073/pnas.0605965104. 449
17. 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:10.1103/PhysRevE.84.016114.
18. Stanford Large Network Dataset Collection. URL: https://snap.stanford.edu/data (дата обращения: 25.04.2017).

Краткое содержание (на английском языке): 
Полный текст в формате PDF: