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

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

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

Метрики

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

Взаимоотношения

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

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

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

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

Связи

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

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

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

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

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

Сегментация

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

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

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

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

Модели

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

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

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

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

Задачи

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

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

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

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

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

Сбор информации

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

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

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

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

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

Проблемы

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

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

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

Примечания

Литература

• M. Granovetter . (англ.) . — American Journal of Sociology, 1973.
• Melville P., Mooney R., Nagarajan R. (англ.) // University of Texas, USA : Материалы конф. / AAAI-02, Austin, TX, USA, 2002. — 2002. — P. 187—192 .
• J.M. Podolny, J.N. Baron. (англ.) . — American Sociological Review, 1997. (недоступная ссылка)
• N. McPherson, L. Smith-Lovin, J.M. Cook. (англ.) . — Annual Reviews, Annual Review of Sociology, 2001.
• M. Kilduff, W. Tsai. (англ.) . — Sage Publications, 2003. — P. 172 .
• C. Kadushin. . — Headquarters, Department of the Army, Washington, DC, 2006. — ISBN 978-1-84787-395-8 .
• A.-K. Pietiläinen, E. Oliver, J. LeBrun. (англ.) . — WOSN’09, August 17, 2009, Barcelona, Spain, 2009. (недоступная ссылка)
• Xu, Guandong et al. . — Springer, 2010. — ISBN 978-1-4419-7734-2 .

• D. Hansen, B. Shneiderman, M. A. Smith. . — Morgan Kaufmann, 2010. — С. 283. — ISBN 978-0-12-382229-1 .

• Shaozhi Ye, Juan Lang, Felix Wu. (англ.) . — APWEB’12, April 6-8, 2010, Busan, Korea, 2010. (недоступная ссылка)

• C. McCarthy. (англ.) . — CBS Interactive Inc., 2010.
• T. Opsahl, F. Agneessens, J. Skvoretz. (англ.) . — Social Networks, 2010. 26 февраля 2018 года.

• M. Roth, A. Ben-David, D. Deutscher. (англ.) . — KDD’10, July 25–28, 2010, Washington, DC, USA., 2010. (недоступная ссылка)

• A. Sala, L. Cao, C. Wilson, R. Zablit, H. Zheng, B. Y. Zhao. (англ.) . — WWW 2010, April 26–30, 2010, Raleigh, North Carolina, USA, 2010.

• D. Horowitz, Sepandar D. Kamvar. (англ.) . — WWW 2010, April 26–30, 2010, Raleigh, North Carolina, USA., 2010.
• F.J. Flynn, R.E. Reagans, L. Guillory. (англ.) . — Journal of Personality and Social Psychology, 2010. 4 марта 2016 года.
• J. Ugander, B. Karrer, L. Backstrom, C. Marlow. (англ.) . — Cornell University Library, 2011.
• My T. Thai, Panos M. Pardalos. . — Springer, 2011. — С. 541. — ISBN 978-1-4614-0856-7 .
• P. J. Carrington, J. Scott. . — SAGE, 2011. — С. 640. — ISBN 978-1-84787-395-8 .

• D. Schioberg, F. Schneider, H. Schioberg, S. Schmid, S. Uhlig, Anja Feldmann. (англ.) . — WebSci 2012, June 22–24, 2012, Evanston, Illinois, USA, 2012.
• M. P. Zillman. (англ.) . — Virtual Private Library, 2012.
• B. R. Holland. (англ.) : Masters's dessertation. — Iowa State University, Ames, Iowa, 2012. (недоступная ссылка)
• C. Kadushin. . — Oxford: Oxford University Press, 2012. — С. 288.
• В. М. Сазанов. . — М. : Лаборатория СВМ, 2010. — С. 180.
• С. Бартунов, А. Коршунов. (рус.) . — Институт системного программирования Российской академии наук, 2012. 22 января 2016 года.
• Н. В. Богатырь. (рус.) . — Международная конференция «Укоренённость и за её пределами: объясняют ли социологические теории экономическую реальность?» Октябрь 25–28, 2012, Москва, Россия, 2012. — С. 168—169 . 26 февраля 2013 года.

Для улучшения этой статьи желательно : Исправить статью согласно стилистическим правилам Википедии . Проверить достоверность указанной в статье информации. На странице обсуждения должны быть пояснения. После исправления проблемы исключите её из списка. Удалите шаблон, если устранены все недостатки.