Связность в графах и поиски сообществ в социальных сетях

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

Цели работы:

1. Познакомиться с понятиями «социальный граф» и «граф интересов»;
2. Рассмотреть задачи, которые решает социальный граф;
3. Составить модель графа для определенного человека;
4. Найти связи между интересами человека;

Задачи:

1. Реализовать программу, которая сможет быстро определить существует ли связь между интересами.
2. Найти практическое применение для такого вида разработки.

Определения из теории графов

Граф — это объект, состоящий из конечного множества вершин и множества ребер, где каждое ребро есть подмножество множества вершин мощности 2.

Граф называется связным, если любые две его вершины связаны.

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

Граф интересов — это онлайн представление интересов конкретного человека, полученное на основе его активности в социальных сетях.

Рассмотрим некоторые задачи, которые решаются при помощи социального графа:

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

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

1. Социальный поиск (поиск социальных объектов, основанный на анализе набора связей, в которых находятся искомые объекты);
2. Генерация рекомендаций (важной задачей является поиск точных алгоритмов генерации рекомендаций и предложений пользователям, который так же используется при создании графа интересов на основе социального графа).

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

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

Выявление реальных связей

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

Рассмотрим что же из себя представляет граф интересов и как он взаимодействует с социальным графом. Вершинами графа интересов (рис. 1) являются увлечения личности, ребра графа отображают взаимоотношения между вершинами графа.

Рисунок 1. Граф интересов для конкретного человека

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

• человек-человек (пользователи в социальной сети могут взаимодействовать напрямую)
• человек-интерес (то с чем пользователь взаимодействует с социальной сети)
• интерес-интерес (схожие интересы могут быть взаимосвязаны)

Граф интересов также может быть представлен в виде взвешенного графа, в этом случае вес ребра означает силу взаимосвязи между вершинами. При построении такого графа изначально вводится предположение о том, что взаимосвязи имеют одинаковую силу, например, интерес к литературе и к кино неизвестен, и взаимосвязь двух интересов выводится в виде бесконечно большого числа. Далее, если будет обнаружено, что люди, интересующиеся литературой, ведут себя похожим образом с теми людьми, которые увлекаются просмотром фильмов, то значение веса ребра между вершинами будет уменьшено. Определим взаимосвязь графа интересов и социального графа. Они тесно взаимосвязаны, но это далеко не одно и то же. Граф интересов используется для создания сети интересов людей. Социальные сети, такие как, например ВКонтакте, организованы вокруг друзей человека, то есть вокруг социального графа, сети увлечений созданы вокруг интересов личностей, их графа интересов.

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

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

Рисунок 2. Пример проверки тем на связность для конкретного человека

На рис.2 представлен пример реализации графа интересов и выявления в них связности.

Из проделанной нами работы можно сделать следующие выводы:

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

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