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

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

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

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

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

Содержание

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

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

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

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

  • Гомофилия [5] (англ. Homophily) — степень, в которой пользователь образует связи с подобными. Сходство может быть определено по полу, возрасту, социальному положению, образовательному уровню и т. д. [6]
  • Множественность (англ. Multiplexity) — число «множественных» связей, в которых находятся пользователи. [7] Например, два пользователя, которые дружат и работают вместе, будут иметь «множественность» равную 2. [8] «Множественность» связывают с «силой связи».
  • Взаимность (англ. Mutuality/Reciprocity) — степень, в которой пользователи взаимодействуют между собой, отвечают взаимностью на действия друг друга. [9]
  • Сетевая закрытость (англ. Network Closure) — степень, в которой друзья пользователя являются друзьями друг другу. Так же ее называют «мерой полноты реляционных триад». Предположение того, что пользователь находится в сетевой закрытости называется транзитивностью. [10]
  • Соседство (англ. Propinquity) — тенденция пользователей иметь большое количество связей с географически близкими пользователями. [9]

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

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

  • Мост (англ. Bridge) — пользователь, чьи слабые связи заполняют «структурные дыры», обеспечивающий единственную связь между другими пользователями или кластерами(группами пользователей). Так же через него будет проходить кратчайший маршрут. [11]
  • Центральность (англ. Centrality) — степень, которая показывает «важность» или «влияние» определенного пользователя (кластера пользователей) внутри графа. [12][13]
Стандартные методы измерения «центральности» включают в себя центральность по посредничеству, центральность по близости, центральность собственного вектора, альфа центральность и центральность по степени. [14]
  • Плотность (англ. Density) — доля прямых связей в сети, по отношению к общему числу возможных. [15][16]
  • Расстояние (англ. Distance) — минимальное количество связей, требуемых для установления наличия взаимосвязи между двумя отдельными пользователями.
  • Структурные дыры (англ. Structural holes) — отсутствие связей между двумя частями сети.
  • Сила связи (англ. Tie Strength) определяется линейной комбинацией времени, «близости» и «взаимности».[11] Чем больше значение силы связи тем она сильнее. Сильные связи определяются «гомофилией», «соседством» или «транзитивностью», в то время как слабые связи определяются «мостами».

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

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

  • Клика (англ. Cliques) — группа, в которой все пользователи имеют «прямые» связи (вершины связаны (соединены) ребром) друг к другу. [17]
  • Социальный круг (англ. Social circles) — группа, в которой не обязательны «прямые» связи между пользователями. [18]
  • Коэффициент кластеризации (англ. Clustering coefficient) — степень вероятности того, что два разных пользователя, связанные с конкретным индивидуумом, тоже связаны. Высокий коэффициент кластеризации указывает на высокую замкнутость группы, другими словами группа может быть «кликой».
  • Сплоченность (англ. Cohesion) — степень, в которой пользователи связаны между собой одной, общей связью, образуя социальную сплочённость. Структурная сплочённость — указывает на такую единую структуру группы, что удаление небольшого количества пользователей ведёт к разрыву группы. [17]

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

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

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

Функционально-управляемые модели (англ. Feature-driven Models) нацелены на воспроизведение статистических характеристик графа, таких как степенное распределение и динамические изменения плотности графа.

Намеренно-управляемые модели (англ. Intent-driven Models) сфокусированы на эмуляцию процесса создания оригинального графа.

  • Случайный обход/прогулка (Random Walk)
  • Ближайший сосед (Nearest Neighbor)

Структурно-управляемые модели (англ. Structure-driven Models) охватывают статистические данные из структуры графа, позволяя соответствующему генератору воспроизводить случайные графы с теми же структурными ограничениями.

  • Графы Кронекра (Kronecker graphs)
  • dK-графы (dK-graphs)

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

Идентификация пользователей [править]

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

  1. Социальный поиск
  2. Генерация рекомендаций

Социальный поиск [править]

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

Генерация рекомендаций [править]

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

  • Рекомендация друзей — пользователи редко делят свои контакты на социальные группы, но, тем не менее, они неявно делят эти контакты на кластеры, через их взаимодействия в рамках социальной сети. [21]
  • Рекомендации контента — рекомендации медиа-контента, сообществ, новостей и т. п. [22]

Подходы к рекомендациям

Существуют традиционные подходы в области рекомендательных систем [22]:

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

Выявление «настоящих» связей [править]

Применение подхода «разведки на основе открытых источников» (англ. Open source intelligence, OSINT) для выявления истинных связей между пользователями, то есть настоящих друзей, родственников и т. п. [24]

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

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

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

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

При обходе оценивают следующие факторы:

  • Выбор узлов: узлы являются отправной точкой обхода. Важно выбрать правильные узлы и порядок обхода очередей, чтобы избежать низкого качества страницы,
  • Алгоритмы выбора узлов: алгоритмы решают, какой узел выбрать следущим. Часто используемые алгоритмы:
  1. поиск в ширину
  2. жадные алгоритмы
  • Защищенные пользователи: из-за закрытости социальных данных, можно пропустить большую часть социальных графа. Разные алгоритмы обходов влияют на таких пользователей по-разному,
  • Разные социальные сети: они имеют свои уникальные свойства, даже если они предоставляют аналогичные услуги.

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

Различия социальных сетей [править]

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

Генерация рекомендаций [править]

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

Закрытость социальных данных [править]

Главная проблема сбора данных для социального графа заключается в закрытости социальных сетей. [26]

Во-первых, трудно получить социальный граф от «провайдеров»[27] из-за ценности и защищенности законом социальных данных.

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

См. также [править]

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

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

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


Источник — «http://ru.wikipedia.org/w/index.php?title=Социальный_граф&oldid=55391246»