НАУКА и ОБРАЗОВАНИЕ

Файл статьи: SE-BMSTU...o199.pdf (727.69Кб)

УДК 519.178; 51-77

1 Россия,  МГТУ им. Н.Э. Баумана

В статье предложен новый алгоритм для выделения сообществ в социальных графах, который использует не только информацию о структуре графа, но и информацию о вершинах. Рассматривается граф ближайшего окружения пользователя, т. е. его друзья без него самого, при этом у каждой вершины есть набор признаков — сведения о месте работы, учебы и т. п. Задача состоит в том, чтобы определить отсутствующие или неуказанные признаки вершин по признакам соседей и по этим признакам выделить сообщества в социальном графе. Считается, что две вершины принадлежат одному сообществу, если у них есть общий признак. Выдвинута гипотеза о том, что если большая часть соседей некоторой вершины имеет общий признак, то и вершина с большой вероятностью имеет этот же признак. Предложенный алгоритм - итеративный, который на каждом шаге обновляет признаки вершины по признакам соседей согласно гипотезе. Доля соседей, которые образуют большую часть, задается параметром алгоритма. Время работы одной итерации линейно зависит от числа ребер в графе.
Для оценки качества кластеризации выбраны три нормированные метрики — ожидаемая плотность, индекс силуэтов и гамма-статистика Хуберта. Описан метод получения тестовой выборки из 2000 графов пользователей социальной сети Вконтакте: сбор осуществлялся путем запросов к API ВКонтакте и сбора HTML-страниц профилей пользователей и поисковой выдачи. В качестве признаков были взяты сведения о членстве в группах, среднем и высшем образовании и местах работы пользователей. Для хранения использована СУБД PostgreSQL, для обработки данные сохранялись в формат gexf. Для тестовой выборки получена оценка метрик для различных значений параметра: значение индекса силуэтов низкое (0.14-0.20), но в пределах нормы; значение ожидаемой плотности высокое - 1.17-1.52; значение Гамма-статистики близко к максимуму — 0.94-0.95. Вычислено количество вершин без признаков до и после применения алгоритма. До применения их было две трети, после работы алгоритма их количество снизилось до 25-64% в зависимости от значения параметра алгоритма. Предложенный алгоритм может быть использован для кластеризации социальных графов, однако его стоит доработать для выделения пересекающихся сообществ.

1. Fortunato S. Community detection in graphs // Physics Reports. 2010. Vol. 486, no. 3-5. P. 75-174. DOI: 10.1016/j.physrep.2009.11.002
2. Mucha P.J., Richardson T., Macon K., Porter M.A., Onnela J.P Community structure in time-dependent, multiscale, and multiplex networks // Science. 2010. Vol. 328, no. 5980. P. 876-878. DOI: 10.1126/science.1184819
3. Newman M.E.J., Girvan M. Finding and evaluating community structure in networks // Physical Review E. 2004. Vol. 69. Art. no. 026113. DOI: 10.1103/PhysRevE.69.026113
4. Schaeffer S.E. Graph clustering // Computer Science Review. 2007. Vol. 1, no. 1. P. 27-64. DOI: 10.1016/j.cosrev.2007.05.001
5. Scott J. Social network analysis: A handbook. 2^nd ed. London: SAGE, 2000.
6. Blei D.M., Ng A.Y., Jordan M.I. Latent Dirichlet Allocation // Journal of Machine Learning Research. 2003. Vol. 3, P. 993-1022.
7. Mislove A., Viswanath B., Gummadi K.P., Druschel P. You are who you know: inferring user profiles in online social networks // Proceedings of the 3^rd ACM International Conference on Web Search and Data Mining, New York, NY, USA, February 03--06, 2010. New York: ACM, 2010. 452~p. P. 251-260. DOI: 10.1145/1718487.1718519
8. Dougnon R., Fournier-Viger P., Nkambou R. Inferring User Profiles in Online Social Networks Using a Partial Social Graph // Advances in Artificial Intelligence / ed. by D. Barbosa, E. Milios. Springer International Publishing, 2015. P. 84-99. DOI: 10.1007/978-3-319-18356-5_8 (Ser. Lecture Notes in Computer Science; vol. 9091).
9. Yang J., McAuley J.J., Leskovec J. Community Detection in Networks with Node Attributes // 2013 IEEE 13th International Conference on Data Mining (ICDM). IEEE Publ., 2013. P. 1151-1156. DOI: 10.1109/ICDM.2013.167
10. Mcauley J., Leskovec J. Discovering Social Circles in Ego Networks // ACM Transactions on Knowledge Discovery from Data. 2014. Vol. 8, no. 1. Art. no. 4. DOI: 10.1145/2556612
11. Granovetter M. The Strength of Weak Ties // American Journal of Sociology. 1973. Vol. 78, no. 6. P. 1360-1380.
12. Stein B., zu Eissen S.M., Wi ßbrock F. On Cluster Validity and the Information Need of Users // Proceedings of the 3rd IASTED International Conference on Artificial Intelligence and Applications (AIA). Benalmadena, Spain, September 8-10, 2003. ACTA Press, 2003. P. 216-221.
13. Rousseeuw P.J. Silhouettes: A graphical aid to the interpretation and validation of cluster analysis // Journal of Computational and Applied Mathematics. 1987. Vol. 20. P. 53-65. DOI: 10.1016/0377-0427(87)90125-7
14. Zaki M.J., Meira Jr. W. Data Mining and Analysis: Fundamental Concepts and Algorithms. Cambridge University Press, 2014. 562 p.
15. Ключарёв П.Г., Чесноков В.О. Исследование спектральных свойств социального графа сети LiveJournal // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2013. № 9. С. 391-400. DOI:10.7463/0913.0603441
16. Gephi — the Open Graph Viz Platform: webcite. Режим доступа: http://gephi.github.io/ (дата обращения 20.09.2015).