Другие журналы

научное издание МГТУ им. Н.Э. Баумана

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

Издатель ФГБОУ ВПО "МГТУ им. Н.Э. Баумана". Эл № ФС 77 - 48211.  ISSN 1994-0408

Выделение сообществ в социальных графах по множеству признаков с частичной информацией

# 09, сентябрь 2015
DOI: 10.7463/0915.0811704
Файл статьи: 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. 2nd 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 3rd 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).
Поделиться:
 
ПОИСК
 
elibrary crossref ulrichsweb neicon rusycon
 
ЮБИЛЕИ
ФОТОРЕПОРТАЖИ
 
СОБЫТИЯ
 
НОВОСТНАЯ ЛЕНТА



Авторы
Пресс-релизы
Библиотека
Конференции
Выставки
О проекте
Rambler's Top100
Телефон: +7 (915) 336-07-65 (строго: среда; пятница c 11-00 до 17-00)
  RSS
© 2003-2020 «Наука и образование»
Перепечатка материалов журнала без согласования с редакцией запрещена
 Тел.: +7 (915) 336-07-65 (строго: среда; пятница c 11-00 до 17-00)