A method to identify expert users in social networks

Luneva Elena PhD in Technical Science Associate Professor, Department of Information Technology, National Research Tomsk Polytechnic University 634050, Russia, g. Tomsk, ul. Pr. Lenina, 30 lee@tpu.ru Efremov Aleksandr Senior Lecturer, Department of Automation and Robotics, National Research Tomsk Polytechnic University 634050, Russia, Tomskaya oblast', g. Tomsk, ul. Lenina, 30 alexyefremov@tpu.ru

Banokin Pavel Assistant, Department of Information Technologies, National Research Tomsk Polytechnic University 634050, Russia, Tomskaya oblast', g. Tomsk, ul. Pr. Lenina, 30 banokin@tpu.ru

Введение

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

Задача поиска влиятельных пользователей социальной сети получила название KPP‑POS (Key Players Problem Positive) ^[1]. Основным подходом к ее решению считается использование дистанционных методов теории графов, учитывающих длины путей между вершинами социального графа. При этом, среди эффективных методов решения данной задачи можно указать методы, основанные на расчете информационной энтропии и показателе Боргатти ^{[1, 2]}. Авторы в работе ^[3] также предложили использовать для данной задачи процедуру ранжирования Кендалла-Уэя и показали, что данный метод дает результаты, сходные с методом Боргатти.

В настоящее время нельзя определенно назвать единственный лучший метод поиска пользователей-экспертов. Валидация и эффективность способов решения задачи KPP‑POS представлена на подробно описанных в литературе социальных графах, таких как krebs ^[4] и mexican ^{[5, 6]}, которые представляют собой невзвешенные и неориентированные графы с заранее известными ключевыми игроками, где большинство известных способов дают сходные, но не идентичные результаты. При этом, для адекватного представления реальной группы пользователей социальных сетей авторы используют ориентированные и взвешенные социальные графы ^[7]. Проверка эффективности данных способов, применительно к задаче поиска в социальных сетях пользователей-экспертов в заданной предметной области, затруднена отсутствием фактических данных. Такие данные могут быть получены путем трудоемкого процесса проведения многократных социологических опросов в разных предметных областях с последующим сравнением результатов опросов и применяемых способов. Таким образом, в настоящее время нельзя определенно назвать оптимальный метод поиска пользователей-экспертов.

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

Теоретический анализ

Множество литературных источников посвящено проблеме идентификации значимых узлов в социальных сетях ^{[1, 8, 9]}. Для обозначения таких узлов используются разнообразные термины: влиятельный узел, ключевой игрок, критический узел, жизненно важный узел и т.д. ^[9]. В работе ^[1] данная проблема была обозначена как проблема поиска ключевых игроков (KPP, Key player problem) и разделена на два класса: Positive (POS) и Negative (NEG). При этом, класс задач KPP‑NEG направлен на поиск такого узла (или группы узлов) социального графа, удаление которого сделает граф максимально фрагментированным. Подходы к решению данной проблемы можно применять для решения задач в области медицины; например, при эпидемиях это задача идентификации группы риска, вакцинация которой максимально сократит распространение заболевания. Также, данные подходы используются для задач антитеррористической направленности, в частности, при выявлении участников, исключение которых из террористической группы максимально разобщит оставшихся членов. Позже данному классу задач был присвоен термин CNP (Critical Node Problem) ^[8] и дано аналитическое описание.

Второй класс задач KPP‑POS направлен на идентификацию узла (или группы узлов), максимально распространяющего информацию по сети. Решение данной проблемы необходимо, например, для решения задачи внедрения в террористическую сеть информаторов, за счет которых неверная информация максимально быстро распространится по сети ^[1].

Пользователи социальных сетей, являющиеся экспертами в некоторой предметной области, задают темы для обсуждения, к их мнению прислушиваются другие пользователи. Мнения пользователей-экспертов распространяются по социальной сети за счет различных действий читателей, таких как комментирование, репост, упоминание, «лайк». Задача идентификации пользователей-экспертов в социальных сетях имеет некоторые отличия от задачи CNP и, очевидно, относится к классу задач KPP‑POS.

Анализ литературы ^{[1, 2, 10, 11]} позволил выявить следующие способы решения задачи KPP‑POS, считающиеся наиболее эффективными:

- способ, основанный на вычислении показателя Боргатти;

- расчет информационной энтропии вершин графа;

- расчет коммуникационной эффективности.

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

Однако, применение предложенных способов решения проблемы KPP‑POS к задаче определения пользователей социальных сетей, являющихся лидерами общественного мнения или рассматриваемых в качестве экспертов по заданной тематике, связано со следующими трудностями:

- в литературе решение данной проблемы апробируется на неориентированных и/или невзвешенных графах [1‑3, 7‑11]. Использование таких графов значительно сокращает их способность адекватно представлять реальную группу пользователей социальных сетей, поскольку не позволяет учитывать дополнительную информацию об отношениях между пользователями ^{[3, 7]}.

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

Проведенные авторами исследования методов решения задачи идентификации пользователей‑экспертов с учетом описанных выше трудностей позволили сформировать методику построения социального графа, отражающего заинтересованность пользователей социальной сети публикациями пользователей-экспертов, что, в свою очередь, позволило адаптировать и оценить эффективность применения существующих известных способов ^{[3, 7, 12]}. Кроме того, результаты исследований позволили подтвердить возможность применения для решения задачи KPP-POS процедуры ранжирования Кендалла-Уэя, несомненным достоинством которой является простота программной реализации алгоритма ранжирования в сравнении с дистанционными алгоритмами ^[3].

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

1. По выбранным данным из социальной сети строится ориентированный взвешенный социальный граф, ` ` , где `V={v_(i) }` – множество узлов графа `(i=1,2,...N)` , `A={(v_(i), v_(j))} subseteq V^(2)` – множество направленных ребер (дуг), а w – весовая функция, ставящая в соответствие каждой дуге `a_(i j) = (v_(i), v_(j)) in A` некоторое значение `a_{i j} in R` .

При этом узлы графа связаны ребрами по следующему принципу: существует направленное ребро (дуга) `a_{i j}` , связывающее узлы i и j, если j-й пользователь комментировал публикации i-го пользователя, делал их репост или репост с комментарием, упоминал в своих комментариях i-го пользователя. Вес каждого ребра рассматривается как значение функции заинтересованности одного пользователя публикациями другого, т.е. `(a_{i j} ) = f (r_{i j}, c_{i j}, m_{i j}, x_{i j})` , где f - функция заинтересованности; r – количество репостов, с – количество комментариев, m - количество упоминаний пользователя-эксперта, x – репостов с комментариями. Методика построения социального графа и расчета `w(a_{i j})` подробно описана авторами в ^[7].

2. На основе данных социального графа параллельно выполняется идентификация пользователей-экспертов в соответствии с выбранными способами. Авторы предлагают использовать метод, предложенный Боргатти, и процедуру ранжирования Кендалла-Уэя, как наиболее эффективные ^{[3, 12]}. Результат ранжирования указанными способами представляет собой набор из пар чисел `(x_{i}, y_{i}), i= 1...N` , определяющих на координатной плоскости положение точек, соответствующих вершинам `v_{i}` графа. При этом координаты представляют собой значения влиятельности, полученные с помощью процедуры ранжирования Кендалла-Уэя (KW) и метода Боргатти (BG) т.е.:

`forall v_{i} in V, v_{i} rightarrow (x_{i},y_{i}), x_{i}=KW_{i}, y_{i}=BG_{i}`

3. Идентификация группы наиболее влиятельных экспертов проводится с использованием кластеризации полученного массива данных методом распространения близости (AP, affinity propagation) ^[13].

Следует отметить, что выбранный метод кластерного анализа обладает рядом преимуществ, среди которых можно отметить более низкую ошибку кластеризации по сравнению с другими методами, например, с известным методом кластеризации k‑средних ^[14]. Также, метод AP самостоятельно определяет количество кластеров и обладает сравнительно низкой вычислительной сложностью при использовании алгоритма, описанного в работе ^[15] – `O (N^{2}+ MT)` , где N – количество узлов в социальном графе, М – количество ребер графа, Т – число итераций алгоритма.

Результат кластеризации позволяет выделить классы пользователей социальной сети в соответствии с попаданием кластеров в одну из четырех зон на координатной плоскости (рисунок 1):

- зона (A), в которую попадают пользователи, обладающие высокими значениями влиятельности в заданной предметной области в соответствии с каждым из методов;

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

- зона (С), в которую попали пользователи, либо являющиеся скрытыми лидерами, либо ошибочно определенные в качестве лидеров одним из методов;

- зона (D), включающая в себя пользователей со средней степенью влиятельности.

Авторы предлагают формировать зоны А, B и С таким образом, чтобы каждая из них представляла собой четверть окружности (рисунок 1). Указанный размер зоны выбран авторами произвольно, исходя из широко распространённого приема работы с квартилями в экспертных методах принятия решений ^[16]. В зависимости от решаемой задачи, размер зоны может быть скорректирован как в сторону увеличения, так и уменьшения. В частности, предлагается использовать дополнительную зону с увеличенным радиусом, что позволит облегчить визуальный анализ.

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

Рисунок 1 – Интерпретация результатов кластерного анализа в предложенном способе

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

Постановка эксперимента

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

При выборе тем авторы руководствовались новостными средствами массовой информации, для подбора предметных областей, активность пользователей по которым составляла бы не менее 384 человек. Данный размер выборки объясняется необходимостью получить репрезентативную выборку, которой будет достаточно для оценки мнения российской аудитории данной социальной сети. Согласно данным Левада‑центра в России социальными сетями пользуется только 59% населения старше 18 лет, из которых социальную сеть Twitter использует 7%, т.е. около 4,13 млн. человек ^[17]. Таким образом, можно говорить о том, что мнения, полученные по крайней мере от 384 человек, представляют репрезентативную выборку с доверительной вероятностью 95% для пользователей данной социальной сети в России.

Для социальных графов, построенных по собранным данным, были определены коэффициент кластеризации и средний кратчайший путь, а также количество сегментов в графе. Можно отметить низкое значение коэффициента кластеризации полученных социальных графов. Так, среднее его значение составило 0,0127, а минимальные и максимальные значения равны 0,01 и 0,2, соответственно. Средний кратчайший путь составляет 1,5. Можно отметить высокую сегментированность используемых для анализа социальных графов: количество сегментов варьируется от 5 до 160. Это объясняется как отсутствием технической возможности сделать полную выборку данных по определенной предметной области, так и возможной особенностью формирования общения пользователей сети, заинтересованных предметной областью. Среди таких пользователей, заинтересованные предметной областью в краткосрочной и долгосрочной перспективе, а также имеющие разную степень заинтересованности. Все это в совокупности может влиять на рассчитанные параметры социальных графов. Кроме этого, можно отметить, что социальные графы проявляют свойство безмасштабных сетей ^[18]: малое количество узлов обладает высокой степенью связности, тогда как большое количество узлов обладает низкой степенью связности.

На этапе выбора генератора модельных социальных графов для проведения экспериментального анализа был проведен обзор существующих моделей случайных графов, среди которых можно отметить модель Эрдеша-Реньи, позволяющую моделировать сети типа «Мир тесен» ^{[19, 20]}, и модель Барбаши-Альберта ^[21]. Также была рассмотрена модель случайного графа с нелинейным правилом предпочтительного связывания, предложенная В.Н. Задорожным ^{[22, 23]}, позволяющая выращивать случайные графы с использованием механизма предпочтительного связывания.

Модель Задорожного выгодно отличается от других, поскольку позволяет генерировать ориентированные графы ^[23]. Однако, в рамках настоящего исследования ее использование осложнено отсутствием эталонной модели социального графа.

Таким образом, оценивая характеристики социальных графов, построенных по выборкам из социальной сети, было принято решение использовать модель предпочтительного связывания, с ее адаптацией для взвешенного ориентированного графа, как описано ниже. Случайный ориентированный граф формируется из небольшого графа‑затравки с количеством вершин от 3 до 6. На рисунке 2 представлен пример графа‑затравки.

Рисунок 2 – Пример графа-затравки, состоящего из 4 узлов

Далее, к графу добавляется новая вершина, которая связывается направленной входной дугой с другими вершинами в соответствии с моделью Барбаши-Альберта. Таким образом, вероятность связывания новой вершины с существующими определяется по формуле ^[18]:

`P (k_{i}) = frac{k_{i}}{sum_{j}{:k_{j}:} }` , (1)

где i – вершина, с которой происходит связывание новой вершины, `k_{i}` – полустепень исхода, j=1…N, N – текущее число вершин в графе.

Из формулы (1) видно, что чем больше полустепень исхода вершины, тем выше вероятность её выбора. Такой способ построения исходящих связей имитирует большую значимость тех пользователей, чьи сообщения находят более активный отклик среди читателей в виде репостов, комментариев и т.п.

Входные дуги для новой добавляемой вершиной формируются с постоянной вероятностью независимо для каждого узла в соответствии с моделью Эрдеша-Реньи. Предлагается использовать небольшие значения данной вероятности: 0,09-0,2. Такой способ получения дуг позволяет построить «горизонтальные» связи социального графа, т.е. имитировать заинтересованность любого пользователя сообщениями другого пользователя вне зависимости от его значимости. Далее, дугам построенного ориентированного графа присваивается случайный вес, распределенный в соответствии с бета-распределением ^[7].

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

Для проведения экспериментального анализа были выбраны четыре предметных области:

- - Область, связанная с проведением космической миссии BepiColombo по исследованию планеты Меркурий, проходящей в момент подготовки данной работы.

- - Область, связанная с ученым-физиком Стивеном Хокингом; данная область была выбрана в связи с выходом книги данного ученого, что повлияло на объем сообщений в социальной сети.

- - Мнения и отзывы пользователей социальной сети, посвященных годовщине восстания в лагере смерти «Собибор» и выходу одноименного фильма.

- - Мнения и отзывы, посвященные сериалу «Westworld»; данные были собраны в день выхода последней серии второго сезона сериала, что позволило в течение короткого времени получить выборку данных с сообщениями 714 уникальных пользователей.

Экспериментальный анализ

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

Для модельных экспериментов было сгенерировано 50 случайных графов с 400 узлами. Большие размеры случайных графов в модельных экспериментах не использовались с целью экономии вычислительных и временных затрат на их обработку. Диапазоны и средние значения характеристик данных графов приведены в таблице 1.

Таблица 1. Характеристики графов, построенных по данным из социальной сети Twitter

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

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

Рисунок 3 – Результаты кластеризации, полученные для случайного графа (N = 400)

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

Таблица 2. Данные социальных графов для анализируемых предметных областей.

Для каждого социального графа была выполнена оценка влиятельности пользователей посредством процедуры ранжирования Кендалла-Уэя ^{[24, 25]} и методом Боргатти ^[1]. Таким образом, для каждого узла были получены две числовых характеристики значимости. Для выполнения кластерного анализа полученные результаты были независимо нормированы по каждой характеристике в диапазоне от 0 до 100.

Однако, полученные результаты обладали низким качеством визуализации данных из‑за большого количества точек с близкими значениями числовых характеристик значимости (рисунок 4 а). Поэтому значения числовых характеристик, полученных по результатам процедуры Кендалла-Уэя и метода Боргатти, вначале были прологарифмированы и лишь затем нормированы (рисунок 4 б).

Рисунок 4 – Визуализация результатов идентификации пользователей-экспертов по хэштегу #StephenHawking

а) нормированные данные; б) нормированные прологарифмированные данные

Подготовленные таким образом данные были подвергнуты процедуре кластеризации методом распространения близости ^[13] с помощью быстрого алгоритма Fast Affinity Propagation (FAP) ^[15], позволяющего получить тот же результат кластеризации за меньшее число итераций, по сравнению со стандартным алгоритмом ^[13].

На рисунке 5 представлен результат кластеризации данных, собранных по хэштегу #Bepicolombo, из которого видно, что пользователи разделились на 4 группы. Большинство точек попало в зону B, две группы кластеров расположены в зоне D и не представляют интереса в рамках поставленной задачи. Группа лидеров состоит из 7 пользователей, два из которых попали в зону D. В зависимости от решаемой задачи они могут быть как исключены из группы пользователей-экспертов, так и проанализированы вместе с явными лидерами.

Рисунок 5 – Результат кластеризации вершин социального графа BepiColombo

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

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

Таблица 3. Профили пользователей-лидеров графа BepiColombo

Аналогично, работоспособность предложенного способа демонстрирует анализ выборки, собранной из социальной сети Twitter по хэштегу #Собибор. На рисунке 6 представлен результат кластеризации данных.

Рисунок 6 –Результат кластеризации вершин социального графа Собибор

Группа лидеров состоит из двух пользователей: профиль Российского военного исторического общества (имя пользователя «rvio_ru»), которое упомянуло о событии в серии твитов, а также профиль пользователя «vltavskaja». Сообщение данного пользователя (доступное по ссылке https://twitter.com/vltavskaja/status/1051373844651565056) вызвало активный отклик среди читателей: 238 ретвитов и 18 комментариев, что и позволило пользователю «vltavskaja» войти в группу лидеров.

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

Рисунок 7. Результат кластеризации вершин социального графа Westworld

На границе зоны А можно выделить два узла; при этом используемые способы дали разную оценку этим узлам. Основная группа лидеров расположилась в зоне D, что говорит о том, что группу лидеров составляют пользователи со средней активностью в данной области. Анализ профилей пользователей лидирующей группы продемонстрировал современный тренд распространения информации в социальных сетях посредством мемов ^[26]. В таблице 4 перечислены ключевые пользователи из группы лидеров и дано описание их профилей.

Таблица 4. Профили пользователей-лидеров графа Westworld

Полученные результаты объясняются, в том числе, отсутствием предобработки исходных данных, которая позволила бы исключить профили и твиты юмористической направленности. Кроме этого, на результат повлияло ограничение API Twitter, в результате которого можно выбрать данные публикуемые в момент сбора данных, а также с давностью не более 7 дней. Таким образом, в выборку не попали профили режиссеров и актеров сериала.

Последней эксперимент с помощью предложенного способа был проведен на выборке, полученной по хэштегу #StephenHawking (рисунок 8). В таблице 5 перечислены ключевые пользователи из группы лидеров.

Рисунок 8 – Результат кластеризации вершин социального графа StephenHawking

Таблица 5. Профили пользователей-лидеров графа StephenHawking

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

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

Заключение

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

В ходе выполнения данной работы был разработан экспериментальный сервис, демонстрирующий работу представленного способа, размещенный по адресу http://socgraph.tpu.ru.

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

Работа выполнена при финансовой поддержке РФФИ (проект №17-07-00034 А).