Википедия

Социальный граф

Социа́льный граф — граф, узлы которого представлены социальными объектами, такими как пользовательские профили с различными атрибутами (например: имя, день рождения, родной город), сообщества, медиаконтента и так далее, а рёбра — социальными связями между ними[1][2].

Неявный социа́льный граф — это такой граф, который можно сформировать (вывести, вычислить) на основе взаимодействий пользователя со своими «друзьями» и группами «друзей» в социальной сети. В этом гра́фе в отличие от обычного социального графа нет явного указания «друзей», то есть нет явных социальных связей[3].

Показаны в каких отношениях состоят разные социальные объекты. Пользователь Ева находится в дружеских отношениях с пользователями Адам и Кейт, при этом Адам и Кейт не являются друзьями друг другу, но у них есть общий друг Ева. Фотография Питера была оценена многими пользователями, в том числе она понравилась и Еве. Также Ева слушает радио с Last.fm и смотрит видео с Youtube.

Особенности социального графа характеризуются такими метриками, как: метрики взаимоотношений[⇨], метрики связей[⇨] и сегментации[⇨]. Для решения задач на социальном графе используются специальные модели, с помощью которых можно заменить «реальные» графы[⇨]. С помощью социальных графов решают такие задачи, как: идентификация пользователей[⇨]; социальный поиск[⇨]; генерация рекомендаций по выбору «друзей», медиаконтента, новостей и тому подобного[⇨]; выявление «реальных» связей[⇨] или сбор открытой информации[⇨] для моделирования графа. Обработка данных социальных графов связана с рядом проблем[⇨], как например различия социальных сетей[⇨], закрытость социальных данных[⇨].

Метрики править

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

Взаимоотношения править

Метрики взаимоотношений отображают характер взаимоотношений одного социального объекта с другими социальными объектами.

Гомофилия[4] — степень, в которой пользователь образует связи с подобными. Сходство может быть определено по полу, возрасту, общественному положению, образовательному уровню и так далее[5].

Множественность — число «множественных» связей, в которых находятся пользователи[6]. Например, два пользователя, которые дружат и работают вместе, будут иметь «множественность», равную 2[7]. «Множественность» связывают с «силой связи».

Взаимность — степень, в которой пользователи взаимодействуют между собой, отвечают взаимностью на действия друг друга[8]. Сетевая закрытость — степень, в которой друзья пользователя являются друзьями друг другу. Также её называют «мерой полноты реляционных триад[англ.]». Предположение того, что пользователь находится в сетевой закрытости, называется транзитивностью. [9]. Соседство — тенденция пользователей иметь большое количество связей с географически близкими пользователями[8].

Связи править

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

Мост — пользователь, чьи слабые связи заполняют «структурные дыры», обеспечивающий единственную связь между другими пользователями или кластерами(группами пользователей). Также через него будет проходить кратчайший маршрут[10].

Центральность — степень, которая показывает «важность» или «влияние» определённого пользователя (кластера пользователей) внутри графа[11][12]. Стандартные методы измерения центральности — центральность по посредничеству[англ.], центральность по близости[англ.], центральность собственного вектора[англ.], альфа-центральность[англ.] и центральность по степени[англ.][13].

Плотность — доля прямых связей в сети по отношению к общему числу возможных[14][15]. Расстояние — минимальное количество связей, требуемых для установления наличия взаимосвязи между двумя отдельными пользователями. Структурные дыры — отсутствие связей между двумя частями сети.

Сила связи определяется линейной комбинацией времени, близости и взаимности[10], чем больше значение силы связи, тем она сильнее. Сильные связи определяются «гомофилией», «соседством» или «транзитивностью», в то время как слабые связи определяются «мостами».

Сегментация править

Метрики сегментации отображают характеристики социального графа, поделенного на сегменты, которые имеют отличительные особенности.

Клика — группа, в которой все пользователи имеют «прямые» связи (вершины связаны (соединены) ребром) друг к другу[16]. Социальный круг — группа, в которой не обязательны «прямые» связи между пользователями[17].

Коэффициент кластеризации — степень вероятности того, что два разных пользователя, связанные с конкретным индивидуумом, тоже связаны. Высокий коэффициент кластеризации указывает на высокую замкнутость группы, другими словами, группа может быть «кликой».

Сплочённость — степень, в которой пользователи связаны между собой одной, общей связью, образуя социальную сплочённость. Структурная сплочённость — указывает на такую единую структуру группы, что удаление небольшого количества пользователей ведёт к разрыву группы[16].

Модели править

 
Модели социальных графов[18]

Некоторые общеизвестные модели графов могут заменить «реальные» социальный графы[18].

Функционально-управляемые модели нацелены на воспроизведение статистических характеристик графа, таких как степенное распределение и динамические изменения плотности графа, среди таковых модель Барабаши — Альберт и модель «горящий лес».

Намеренно-управляемые модели сфокусированы на эмуляцию процесса создания оригинального графа, к данному классу моделей относятся случайный обход и случайные блуждания, модель ближайшего соседа.

Структурно-управляемые модели охватывают статистические данные из структуры графа, позволяя соответствующему генератору воспроизводить случайные графы с теми же структурными ограничениями, среди таких моделей — графы Кронекера, dK-графы.

Задачи править

Идентификация пользователей — обнаружение профилей, принадлежащих одному человеку, в нескольких социальных сетях[19]. Решение этой задачи позволяет получить более полный социальный граф, что может быть полезно во многих задачах, таких как социальный поиск и генерация рекомендаций.

Поиск социальных объектов (пользователей, их данных, их записей и так далее), основанный на анализе набора связей, в которых находятся искомые объекты[20].

Важной задачей является поиск точных алгоритмов генерации рекомендаций и предложений пользователям, который так же используется при создании графа интересов на основе социального графа. Это могут быть рекомендация друзей (пользователи редко делят свои контакты на социальные группы, но тем не менее они неявно делят эти контакты на кластеры, через их взаимодействия в рамках социальной сети[21]), рекомендации содержимого (рекомендации медиаконтента, сообществ, новостей и так далее[22][уточнить ссылку]). Существуют традиционные подходы в области рекомендательных систем[23][уточнить ссылку]:

  • коллаборативная фильтрация[24] — заключается в формировании списка рекомендованных объектов на основе мнений пользователей, ведущих себя похожим образом;
  • фильтрация содержимого — основывается на характеристиках предмета и известной о нём информации.
  • социальные подходы — отталкиваются от социальных связей пользователей.

Отдельная задача связана с применением подхода «разведки на основе открытых источников» для выявления истинных связей между пользователями, то есть настоящих друзей, родственников и так далее[25].

Сбор информации править

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

Для оценивания задачи ставятся следующие критерии[26]:

  • эффективность: насколько быстро обнаруживаются узлы и связи в результате сканирования,
  • чувствительность: как разные социальные сети и количество защищённых и закрытых пользователей («чёрной дыры») влияют на обход,
  • отклонение: насколько сильно отличаются статистические свойства подграфов, полученных при обходе, от свойств исходного графа.

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

Из-за закрытости социальных данных, можно пропустить большую часть социальных графа, разные алгоритмы обходов влияют на таких пользователей по-разному. Кроме того, разные социальные сети обладают различными уникальными свойствами, даже если предоставляют аналогичные услуги, что также усложняет задачу сбора информации.

Проблемы править

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

Основной проблемой генерации рекомендаций является проблема холодного старта — расчёт рекомендации для новых социальных объектов (пользователей, постов, медиаконтента и так далее)[28][уточнить ссылку].

Главная проблема сбора данных для социального графа заключается в закрытости социальных сетей[29]. Во-первых, трудно получить социальный граф от «поставщиков»[30] из-за ценности и защищенности законом социальных данных. Во-вторых, большой трудностью является сбор миллионов списков контактов, профилей, фотографий, видео и тому подобного содержимого парсерами. Многие «поставщики» социальных сетей используют одностраничную модель или множество динамических страниц, содержащих Ajax и DHTML, что также создаёт очень много проблем для создания гибкого парсера.

Примечания править

  1. ↑ Задача идентификации пользователей в социальных сетях, 2012, pp. 3.
  2. ↑ Социальный поиск, 2010, pp. 199.
  3. ↑ Suggesting Friends, 2010, pp. 2.
  4. ↑ Понятие гомофилия, 2012, pp. 168—169.
  5. ↑ Гомофилия, 2001, pp. 415—444.
  6. ↑ Множественность, 1997, pp. 673—693.
  7. ↑ Пример множественности, 2003.
  8. ↑ 1 2 Понимание социальных графов, 2012.
  9. ↑ Транзитивность, 2010, pp. 855—869.
  10. ↑ 1 2 Сила связей, 1973, pp. 1360—1380.
  11. ↑ Центральность, 2010, p. 32.
  12. ↑ Метрики для базового сетевого анализа, 2011, pp. 364—367.
  13. ↑ Центральность вершин, 2010, pp. 245.
  14. ↑ Анализ социальных сетей, 2006, pp. B-11—B-12.
  15. ↑ Социальные сети: техники и приложения, 2010, pp. 25.
  16. ↑ 1 2 Клика в анализе социальных сетей, 2011, pp. 149.
  17. ↑ Метрики для базового сетевого анализа, 2011, pp. 346—347.
  18. ↑ 1 2 Social Graph Models, 2010, pp. 3—4.
  19. ↑ Задача идентификации пользователей в социальных сетях, 2012, pp. 2—4.
  20. ↑ Социальный поиск, 2010, pp. 431.
  21. ↑ Suggesting Friends, 2010, pp. 2—7.
  22. ↑ Рекомендации треков в социальных сетях, 2012, p. 34.
  23. ↑ Подходы к рекомендациям, 2012, pp. 8—13.
  24. ↑ Рекомендательные системы на основе коллаборативной фильтрации, 2002, с. 187.
  25. ↑ OSINT, 2012, pp. 21—39.
  26. ↑ Crawling OSN, 2010, pp. 1—7.
  27. ↑ Проблемы задачи идентификации пользователей, 2012, pp. 13—17.
  28. ↑ Проблема холодного старта, 2012, pp. 5—11.
  29. ↑ Crawling OSN, 2010, pp. 1.
  30. ↑ Crawling OSN, 2010, pp. 3.

Литература править

  • M. Granovetter. The strength of weak ties (англ.). — American Journal of Sociology, 1973.
  • Melville P., Mooney R., Nagarajan R. Content-Boosted Collaborative Filtering for Improved Recommendations (англ.) // University of Texas, USA : Материалы конф. / AAAI-02, Austin, TX, USA, 2002. — 2002. — P. 187—192.
  • J.M. Podolny, J.N. Baron. Resources and relationships: Social networks and mobility in the workplace (англ.). — American Sociological Review, 1997. (недоступная ссылка)
  • N. McPherson, L. Smith-Lovin, J.M. Cook. Birds of a feather: Homophily in social networks (англ.). — Annual Reviews, Annual Review of Sociology, 2001.
  • M. Kilduff, W. Tsai. Social networks and organisations (англ.). — Sage Publications, 2003. — P. 172.
  • C. Kadushin. Social Network Analysis. — Headquarters, Department of the Army, Washington, DC, 2006. — ISBN 978-1-84787-395-8.
  • A.-K. Pietiläinen, E. Oliver, J. LeBrun. MobiClique: Middleware for Mobile Social Networking (англ.). — WOSN’09, August 17, 2009, Barcelona, Spain, 2009. (недоступная ссылка)
  • Xu, Guandong et al. Web Mining and Social Networking: Techniques and Applications. — Springer, 2010. — ISBN 978-1-4419-7734-2.
  • Shaozhi Ye, Juan Lang, Felix Wu. Crawling Online Social Graphs (англ.). — APWEB’12, April 6-8, 2010, Busan, Korea, 2010. (недоступная ссылка)
Источник — https://ru.wikipedia.org/w/index.php?title=Социальный_граф&oldid=116839686