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

На данной анимации показаны в каких отношениях состоят разные социальные объекты. Пользователь Ева находится в дружеских отношениях с пользователями Адам и Кейт, при этом Адам и Кейт не являются друзьями друг другу, но у них есть общий друг Ева. Фотография Питера была оценена многими пользователями, в том числе она понравилась и Еве. Так же Ева слушает радио с 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) нацелены на воспроизведение статистических характеристик графа, таких как степенное распределение и динамические изменения плотности графа.

• Модель Барабаси — Альберта
• Модель «Горящий лес» (Forest Fire)

Намеренно-управляемые модели (англ. 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, что создает очень много проблем для создания гибкого парсера.

См. также

• Social network analysis
• Random graph

• Глоссарий теории графов
• Коллаборативная фильтрация
• Мир тесен

Примечания

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

Литература

• 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. — С. 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. — С. 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

• D. Hansen, B. Shneiderman, M. A. Smith Analyzing Social Media Networks with NodeXL. — Morgan Kaufmann, 2010. — С. 283. — ISBN 978-0-12-382229-1

• Shaozhi Ye, Juan Lang, Felix Wu Crawling Online Social Graphs (англ.). — APWEB’12, April 6-8, 2010, Busan, Korea, 2010.

• C. McCarthy Facebook: One Social Graph to Rule Them All? (англ.). — CBS Interactive Inc., 2010.

• T. Opsahl, F. Agneessens, J. Skvoretz Node centrality in weighted networks: Generalizing degree and shortest paths (англ.). — Social Networks, 2010.

• M. Roth, A. Ben-David, D. Deutscher Suggesting Friends Using the Implicit Social Graph (англ.). — KDD’10, July 25–28, 2010, Washington, DC, USA., 2010.

• A. Sala, L. Cao, C. Wilson, R. Zablit, H. Zheng, B. Y. Zhao Measurement-calibrated Graph Models for Social Network Experiments (англ.). — WWW 2010, April 26–30, 2010, Raleigh, North Carolina, USA, 2010.

• D. Horowitz, Sepandar D. Kamvar The Anatomy of a Large-ScaleSocialSearch Engine (англ.). — WWW 2010, April 26–30, 2010, Raleigh, North Carolina, USA., 2010.

• F.J. Flynn, R.E. Reagans, L. Guillory Do you two know each other? Transitivity, homophily, and the need for (network) closure. (англ.). — Journal of Personality and Social Psychology, 2010.

• J. Ugander, B. Karrer, L. Backstrom, C. Marlow The Anatomy of the Facebook Social Graph (англ.). — Cornell University Library, 2011.

• My T. Thai, Panos M. Pardalos Handbook of Optimization in Complex Networks: Communication and Social Networks. — Springer, 2011. — С. 541. — ISBN 978-1-4614-0856-7

• P. J. Carrington, J. Scott The Sage Handbook of Social Network Analysis. — SAGE, 2011. — С. 640. — ISBN 978-1-84787-395-8

• D. Schioberg, F. Schneider, H. Schioberg, S. Schmid, S. Uhlig, Anja Feldmann Tracing the Birth of an OSN: Graph and Profile Analysis in Google+ (англ.). — WebSci 2012, June 22–24, 2012, Evanston, Illinois, USA, 2012.

• M. P. Zillman Online Social Networks (англ.). — Virtual Private Library, 2012.

• B. R. Holland Enabling Open Source Intelligence (OSINT) in private social networks (англ.) : Masters's dessertation. — Iowa State University, Ames, Iowa, 2012.

• C. Kadushin Understanding social networks: Theories, concepts, and findings. — Oxford: Oxford University Press, 2012. — С. 288.

• В.М. Сазанов Социальные сети как новая общественная сфера. Системный анализ и прогноз.. — М.: Лаборатория СВМ, 2010. — С. 180.

• С. Бартуков, А. Коршунов Идентификация пользователей социальных сетей в Интернет на основе социальных связей (рус.). — Институт системного программирования Российской академии наук, 2012.

• А.А. Дзюба Рекомендации треков в социальных сетях (рус.) : Магистерская диссертация. — Санкт-Петербургский Государственный Университет, 2012.

• Н. В. Богатырь Укоренённость и за её пределами: воздействие сетей (рус.). — Международная конференция «Укоренённость и за её пределами: объясняют ли социологические теории экономическую реальность?» Октябрь 25–28, 2012, Москва, Россия, 2012. — С. 168-169.