Акциональная модель влиятельности пользователей социальной сети

У

правление в социально-экономических системах

УДК 519.8

АКЦИОНАЛЬНАЯ МОДЕЛЬ ВЛИЯТЕЛЬНОСТИ ПОЛЬЗОВАТЕЛЕЙ СОЦИАЛЬНОЙ СЕТИ

Д.А. Губанов, А.Г. Чхартишвили

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

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

ВВЕДЕНИЕ

В последнее десятилетие онлайновые социальные сети (РаееЪоок, ВКонтакте, Одноклассники и др.) прочно вошли в нашу жизнь и оказывают большое влияние на экономическую и социально-политическую жизнь общества. Им посвящено большое количество публикаций (см., например, [1, 2]), однако по-прежнему актуальной остается задача построения развернутых содержательных моделей.

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

неудивигельно, что ответ на вопрос «какие пользователи социальной сети самые влиятельные?» интересует как теоретиков, так и практиков.

Среди исследований моделирования социального влияния и влиятельности можно выделить несколько направлений. Большая область исследований связана со структурным подходом к оценке влияния, оперирующим понятиями структурной центральности классической теории социально-сетевого анализа (Social Network Analysis, SNA). Вот уже несколько десятилетий исследователями разрабатываются такие показатели структурной центральности узлов и связей в сетях как, например, близость узла, посредничество узла, посредничество связи и другие (см. работы [4, 5] и др.). Несмотря на свою математическую строгость, такой подход, учитывающий только статическую структуру связей между членами социальных сетей, является содержательно бедным и слабо обоснованным (на основании чего определяется влияние членов сети и как использовать полученные результаты для решения конкретной задачи управления?). К этой области исследований примыкает еще одно интенсивно развивающееся в последнее десятилетие «вычислительное» направление, которое связано с разработкой методов расчета влиятельности пользователей в онлайновых социальных сетях. Для расчета влиятельности в социальных сетях исследователи (см. работы [6—8] и др.), как правило, модифицируют различные методы ранжирования веб-страниц и наукометрические

методы. Недостатки этого направления (его возникновение обусловлено появлением доступных данных из онлайновых социальных сетей) такие же, как и «обычного» SNA, несмотря на частичный учет некоторых аспектов влияния (напри -мер, учет тематического влияния, учет активности пользователей).

Еще одна большая область исследований связана с изучением и моделированием различных информационных процессов в социальных сетях. Собственно, в таких исследованиях при помощи влияния объясняется динамика процессов (изменение мнений, распространение информации и т. п.). Разрабатываются марковские модели, модели с порогами, модели независимых каскадов, модели клеточных автоматов, модели эпидемий и др. (см. работы [9—13] и др.). Основная цель такого рода моделей — объяснить социальное поведение для сети в целом (на макроуровне), поэтому правила для отдельных элементов сети (на микроуровне) очень просты: члены сети обновляют свое внутреннее состояние при взаимодействии со своими соседями, и возникающее макроскопическое поведение системы является результатом большого числа таких взаимодействий. Влияние агента служит некоторым числом (или вектором) и определяет значимость взаимодействия, природа самого влияния зачастую не раскрывается. К этой области примыкает отдельная ветвь исследований, в которой на основе упомянутых моделей решаются различные задачи оптимизации, в частности, задача определения наиболее влиятельных пользователей (в более общем случае — конечного множества наиболее влиятельных пользователей), косвенное воздействие которых приводит к максимальному распространению (см. работы [11, 12] и др.).

Однако несмотря на обилие исследований, на данный момент отсутствуют более фундаментальные модели, в рамках которых можно анализировать и сравнивать различные методы и алгоритмы. В настоящей работе предлагается общий подход к определению влиятельности, основанный на модели распространения действий (§ 2) и учете точки зрения управляющего органа (§ 3). В основе предлагаемой модели лежат действия пользователей, поэтому она названа акциональной моделью. В § 4 и 5 приведены примеры возможного применения предлагаемого подхода, а в § 6 показана возможность обобщения для расчета влиятельности подмножества пользователей.

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

Стена — личная страница пользователя с информацией о его активностях за период пользования социальной сетью: посты, комментарии и пр.

Пост — отдельное сообщение, размещаемое пользователем на стене.

Комментарий — сообщение, следующее после поста (или другого комментария) и представляющее собой реакцию на него.

Репост — пост, являющийся копией поста другого пользователя.

Оригинальный пост — пост, не являющийся ре-постом.

Лайк — условное выражение одобрения материалу (посту, комментарию).

Подписка — связь между двумя пользователями, означающая следующее: если пользователь 1 подписан на пользователя 2, то пользователь 1 читает посты пользователя 2.

1.РАСПРОСТРАНЕНИЕ ДЕЙСТВИЙ

Опишем формальную модель распространения действий в социальной сети.

Пусть участниками сети являются агенты (пользователи) из множества N = {1, 2, ..., п}, которые совершают действия того или иного вида из фиксированного множества К = {1, 2, ..., 1} в те или иные моменты времени из интервала Т. Видом действия может быть написание поста, написание комментария к посту и т. п. Обозначим множество действий (написание конкретного поста, комментария и т. п.) через А. Будем считать это множество конечным.

Каждое действие а е А характеризуется тремя параметрами — совершающим его агентом, видом действия и моментом времени t, в который совершается действие: а(1,у, I е N у е К, t е Т.

Далее, пусть на множестве действий задано бинарное отношение частичного порядка «а является причиной Ь» (или, что будем далее считать эквивалентным, «Ь является последствием а»), обозначаемое как а ^ Ь.

Пример такого отношения в реальной онлайновой социальной сети: а — создание поста, Ь — создание комментария к этому посту.

Будем считать, что бинарное отношение удовлетворяет следующим свойствам.

• Рефлексивность: для любого а е А справедливо а ^ а.

• Транзитивность: если а ^ Ь и Ь ^ с, то а ^ с.

• Антисимметричность: если а ^ Ь и Ь ^ а, то а и Ь совпадают.

зывать ее просто значимостью) является монотонно возрастающей функцией:

Рис. 1. Множество А = {а1? а2} и его последствия р(А) ={«!, а2, а3, а4, а5, а6, а7}

Если задано множество А с А, то можно определить множество всех действий, являющихся последствиями действий из А:

п(А) = {Ь е А | 3 а е А, а ^ Ь}.

Отметим, что для всех множеств А с А выполняется включение А с п(А), которое справедливо в силу рефлексивности бинарного отношения (рис. 1, где кругами обозначены действия, а стрелками — бинарные отношения).

2. УЧЕТ ПРЕДПОЧТЕНИЙ ЦЕНТРА

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

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

Ф: 2а ^ [0, +<»).

Естественно предположить, что если к некоторому множеству действий добавить еще действия, то значимость множества увеличится (по крайней мере, не уменьшится). Поэтому будем считать, что значимость множества действий (далее будем на-

если А с В, то Ф(А) < Ф(В).

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

3.ВЛИЯТЕЛЬНОСТЬ И ВЛИЯНИЕ

Считая заданной значимость каждого множества действий, определим влиятельность е(А) множества действий А с А как е(А) = Ф(п(А)).

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

Для определения влиятельности агента I е N определим сначала множество 8 с А всех совершенных им действий:

8 =

У а(1, у,

а е А, . е К, t е Т

Теперь определим влиятельность агента следующим образом (оставив то же обозначение е):

е, = Ф(л(8.)).

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

Если определена влиятельность агента, то можно задаться следующим вопросом: в какой мере один агент влияет на последствия действий другого? Или, говоря более кратко, каково влияние агентов друг на друга?

Введем показатель влияния агентов на основе влиятельности, который будем называть е-влиянием; е-влияние 1-го агента на у-го агента будем обозначать V,.. и вычислять как V,.. = е,.,/е., где

У У У )

е. = Ф(п(8,) п п(8у)).

(Если е. = 0, то, очевидно, е,.. = 0; в этом случае

} и

положим V,.. = 0.) Говоря неформально, V,.. означает

У У

долю влиятельности у-го агента, которая обусловлена действиями 1-го агента. Из очевидного соотношения

п

вытекает, с учетом свойства (1), что 0 < V ,.,. < 1. При этом V , = 1 для всех агентов с ненулевой влиятельностью, т. е. каждый агент влияет сам на себя.

Выполнение равенства V= 0 означает, что I- и у-й агенты никак не связаны друг с другом в при-

22

СОЫТВОЬ БС!ЕМСЕ8 № 4 • 2014

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

Введенные понятия влиятельности и е-влияния удовлетворяют трем свойствам, которые сформируем в виде утверждений 1—3.

Утверждение 1. Если множество последствий действий 1-го агента содержится в множестве последствий действий ]-го агента, то влиятельность 1-го агента не превосходит влиятельности ]-го агента:

л(5г) с л(5у) ^ Ег. < ег

в силу

Доказательство. п(8;) с л(8Ч-) ^ Ф(п(8;)) <

по определению

< Ф(п(8у.)) о е,- < еу,

Утверждение 2. Если е-влияние 1-го агента на любого из агентов не меньше Е-влияния на него ]-го агента, то влиятельность 1-го агента не меньше влиятельности ]-го агента:

ук е N % > 4 ^ щ > 4

Доказательство. Поскольку левая часть соотношения (4) выполняется для всех к, она справедлива также для к = г и к = у:

V.. > , V.. > ..

» ч' ч ч у '

Если еч- = 0, то неравенство е, > еу. очевидно. Пусть еч- > 0, при этом Уц. = 1. Тогда из выражения (5) с учетом 0 < Уц < 1 вытекает, что Уц = 1. Следовательно, е^ > 0, а значит е, > 0. Поэтому выполняется

V;; , е,7/ е, , е; , > 1 ^ ; > 1 ^ - > 1.

Утверждение 3. Если е-влияние 1-го агента на]-го агента больше Е-влияния]-го агента на 1-го агента, то влиятельность 1-го агента больше влиятельности ]-го агента:

V.. > V.. ^ Е. > Е..

Ч А г Ч

Доказательство. Если Уц > ц то Уц > 0, и, следовательно, Уц > 0. Поэтому, исходя из определения е-влияния и тождества е^ = е^, получаем:

уц е,-

У-е- = е- = У-е- ^ —- = — .

Ч Ч Ч Ч I л! .. е.

4. ПРИМЕРЫ ВОЗМОЖНОГО ПРИМЕНЕНИЯ

Описанная схема расчета влиятельности пользователей может быть применена (при наличии необходимых исходных данных и технологий их обработки) для расчета влиятельности пользователей конкретной социальной сети при различных предположениях о взаимосвязи действий и их значимости. Рассмотрим несколько примеров.

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

В этом случае можно ограничиться рассмотрением следующих видов действий:

1) создание поста (оригинального или репоста);

2) создание комментария к посту;

3) создание лайка посту;

4) создание лайка комментарию.

Тем самым, множество К состоит из четырех элементов: К = {1, 2, 3, 4}. Далее вместо действия «создание поста» и т. п. будем для краткости писать «пост» и т. п.

Будем считать, что бинарное отношение причинности а ^ Ь выполнено в следующих случаях:

• а — пост, Ь — комментарий к нему;

• а — пост или комментарий, Ь — поставленный ему

лайк;

• а — пост, Ь — его репост;

• а и Ь совпадают.

При описанных условиях значимость совокупности действий зависит аддитивно от каждого из них:

Ф(Л) = I Ф(а),

а е 5

где

Ф(а) =

если а — пост с упоминанием объекта, созданный в интервале т; ус, если а — комментарий к посту с упоминанием

объекта, созданный в интервале т; V, если а — лайк к посту или комментарию с упоминанием объекта, созданный в интервале т;

0, в остальных случаях.

Таким образом, мы получили все необходимые исходные данные для расчета влиятельности пользователей по формулам (2) и (3).

Пример 2. Предположим, что значимым для центра действием является подписка на какого-либо пользователя, осуществленная пользователем из некоторого множества М с N (содержательно М может быть множеством пользователей определенного возраста, места проживания и т. п.), причем значимость каждого такого действия задается положительной константой V.

В этом случае можно ограничиться рассмотрением следующих видов действий:

1) создание учетной записи пользователя (появление пользователя в сети);

2) подписка на пользователя.

Тем самым, множество К состоит из двух элементов: К = {1, 2}. Будем считать, что бинарное отношение причинности а ^ Ь выполнено в следующих случаях:

• а — создание учетной записи пользователя, Ь — подписка на этого пользователя;

• а и Ь совпадают.

Здесь, как и в примере 1, значимость совокупности действий зависит аддитивно от каждого из них:

Ф(£) = I Ф(а),

а е 5

где

Ф(а) =

_ IV, если а е М;

0, если а £ М.

Далее влиятельность можно рассчитать по формулам (2) и (3). Ясно, что в данном случае влиятельность трактуется как наличие большого количества подписчиков из заданного множества.

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

В этом случае можно ограничиться рассмотрением одного вида действий — создание поста (репоста), при этом множество К является одноэлементным.

Будем считать, что бинарное отношение причинности а ^ Ь выполнено в следующих случаях:

• а — пост, Ь — его репост;

• а и Ь совпадают.

Определим значимость Ф(£) множества £ как количество пользователей, создавших посты из множества £, содержащие ссылку на интересующую центр публикацию. Отметим, что в данном случае, в отличие от примеров 1 и 2, функция Ф(£) не является аддитивной (поскольку пользователь может создать несколько постов, содержащих ссылку на публикацию).

Далее, аналогично примерам 1 и 2, можно рассчитать влиятельности пользователей по формулам (2) и (3).

5. РАСЧЕТ ВЛИЯТЕЛЬНОСТИ ПОЛЬЗОВАТЕЛЕЙ НА ПРИМЕРЕ СЕТИ РДОЕБООК

Приведем пример расчета влиятельности пользователей русскоязычного сегмента сети БасеЪоок1. Будем считать, что значимыми для центра являются посты (оригинальные и репосты) внешних ссылок в БасеЪоок, а также комментарии и лайки к ним. При этом центр интересуют только действия, связанные с политическим кризисом на Украине и совершенные за период с середины ноября 2013 г. по середину января 2014 г. Значимость совокупности действий зависит аддитивно от каждого из них (см. пример 1 в § 4), а значимость отдельного действия определяется на основании того, как час-

Рис. 2. Распределение внешних ссылок по количеству пользователей, совершивших репост

1 Анонимизированные данные были предоставлены для исследований компанией «Лаборатория цифрового общества» (www.digsolab.com).

Рис. 3. Распределение пользователей сети ЕаееЬоок по их влиятельности

то они совершались в сети БасеЪоок (более редкое действие является более значимым).

Построим распределение внешних ссылок по числу разместивших их пользователей-«репосте-ров» (рис. 2; каждая точка показывает, каково количество пользователей, в постах которых содержится данное количество ссылок).

Оказывается, что только небольшое число внешних ссылок размещено действительно большим числом пользователей: всего лишь 377 внешних

24

СОЫТВОЬ БтЕМСЕБ № 4 • 2014

ссылок имеет число пользователей большее 500, среди них 152 внешние ссылки связаны с политическим кризисом на Украине (тематика ссылок определялась вручную). Этот факт дает основание рассчитать влиятельность только по наиболее популярным внешним ссылкам. Полученное распределение пользователей по влиятельности приведено на рис. 3 (каждая точка показывает, каково количество пользователей с данной влиятельностью).

Из рис. 3 видно, что лишь небольшое число пользователей обладают большой влиятельностью.

6. ВЛИЯТЕЛЬНОСТЬ МЕТА-ПОЛЬЗОВАТЕЛЕЙ

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

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

Пусть имеется мета-агент I (здесь I с N). Определим его влиятельность как

е1 = ф(л(57)),

где

Ь1 = и а(1, у, 0,

а еА, г е I, Ч е К, 1 е Т

а Е-влияние мета-агента I на мета-агента / (I с N, / с N) определим как vI/ = е^/е^-, где vIJ = Ф^^) п л(5/)).

Здесь разные мета-агенты могут содержать «общих» агентов, т. е. возможна ситуация непустого пересечения множеств I и /.

ЗАКЛЮЧЕНИЕ

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

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

ЛИТЕРАТУРА

1. Aggarwal C.C. Social Network Data Analytics. — Boston; Dordrecht; London: Kluwer Academic Publishers, 2011. — 502 p.

2. Everton S.F. Disrupting Dark Networks (Structural Analysis in the Social Sciences). — Cambridge: Cambridge University Press, 2012. — 482 p.

3. Губанов Д.А., Чхартишвили А.Г. Концептуальный подход к анализу онлайновых социальных сетей // Управление большими системами. — 2013. — Вып. 45. — С. 222—236.

4. Hubbell C. An input-output approach to clique identification // Sociometry. — 1965. — Vol. 28. — P. 377—399.

5. Freeman L.C. A set of measure of centrality based on between-ness // Sociometry. — 1977. — Vol. 40. — P. 35—41.

6. Agarwal N., Liu H., Tang L, Yu P.S. Identifying the influential bloggers in community // Proc. of the 1st ACM Intern. Conf. on Web Search and Data Mining. — 2008. — P. 207—217.

7. Weng J., Lim E.-P., Jiang J., He Q. Twitterrank: finding topic-sensitive influential twitterers // Proc. of the Third Intern. Conf. on Web Search and Web Data Mining. — 2010. — P. 261—270.

8. Akritidis L, Katsaros D., Bozanis P. Identifying Influential Bloggers: Time Does Matter // Proc. of the 2009 IEEE/WIC/ACM Intern. Joint Conf. on Web Intelligence and Intelligent Agent Technology. — 2009. — P. 76—83.

9. Губанов Д.А., Новиков Д.А., Чхартишвили А.Г. Модели влияния в социальных сетях // Управление большими системами. — 2009. — Вып. 27. — С. 205—281.

10. Friedkin N.E., Johnsen E.C. Social Influence Network Theory: A Sociological Examination of Group Dynamics. — Cambridge: Cambridge University Press, 2011. — 367 p.

11. Губанов Д.А., Новиков Д.А., Чхартишвили А.Г. Социальные сети: модели информационного влияния, управления и противоборства. — М.: Физматлит, 2010. — 228 с.

12. Kempe D., Kleinberg J., Tardos E. Maximizing the spread of influence through a social network // Proc of the 9th ACM SIGKDD Intern. Conf. on Knowledge Discovery and Data Mining. — 2003. — P. 137—146.

13. Granovetter M. Threshold Models of Collective Behavior // American Journal of Sociology. — 1978. — Vol. 83. — P. 1420—1443.

Статья представлена к публикации членом редколлегии чл.-корр. РАНД.А. Новиковым.

Губанов Дмитрий Александрович — канд. техн. наук, ст. науч. сотрудник,

(495) 334-87-61, И dmitry.a.g@gmail.com,

Чхартишвили Александр Гедеванович — д-р физ.-мат. наук, гл. науч. сотрудник,

(495) 334-90-51, И sandro_ch@mail.ru,

Институт проблем управления им. В.А. Трапезникова РАН.