Independent cascade model of reposts spreading in online social network

Toropov Boris Andreevich PhD in Technical Science Associate Professor at the IT Department of the Academy of Management of the Ministry of Internal Affairs of the Russian Federation 125171, Russia, g. Moscow, ul. Z.i A. Kosmodem'yanskikh, 8 torbor@mail.ru Other publications by this author

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

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

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

Полученный по данной технологии граф формируется на основе множества вершин U = {u₁, u₂, ... u_n} – пользователей сети и квадратной матрицы сопряженности g={0,1}^nxn, каждый элемент которой принимает значение либо 1 либо 0, в зависимости от того добавил ли пользователь i (номер строки в матрице g) в друзья пользователя j (номер столбца в матрице g) или не добавил соответственно.

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

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

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

Основой элемент рассматриваемой модели – это механизм взаимодействия соседних узлов сети, одни из которых уже активировались (в рассматриваемом случае – сделали репост определенного сообщения), а другие находятся в неактивном состоянии. Таким образом, необходимо смоделировать условия, в которых происходит успешное прохождение сообщения от u_j к u_i в случае наличия между ними непосредственной связи, g_ij = 1. Существует достаточно большое количество моделей распространения влияния в социальных сетях, их типология, в частности, описана в ^[2], где среди прочих приведены модели с линейными порогами.

Данный класс моделей достаточно хорошо известен, одна из первых посвященных им работ ^[3] датирована 1978 г., обобщенный вид приведен в ^[4]. Такие модели предполагают, что узел социальной сети (вершина графа) может находиться либо в активном, либо в неактивном состоянии. Причем для каждого узла возможен переход из неактивного состояния в активное, но не наоборот.

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

Согласно пороговой модели, узел u_i находится под влиянием каждого из своих соседей u_j|g_ij=1 таким образом, что сумма этих взвешенных влияний a_j|g_ij не превышает 1, а неактивные соседи влияния не оказывают совсем:

`sum_(j)g_(ij)a_(j)<=1`

Каждый узел обладает заданным порогом активации `theta_(i)in[[0,1]]` , который может задаваться случайно, либо на основании различных характеристик узла u_i (предшествующая активность, оценка подверженности внешним влияниям, убеждения, опыт и т.д.), либо порог может быть задан равным, например, 1/2 или 1/3, для всех узлов. Модель носит имитационный характер и заключается в том, что выбирается некоторое множество узлов `U_(0)subU`, которые изначально активны и являются инициаторами процесса распространения информационного сообщения (публикуют запись на своей страничке, откуда она попадает в ленты друзей). Сам процесс разворачивается детерминировано дискретными шагами. На каждом шаге t все узлы, которые были активны на t-1, остаются активными и плюс к этому активируются те, для которых выполняется условие:

`sum_(j)g_(ij)a_(j)<=theta_(i)`

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

Сложность в применении данной модели состоит в том, что она предполагает длящееся влияние на каждого пользователя u_i со стороны соседей-друзей u_j|g_ij=1, которое проявляется на каждом шаге t имитации процесса. Однако в реальных ОСС пользователь, как правило, одно и то же сообщение размещает один раз. Те из его друзей, кто данное сообщение увидел, принимают решение публиковать его на своей страничке или не публиковать, причем от повторного появления этого сообщения решение, скорее всего, не изменится. Измениться оно может в случае появления аналогичного сообщения от другого, возможно, более влиятельного пользователя.

Для имитации такого процесса хорошо подойдет другой близкий класс моделей, названных в ^[4] моделями независимых каскадов (Independent Cascade Model). Там же предлагается обобщенная модель, для которой пороговая модель и модель независимых каскадов являются частными случаями. В рамках данной статьи рассмотрим модель независимых каскадов применительно к репостам в ОСС.

В простейшем варианте данной модели процесс распространения информации инициируется подмножеством первоначально активных узлов `U_(0)subU` . Далее процесс вновь разворачивается пошагово. Для каждого вновь активированного на шаге t узла срабатывает правило, в соответствии с которым он может активировать каждый из узлов-соседей с заданной вероятностью. Эта вероятность p_ij – параметр системы, заданный для каждой пары соседних узлов в сети. Причем если на шаге t неактивный узел u_j становится соседом нескольких вновь активированных узлов, то каждый из них поочередно имеет шанс произвести его активацию (порядок очередности значения не имеет). Если активация прошла успешно, то со следующего шага t+1 данный узел считается активным. Вне зависимости от этого все узлы, активные начиная с шага t, больше не имеют возможности участвовать в процессе активации соседних узлов. Процесс продолжается до тех пор, пока сохраняется хотя бы одна возможная попытка активации.

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

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

Однако некоторые проявления видимой (наблюдаемой) активности пользователей в ОСС могут оказаться полезны. Так в ^[5] показано, что, например, пользователь Facebook в 2,83 раза чаще готов делиться с другими ссылкой, полученной от того, кто ранее оставил 3 комментария к его сообщениям, чем от того кто комментариев прежде не оставлял. То есть можно предположить, что объем направленных на пользователя условно позитивных воздействий со стороны другого пользователя (конструктивные комментарии, репосты, лайки, упоминания и ссылки, сам факт добавления в друзья, оформление подписки, отправка виртуальных подарков и т.п.) прямо коррелирует с последующим влиянием на адресата этих воздействий. Это представляется полезным для моделирования вероятности p_ij успешной доставки сообщения и последующего репоста и первая составляющая модели будет выглядеть следующим образом:

`(c_(ij))/(sum_(v)g_(vj)c_(vj)),`

где:

c_ij – видимая активность пользователя u_i, направленная на пользователя u_j. Причем принимается, что `c_(ij)>=1` , так как сам факт добавления одним пользователем другого в друзья (что является в рассматриваемом случае основанием для появления ребра ij графа связей) засчитывается за факт активности, направленной на пользователя u_j;

`sum_(v)g_(vj)c_(vj)` - суммарная активность всех друзей пользователя u_j, направленная на него.

Кроме того, логично предположить, что вероятность p_ij будет прямо пропорциональна ключевому свойству самого пользователя, а именно его общей активности в ОСС по размещению сообщений:

`(c_(j))/(sum_(v)c_(v)),`

где:

c_j – общая активность пользователя u_j;

`sum_(v)c_(v)` - суммарная активность всех пользователей ОСС.

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

Особенное значение в этом свете приобретает доля активности напрямую связанная с размещением репостов:

`(r_(j))/(c_(j)),`

где: r_j – число репостов, сделанных пользователем j.

Таким образом, предлагается модель вероятности p_ij успешно доставить сообщение от пользователя u_i к пользователю u_j так, чтобы u_j сделал репост этого сообщения:

` ` `p_(ij) = (c_(ij))/(sum_(v)g_(vj)c_(vj))xx(c_(j))/(sum_(v)c_(v))xx(r_(j))/(c_(j)) = (c_(ij))/(sum_(v)g_(vj)c_(vj))xx(r_(j))/(sum_(v)c_(v)) `

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

Предлагаемая модель может быть верифицирована на реальных данных путем расчета r_ji/с_i за достаточно длительный период наблюдения, поскольку r_ji, число репостов сообщений пользователя u_i со стороны пользователя u_j, для большинства участников ОСС будет нулевым или очень малым.

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