Анализ динамических характеристик целевых групп социальных сетей

Ипатов Юрий Аркадьевич кандидат технических наук доцент, кафедра информатики, Поволжский государственный технологический университет 424000, Россия, Республика Марий Эл, г. Йошкар-Ола, пл. Ленина, 3 Ipatov Yurii Arkad'evich PhD in Technical Science Associate Professor of the Department of Informatics at the Volga State University of Technology 424000, Russia, Mari El, Yoshkar-Ola, pl. Lenina, d. 3 philsilver@mail.ru Другие публикации этого автора

Калагин Иван Владимирович студент, кафедра ИиСП, Поволжский государственный технологический университет 424000, Россия, Республика Марий Эл, г. Йошкар-Ола, пл. Ленина, 3 Kalagin Ivan Vladimirovich Student, Department of Сomputer Science and System Programming, Volga State University of Technology 424000, Russia, Respublika Marii El, g. Ioshkar-Ola, pl. Lenina, 3 lulldev@yandex.ru

Разработка ведется в рамках гранта Президента РФ для государственной поддержки молодых ученых МК-7290.2015.9.

Развитие информационных технологий незаметно меняют и трансформируют способы коммуникации людей в современном мире. Ключевым механизмом в этой среде является понятие социальной сети. Этот объект наблюдения активно изучается и исследуется с зарождающейся науке о сетях ^[1,2]. Среди других объектов анализа схожей природы здесь можно назвать технологические сети (сеть компьютеров, вычислителей), информационные сети (веб страницы, ссылки научных статей и литературы), биологические сети (экосети, нейросети и др.) ^[3]. Комплексное изучение сетевых объектов позволяет решать большое количество принципиально важных задач. Например, анализ распространите вирусов как информационных, так и биологических, что позволяет выявить динамику их распространения. Какие изменения топологии сети необходимо сделать, чтобы минимизировать распространите эпидемии ^[4]. Устойчивость критически важных объектов сетевой инфраструктуры при техногенных катастрофах или целенаправленном воздействии, например, сети связи, электрификация, транспортно-логистические системы и др. ^[5]. Вот лишь краткий перечень прикладных исследований, где применяются последние достижения в области больших данных и моделировании сложных систем.

В изучении современных социальных сетей необходимо учитывать разносторонние аспекты их функционирования и специфики. Это в свою очередь, позволит построить эффективные методы в изучении поставленных задач. В связи с этим, выделяют следующие подходы в изучении: ресурсный, структурно-функциональный, нормативный и динамический ^[6,7].

В структурно-функциональном подходе изучается топология сети, где вершины графа рассматриваются как отдельные объекты (пользователи), а уровень их взаимоотношений, как разные веса ребер в этом графе ^[8-10]. Ключевыми особенностями в изучении данного подхода могут быть пространственная топология вершин графа, то есть их взаимное расположение. Также здесь можно выделить показатель центральности^[11], который служит количественной мерой числа связей объекта с другими объектами. Максимальный показатель центральности характеризует наиболее влиятельных объектов социальной сети. Также в данном подходе анализа графов следует выделить свойство транзитивности. Для которого характерно следующее отношение, если , где - набор вершин графа G и при этом , то . Иными словами, отношение транзитивности в графе создает избыточные связи, которые повышает его устойчивость и повышает скорость распространения информации. Использование структурно-функционального подхода в моделировании социальных графов и интерпретация результатов задействует теорию сетевого обмена и структурную теорию ^[12,13].

В ресурсном подходе анализа социальных сетей, рассматривается фактическая и потенциальная возможность пользователей, уникальным образом созданных или собранных в едином месте ресурсов в широком понимании для каких-либо целей и задач. Разделени­е пользователей и их группировка, происходит по количественным показателям ресурсов, например, сила структурной позиции участника ^[14]. Примерами уникальных персональных ресурсов могут быть место жительства, степень умений и знаний, уровень материальных и нематериальных активов, пол. Характерными сетевыми ресурсами могут быть статус, степень влияния, размер и качество информации ^[15]. Это направление анализа, является ключевым в с точки зрения анализа содержания социальных сетей, а также создания интеллектуальных систем автоматического извлечения контента^[16] и анализа больших объемов данных на их основе^[17].

Для изучения нормативного подхода центральным понятием является уровень доверия между пользователями социального окружения, а также правила и нормы, регулирующие их взаимоотношения. Уровень доверия может градуироваться по нескольким относительным степеням, и быть интерпретирован, как ребро в графе. Например, «высокий» он характерен для отношений внутри семейных или родственных связей, «средний» может быть между друзьями или знакомыми, «умеренный» или «сдержанный» встречается в деловых связях и бизнес среде. Интеграция персональных и сетевых ресурсов пользователей с учетом существующих правил и норм для данной социальной сети, может рассматриваться как уникальная характеристика, под названием «сетевой капитал». Это принципиально новая категория нематериального актива, позволяющая достичь с большей вероятностью поставленную цель или задачу ^[18,19].

Динамический подход направлен на изучение социальной сети, где основным объектом исследований являются изменения с течением времени в структурно-функциональных элементах рассматриваемого графа. Важными характеристиками в наблюдаемых переменах связаны с привлечением пользователей и исчезновением существовавших участников, созданием новых и удалением старых связей ^{[20, 21]}. Порождающие преобразования ставят вопросы, связанные с краткосрочными и долгосрочными изменениями и по каким законам они могут быть рассчитаны. Так задача прогнозирования уровня формирования связей в социальной группе, является одной из ключевых. Здесь может быть задействована информация о структурной составляющей рассматриваемого графа, а также специфические особенности различных его вершин. Для этого необходимо синтезировать реляционные и структурно-функциональные модели ^[22].

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

Анализ больших социальных сетей – это сложная и ресурсоемкая задача, однако для достижения этой цели, исследователи стараются уменьшить размерность данных посредствам различных подходов. Так можно исследовать отдельные сообщества, группируемые по различным признакам, задействовать механизм разреза графа или его аппроксимации ^[24,25]. В большинстве случаев исследуются отдельные группы пользователей социальных сетей (микроуровень), где по не линейным закономерностям их функционирования делается обобщение на графы большей размерности (мезоуровень, макроуровень) ^[26,27]. Рассмотрим некоторые фундаментальные эксперименты анализа социальных сетей.

Грановеттер доказывает, что для большого числа социальных проблем, таких как карьерный рост, новые источники информации или ценные данные, слабые связи оказываются в большей степени эффективнее сильных ^[27,28]. Данный эффект получил название силой слабых связей. Ребру графа соответствует определенное значение «силы» связи между участниками, которое может быть рассчитано, как комбинация линейной характеристики, зависящей от длительности, эмоциональной окраски и значимости взаимных услуг.

Один из хорошо известных примеров анализа социальных сетей, проведенных Милгрэмом и Трэверсом в 70-х годах ХХ века, называется «феномен малого мира», или «теория шести рукопожатий». Предположение заключается в том, что каждый отдельно взятый человек знаком с любым другим через цепочку знакомых, в среднем не превышают шести человек ^[29]. Этот феномен позволил провести, множество научных экспериментов в масштабах разного числа людей на планете и доказать свою состоятельность. Также были созданы компьютерные игры, пьесы и фильмы на основании этой гипотезы.

Рис. 1. Гистограмма средней степени разделения для заданного количества пользователе Facebook.

Последние исследования, проведенные самой большой социальной сеть в мире Facebook (рис. 1), показывают, что данном феномене неуклонно уменьшается значение самого числа ^[30]. Это можно объяснить тем, что уровень глобализации непрерывно растет и расширяет горизонтальные связи в социуме.

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

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

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

Для графовых моделей социальных сетей характерны количественные оценки следующих типов ^[31-33]. Коэффициент плотности определятся, как отношение всех ребер графа к числу ребер полно связного графа. Также существуют показатели количества путей заданной длины, где под путем понимается последовательность вершин, соединённых между собой. Показатель минимального числа ребер, удаление которых влечет за собой разбиение графа на несколько подграфов. Величина центральности может быть вычислена несколькими способами, поэтому имеет различные подходы её вычисления. В сводной таблице приведены различные её названия и краткое описание характеристик, а также на рис.2 визуализированы особенности каждого вида центральности.

Таблица

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

Иногда полезно разделить вершины в социальном графе на два типа: авторитетные страницы (authorities), которые соответствуют запросу, имеющие больший удельный вес среди страниц данной тематики, т.е. большее число страниц ссылаются на данную страницу. А также хаб страницы (hubs) или интеграторы, содержащие ссылки на лучшие авторитетные страницы (authorities). Авторитетные страницы по интересующей тематике могут содержать не только большое число входных ссылок на внешние источники, но и что не менее важно, пересекаться между собой. Этот механизм обеспечивается интеграторами, которые содержат ссылки, например, на несколько авторитетных страниц по интересующей тематике. Это в свою очередь позволяет вычислить показатель «authority & hub» страницы, для которого можно удовлетворить поиск по прямому запросу и его синонимам в социальной сети по тематически связанным страницам.

Рис.2. Виды центральности для одного графа.

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

Другим центральным понятием в анализе социальной сети является то, насколько вершины сходны между собой. Мера эквивалентности (Similarity measure) может быть рассчитана на свойстве эквивалентности вершин, по заданным свойствам, например: интересы, образование, лайки и другие характеристики пользователей. Выделяют структурную и регулярную эквивалентность. Также существуют показатели сходства между группой вершин: максимальная эквивалентность по всем вершинам группы (single-linkage clustering), минимальная эквивалентность no всем вершинам группы (complete-linkage clustering) и усредненная эквивалентность no группе (average-linkage clustering).

Модели динамики сети. В изучении эволюционных характеристик социальной сети используются различные системные подходы^[34]. Так анализ фундаментальных работ направленных на исследование динамических характеристик социальной сети показывает, что число ребер возрастает по линейному закону с появлением новых вершин. В то время, как плотность графа изменятся по полиномиальной закономерности. Известны следующие модели, которые позволяют изучать эволюцию социальной сети:

- гравитационная модель сети (GM) ^[35].

- экспоненциальные модели случайных графов (ERGM, STERGM) ^[36];

- стохастические акторно-ориентированные модели (SAOM) ^[37].

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

В экспоненциальных моделях случайных графов существуют механизмы, которые могут ответить на вопрос о предпосылках возникновения сети и её эволюции. Эволюция и формирование такой сети рассматривается как дискретный случайный процесс. Основная задача анализа в изучении таких систем состоит в выявлении причинно-следственных связей породивших изменение.

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

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

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

Приложение Socialev представляет собой клиентский интерфейс, работающий в браузере, которое извлекает данные из социальной сети посредством Open API ^[38] социальной сети Vk.com. Процесс работы от начала запуска программы имеет неопределенную длительность - то есть мониторинг может происходить сколь угодное время. В процессе работы программа совершает фиксацию добавления пользователей в определенные сообщества, ведет журнал активности каждого пользователя по факту его добавления в сферу исследования, визуализирует процесс эволюции сети с помощью интерактивного графа в реальном времени.

Рис.3. Главная страница интерфейса приложения Socialev

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

Рис. 4. Процесс сбора охвата после запуска мониторинга. Выведены результирующие таблицы, в которые будут помещаться данные

Для показательной работы приложения было выбрано исследование активности пользователей группы (сообщества) Хабрахабр (http://vk.com/habr) и сфера интернет-магазина Aliexpress, в которые вошли 5 самых крупных по количеству пользователей группы vk.com:

1. Официальное сообщество “AliExpress.com по-русски” (2 000 000 пользователей)
2. Группа “Смотри, что я нашел на AliExpress” (754 000 пользователей)
3. Группа “Зацени, что я нашел на AliExpress” (1 950 000 пользователей)
4. Группа “Смотри, что я нашел на AliExpress” (940 000 пользователей)
5. Группа “AliExpress – Горящие товары, скидки до 90%” (429 000 пользователей)

Исследование проводилось в будний день и длительность процесса мониторинга составила 6 часов. В процессе исследования было выявлено 4 факта добавления в сообщества указанной сферы.

Рис. 5. Начало мониторинга. Страница с интерактивным графом.

Четыре пользователя (по два на группу) в течении исследования вступили в группы “Смотри, что я нашел на AliExpress” и “Зацени, что я нашел на AliExpress”.

Рис. 6. Окончания исследования. Результат в интерактивном графе.

Рис. 7. Окончания исследования. Результат в таблицах.

Данный метод анализа эволюции графа позволяет проводить разнообразные исследования с целевой аудиторией, позволяет вычислять активность пользователей на основе вступления в сообщества и строить предположения и прогнозы на основе данных мониторинга. Разработанный программный инструментарий может быть полезным для дальнейшего развития и исследования тематик: визуализации социальных графов в реальном времени ^[23,39,40], управления и влияния в социальной сети на целевые аудитории ^[14,41,42], процесс быстрого сбора данных для анализа из социальных сетей ^[9,43] и др.

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