УДК 32.019.51

В.С. ЗАЯКИН, А.Н. РАБЧЕВСКИЙ, Е.А. РАБЧЕВСКИЙ

ВЫЯВЛЕНИЕ МОСТОВ В КЛАСТЕРНЫХ СЕТЯХ

И ОЦЕНКА ИХ УРОВНЯ ИНФОРМАЦИОННОГО ВЛИЯНИЯ

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

Ключевые слова: социальные сети; кластерные сети; мосты; определение мостов; центральность; взвешенный вклад.

ВВЕДЕНИЕ

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

Изучение механизмов и степени влияния социальных сетей на поведение людей вызвало большой научный интерес. По мнению [1-3], все протестные движения неразрывно связаны с созданием автономных сетей связи, поддерживаемых Интернетом. Существенное влияние социальных сетей на уровень мобилизации людей к активным действиям описано в работах [4-6]. Исследуя социальные сети в контексте протестных настроений, часто приходится наблюдать их ярко выраженную кластерную структуру.

Рисунок 1 – Примеры кластерной структуры графов социальных сетей

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

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

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

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

ПОСТАНОВКА ЗАДАЧИ

С помощью программного обеспечения «Поисковая система «SEUS» [7], активно используемого правоохранительными органами РФ [8], был выполнен поиск публикаций в социальной сети ВКонтакте, связанных с организацией протестных мероприятий в январе – августе 2019 г. в Москве. Для каждого пользователя был рассчитан уровень публикационной активности, который учитывал количество постов, репостов, комментариев, лайков и т.д. В результате ранжирования по уровню публикационной активности был составлен рейтинг активности пользователей. Для каждого пользователя были построены графы социальных связей друзей пользователей и друзей их друзей. При этом учитывались следующие условия:

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

Мостом считался узел социальной сети, удовлетворяющий следующим требованиям:

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

На рисунке 2 представлен фрагмент типичного узла, выполняющего роль моста.

Рисунок 2 – Фрагмент графа пользователя – моста

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

СУЩЕСТВУЮЩИЕ МЕТОДЫ

ВЫЯВЛЕНИЯ МОСТОВ В КЛАСТЕРНЫХ СЕТЯХ

Для выявления характеристик узлов в сетях используются различные метрики центральности, описанные в обзорной работе [9]. Самой известной метрикой центральности, характеризующей коммуникативные способности узлов, является впервые введенная [10] центральность по промежуточности, которая соответствует тому, с какой вероятностью данный узел будет связывать множество пар узлов в графе. Поскольку каждый узел в исследуемых нами сетях имел определенный уровень активности, необходимо было учитывать вес каждого узла в сети. Для вычисления центральности по промежуточности для взвешенных сетей можно было использовать методики, предложенные в работах [11-15]. Однако, центральность по промежуточности, не важно с учетом веса или без, может выявить уровень коммуникативной способности узла сети, но не может точно определить действительно ли данный узел является мостом, так как узлы с высоким значением центральности по промежуточности могут находиться как в центре ядра сети, так и на периферии сети, являясь мостами.

Влиятельные узлы, по мнению [16], всегда действуют как «мост» между сообществами и существуют в рамках пересечения сообществ. Авторы предлагают использовать для определения таких влиятельных узлов локальный центральный метод, который предполагает, что чем больше сообществ принадлежит узлу, тем большее влияние он оказывает. В работах [17, 18] для определения мостов предлагаются метрики «центральность передачи» и «модульная центральность», однако значение центральности передачи может быть высоким как у вершин ядра, так и у мостов, поэтому ее смысл не сильно отличается от промежуточности, а в модульной центральности мостом являются узлы, соединяющие сообщества, тогда как мы исследовали узлы между сообществами и ядром сети, то есть понятие мост в данном контексте имело иной смысл.

Метод, успешно определяющий мосты, представлен в работе [19], в которой авторы ввели понятие «Мостовая центральность». Эта метрика более точно выявляет мосты, однако она работает только в разреженных сетях с большим количеством колен, так как в ее основе лежит идея о том, что для выявления мостов необходимо отбрасывать значение связей с узлами, находящимися в непосредственной близости узла, то есть связи первого колена графа. Поскольку, в нашем случае пользователи кластера связаны только с мостом, то они не могут быть учтены в расчете данной метрики, что нас не устраивало. Наиболее близкая метрика для нашей задачи, это «Центральность вклада», предложенная [20], суть которой состоит в том, что центральность узла пропорциональна сумме центральностей узлов в его окрестности, взвешенной по их вкладам. Центральность вклада действительно наиболее применима для решения нашей задачи, так как она может определить вклад каждого моста для пользователей ядра, но она не гарантирует однозначное определение моста, что в нашем случае являлось необходимым условием.

Как видим, все представленные выше метрики в той или иной степени могли бы определить уровень коммуникативной способности узла, но не могут точно определить является ли данный узел мостом в нашем понимании.

МЕТОД ВЫЯВЛЕНИЯ МОСТОВ

В ЯРКО ВЫРАЖЕННЫХ КЛАСТЕРНЫХ СЕТЯХ

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

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

Рисунок 3 – Схема сети узлов с учетом весов

Для узла F связи с узлами E и X1-X4 учитываться не будут, так как они имеют связи с другими узлами в сети, а значит значение суммарного рейтинга узла F, также как и для X1-X4, будет равно 0.

Для узлов A, B, C, D, имеющих связь только с узлом E, значение так же будет равно 0, так как у него также есть другие связи.

Для узла E связь с узлом F также дает 0, а связи с узлами A, B, C, D дают значение весов этих узлов, вес узла E будет равен сумме весов синих узлов E=A+B+C+D.

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

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

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

Значение центральности по взвешенному вкладу =0 , если узел не является мостом, и >0, если узел является мостом. Самый влиятельный узел в роли моста имеет максимальное значение центральности по взвешенному вкладу для данной сети.

Введем обозначения для формального описания предлагаемой методики.

Пусть G = (U, F) – граф, состоящий из множества U пользователей и множества F неупорядоченных пар различных элементов множества U, отражающего дружественные связи между пользователями (рёбра графа).

Если пользователи u и υ являются друзьями, то есть образуют связь f ∈ F, будем писать f = (uυ) = (υu). Множество друзей пользователя u ∈ U обозначим F(u) = {υ ∈ U : (uυ) ∈ F}. Тогда степень узла, т. е. число друзей пользователя u ∈ U, естественно обозначить |F(u)|.

Множество пользователей, связанных только с данным пользователем u, назовем соседями пользователя u ∈ U и обозначим S(u). Тогда:

S(u) = {υ ∈ U : (uυ) ∈ F , |F(υ)| = 1} = {υ ∈ U : |F(υ)| = 1} ∩ F(u) (1)

Если уровень активности пользователя u ∈ U обозначить как r(u), то суммарный уровень активности некоторого подмножества пользователей V ⸦ U будет вычисляться по формуле:

R (V) = \sum_{u \in V} r (u)

(2)

Пользуясь формулой (2), получаем формулу вычисления веса кластера, подключаемого мостом, произвольного пользователя графа:

C_{WC} (u) = R (S (u)) = \sum_{w \in S (u)} r (w)

(3)

Центральность по взвешенному вкладу определяется как отношение веса кластера, подключаемого мостом к ядру сети, к общему уровню активности сети, что можно выразить как

C_{WC} (u) = \frac{W (u)}{R (U)}

Код функции на языке Python3, используемой для вычисления мостов в составе программы [21], представлен ниже:

def calculate_weighted_contribution_centrality(graph, rating):

centrality = {}

for user, friends in graph.items():

c = 0 # накапливаемое значение центральности пользователя user

# накапливаем рейтинг по друзьям пользователя

for friend in friends:

# если друг пользователя связан в графе только с ним, то прибавляем его рейтинг

if len(graph[friend]) == 1:

c = c + rating[friend]

centrality[user] = c

return centrality

ОЦЕНКА ЭФФЕКТИВНОСТИ МЕТОДА ВЫЯВЛЕНИЯ МОСТОВ

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

Таблица 1

Изменение веса графа в результате удаления из графа 10 мостов с их вершинами

№ графа	Изменение веса графа	Изменение веса кластеров
1	-32,7%	-67,5%
2	-53,0%	-88,6%
3	-44,1%	-65,9%
4	-92,0%	-94,5%
5	-97,3%	-99,7%
6	-72,1%	-92,6%
7	-21,9%	-61,0%
8	-27,2%	-68,3%
9	-48,5%	-72,3%
10	-83,4%	-98,9%
	Среднее значение	Среднее значение
	-57,2%	-80,9%

Как видим, при удалении из графов 10 самых влиятельных мостов, суммарный вес графа или суммарный уровень активности пользователей в графе снижается в среднем на 57,8%, что показывает высокий уровень влияния мостов. При этом суммарный вес кластеров снижается на 80,9%, что соответствует тому, какую роль играют 10 самых влиятельных мостов в расширении сети. Из этого можно сделать вывод, что узлы сети, выявленные нами как мосты, действительно вносят существенный вклад в общий уровень активности сети. Сравнение результатов, которые получились при использовании центральности по промежуточности и центральности по вкладу представлены в таблице 2.

Таблица 5

Изменение метрик центральности в результате удаления из графа 10 мостов с их вершинами

Метрика	Изменение веса графа	Изменение веса кластеров
Центральность по промежуточности	-54,4%	-76,0%
Центральность по вкладу	-52,7%	-66,4%
Центральность по взвешенному вкладу	-57,2%	-80,9%

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

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

ЗАКЛЮЧЕНИЕ

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

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

Оценка уровня информационного влияния осуществляется путем ранжирования мостов по метрике центральности по взвешенному вкладу.

Алгоритм вычисления в кластерных сетях на основе метрики центральности по взвешенном вкладу реализован в программном обеспечении (Свидетельство о государственной регистрации программы для ЭВМ № 2021616086 от 16 апреля 2021г.).

Данный метод выявления мостов и оценки их информационного влияния был использован в рамках аналитического исследования «структур пропаганды политического протеста в России и Беларуси» [22], проводимого аналитическим центром ООО «СЕУСЛАБ». Исследование включало оценку оперативной значимости полученных результатов, и было представлено на площадке Антитеррористического Центра СНГ и НИИ проблем безопасности СНГ в марте 2021 года. По результатам апробации научно-консультативный совет Антитеррористического Центра СНГ составил экспертное заключение о целесообразности использования данного метода в информационно-аналитических системах, используемых в оперативно-служебной деятельности МВД России.

СПИСОК ЛИТЕРАТУРЫ

1.Castells M. Networks of Outrage and Hope. Social Movements in the Internet Age. – Polity. – Cambridge, 2012 [Электронный ресурс]. – URL: https://doi.org/10.1145/324133.324140.
2.Gerbaudo P. Tweets and the Streets. Social Media and Contemporary Activism. – Pluto Books. – London, 2012 [Электронный ресурс]. – URL: https://library.oapen.org/bitstream/handle/20.500.12657/30772/642730.pdf?sequence=1.
3.Faris D. Dissent and Revolution in a Digital Age: Social Media, Blogging, and Activism in Egypt. – I.B. Tauris. – London, 2013 [Электронный ресурс]. – URL: https://doi.org/10.5040/9780755607839.
4.Tindall D.B. From metaphors to mechanisms: Critical issues in networks and social movements research. – Social Networks. – № 29(1). – P. 160-168, 2007 [Электронный ресурс]. – URL: https://doi.org/10.1016/j.socnet.2006.07.001.
5.Bennett W.L., Segerberg A. The logic of connective action. Information, Communication & Society. – № 15(5), 2013 [Электронный ресурс]. – URL: https://doi.org/10.1080/1369118X.2012.670661.
6.Juris J.S. Reflections on #Occupy Everywhere: Social media, public space and emerging logics of aggregation. – American Ethnologist. – № 39(2). – P. 259-279, 2012 [Электронный ресурс]. – URL: https://doi.org/10.1111/j.1548-1425.2012.01362.x.
7.[Электронный ресурс]. – URL: https ://www .seuslab .ru /seus.
8.[Электронный ресурс]. – URL: https ://meduza .io /feature /2018/10/16/politsiya -po -vsey -rossii -pokupaet -sistemy -monitoringa -sotssetey -oni -pomogayut -iskat -ekstremizm -ne -vyhodya -iz -rabochego -kabineta.
9.Lü L. Vital nodes identification in complex networks. – Physics Reports, 2016. – Vol. 650.
10.Freeman L.C. Centrality in social networks conceptual clarification. – Social Networks. – № 1(3). – P. 215, 1978 [Электронный ресурс]. – URL: https://doi.org/10.1016/0378-8733(78)90021-7.
11.Opsahl T., Agneessens F., Skvoretz J. Node centrality in weighted networks: Generalizing degree and shortest paths. – Social Networks. – № 32(3). – P. 245251, 2010 [Электронный ресурс]. – URL: https://doi.org/10.1016/j.socnet.2010.03.006.
12.Кузнецов Е. Анализ структуры сетевых взаимодействий: контекстно-зависимые меры центральности. – Управление большими системами. – Выпуск 80. – М.: ИПУ РАН. – С. 57-82, 2019 [Электронный ресурс]. – URL: https://doi.org/10.25728/ubs.2019.80.4.
13.Wang H., Hernandez J.M., Van Mieghem P., Betweenness centrality in a weighted network. – Physical Review E. – № 77(4), 2008 [Электронный ресурс]. – URL: https://doi.org/10.1103/physreve.77.046105.
14.Van Mieghem P., Van Langen S., Influence of the link weight structure on the shortest path. – Phys Rev E Stat Nonlin Soft Matter Phys, 2005. – May;71(5 Pt 2):056113. Epub 2005 May 20. PMID: 16089608, 2005 [Электронный ресурс]. – URL: https ://doi .org /10.1103/PhysRevE .71.056113.
15.Levandowsky M., Winter D., Distance between Sets. – Nature. – № 234(5323). – P. 34-35, 1971 [Электронный ресурс]. – URL: https://doi.org/10.1038/234034a0.
16.Wei H. and other. Identifying influential nodes based on network representation learning in complex networks / H.Wei, Z. Pan, G. Hu, L. Zhang, H. Yang, X. Li, X. Zhou // PLOS ONE, 13(7), e0200091, 2018 [Электронный ресурс]. – URL: https://doi.org/10.1371/journal.pone.0200091.
17.Zhang Q., Karsai M., Vespignani A. Link transmission centrality in large-scale social networks. – EPJ Data Science. – № 7(1), 2018 [Электронный ресурс]. – URL: https://doi.org/10.1140/epjds/s13688-018-0162-8.
18.Ghalmane Z., El Hassouni M., Cherifi C. Centrality in modular networks. EPJ Data Sci. 8, 15, 2019 [Электронный ресурс]. – URL: https://doi.org/10.1140/epjds/s13688-019-0195-7.
19.P. Ensen and other. Detecting global bridges in networks / P. Ensen, M. Morini, M. Karsai, T. Venturini, M. Jacomy, J-P. Cointet, P. Merckle´, E. Fleury // IMA Journal of Complex Networks, 2015. – P. 1, 2015 [Электронный ресурс]. – URL: https://arxiv.org/pdf/1509.08295.
20.Alvarez-Socorro A., Herrera-Almarza G., González-Díaz L. Eigencentrality based on dissimilarity measures reveals central nodes in complex networks. – Sci Rep 5, 17095, 2015 [Электронный ресурс]. – URL: https://doi.org/10.1038/srep17095.
21.«Программа вычисления мостов в кластерных сетях», свидетельство о государственной регистрации программы для ЭВМ № 2021616086 от 16.04.2021.
22.Рабчевский Е.А., Рабчевский А.Н., О некоторых аспектах структур пропаганды политического протеста в социальных сетях. // Деятельность террористических и экстремистских организаций, направленная на насильственное изменение конституционного строя, как угроза государственной и общественной безопасности стран СНГ: Сборник материалов совместного заседания ученого совета Научно-исследовательского института проблем безопасности СНГ и Научно-консультативного совета при АТЦ СНГ. М.: АТЦ СНГ, 2021, c. 193–211.

Сведения об авторах

Рабчевский Андрей Николаевич – ООО «СЕУСЛАБ», директор по науке, 614066, г. Пермь, ул. Шоссе Космонавтов 111, корпус 3, помещение 4 (оф. 302). тел +79127808729, эл. почта: andrey @ranat .ru,

Заякин Виктор Сергеевич (Пермь, Россия) – ООО «СЕУСЛАБ», аналитик данных614066, г. Пермь, ул. Шоссе Космонавтов 111, корпус 3, помещение 4 (оф. 302)., тел.+79523208551, эл. почта: vszayakin @yandex .ru,

Рабчевский Евгений Андреевич (Пермь, Россия) – ООО «СЕУСЛАБ», генеральный директор, 614066, г. Пермь, ул. Шоссе Космонавтов 111, корпус 3, помещение 4 (оф. 302), тел +79082658825, эл. почта: e .rabchevskiy @seuslab .ru.

Identifying bridges in cluster networks

Abstract. The task of identifying users who maximize the dissemination of information and the growth of the number of participants in social networks is very important to prevent the spread of viral content, fakes and other destructive information. The article proposes a methodology for identifying the most influential users of social networks connecting clusters (communities) with the network core and acting as bridges in cluster networks, based on the original measure of weighted contribution centrality. A description of the measure and an algorithm for its calculation are presented.

Keywords: social networks, cluster networks, bridges, bridge definition, centrality, weighted contribution.