Теория графов в анализе социальных сетей.
Бабаянц А.С., Покусаев Е.
Кубанский государственный технологический университет (КубГТУ)
Теория графов- гигантский раздел в области дискретной математики, который широко применяется в настоящее время не только в математике, но и других областях человеческой деятельности. Данная теория посвящена изучению графов, множеству точек и множеству линий, которые в конечном итоге отображают связи.
Для социального графа не было придумано пока никакого четкого формального определения. Но можно вывести то, что социальный граф — это такой граф, который характеризуется тем, что имеет одну общую компоненту связности. Она захватывает большинство вершин. Также присутствует такое отношение, как «безмасштабные сети», что показывает распределение на степенях вершин.[1] Не маловажное значение занимает среднее расстояние, у социальных графов такое расстояние крайне мало.
Социальный граф является множеством вершин, представленный в виде участников сети и подмножества связей между ними. Различают два вида связей: «явные», чем представлены друзья, родственники, и «неявные», эти в свою очередь являются очень отдалены от пользователя, например, поклонники одного артиста или певца.
Для анализа социальных сетей используют показатели центральности. В рамках теории графов и сетевого анализа различают меры центральности вершины в графе, которые определяют относительную важность вершины в графе. Центральность по степени определяется как число связей, приходящихся на узел(Рисунок 1). Центральность по близости является показателем, насколько быстро распространяется информация в сети от одного участника к остальным.[2]
Рисунок 1 – Меры центральности.
Посредническая центральность является мерой центральности вершины в графе. Центральность по собственному вектору является мерой важности узла в сети. Она назначает относительные оценки всем узлам в сети на основе принципа, согласно которому подключения к узлам с высокой оценкой вносят больший вклад в оценку рассматриваемого узла, чем равные подключения к узлам с низкой оценкой.
Социальных графы помогают решать задачи идентификации пользователя; социальный поиск; генерация рекомендаций по выбору «друзей», медиа-контента или новостей; выявление «реальных» связей или сбор открытой информации для моделирования графа.
В идентификацию пользователя входит обнаружение профилей, принадлежащих одному человеку, в нескольких социальных сетях. Решение этой задачи позволяет уточнить социальный граф, что может быть полезно в поиск социальных объектов(пользователей, их данных, их записей и т. д.); генерации рекомендаций друзей или любого контента.
Реальные и, в частности, социальные сети обладают уникальной структурой, которая обычно отличает их от случайных математических сетей. Примеры сетей изображены на рисунке 2:
Рисунок 2 – Сложные сети.
При наличии огромного количества связей, высчитывать подобие п уточнять рекомендации помогают как раз такие меры центральности. Находя самые важные схожести у узлов сети, алгоритмы могут эффективнее анализировать данные пользователей социальных сетей.
Подведя итоги, можно сказать, что графы являются не просто удобным представлением взаимодействий объектов в социальных сетях, но и практичным способом для реализации алгоритмов по подбору интересующего людей контента и поиску груп по интересам.
Библиографический список
- Huang Chun Yuan et al “Influence of Local Information on Social Simulations in Small-World Network Models.” J. Artif. Soc. Soc. Simul. 8(2005): n. pag.
- Arroyo, Daniel Ortiz. “Discovering Sets of Key Players in Social Networks.” Computational Social Network Analysis(2010).
- Электронный источник https://online.edu.rane