Translate this page:
Please select your language to translate the article


You can just close the window to don't translate
Library
Your profile

Back to contents

Cybernetics and programming
Reference:

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
 

 

DOI:

10.7256/2306-4196.2016.5.20624

Received:

04-10-2016


Published:

29-01-2017


Abstract: The article focuses on the modeling of information dissemination in online social networks through reposts. The author considers the threshold model and an independent cascade model of information spreading in network. In the context of the independent cascade model author suggests a method of estimating the probability of spreading of information for each pair of connected users. The article reviews visible activity of online social network users that affect the likelihood for a particular user to read the information message, published by one of his friends, and then make a repost. The methodology of the study is related to the mathematical modeling of social processes. To build the model the author uses elements of set theory, graph theory. The main conclusion is that of the models considered (the threshold model and the independent cascade model), which both are special cases of same generalized model, it is the independent cascade model that most accurately reflects the logic of the process of information spreading in the online social network via reposts. The scientific novelty of the work lies in the fact that using the results for independent cascade model the author provides a method for the evaluation of information transmission probabilities for each pair of connected users.


Keywords:

social network analysis, modeling, independent cascades model, threshold model, information diffusion, information receiption probability, connected users, online social network, feed, repost


Введение

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

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

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

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

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

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

Пороговая модель

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

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

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

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

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

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

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

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

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

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

Модель независимых каскадов

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

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

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

_

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

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

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

где:

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

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

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

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

где:

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

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

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

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

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

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

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

` ` `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] получены значения порядка сотых долей процента для вероятности выкладывания пользователем ссылки на информацию.

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

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

References
1. Shalimov A.B. Dialektika sotsial'nogo i individual'nogo v sotsial'nykh setyakh // Psikhologiya i Psikhotekhnika. - 2013. - 11. - C. 1030 - 1036.
2. Gubanov D.A., Novikov D.A., Chkhartishvili A.G. Sotsial'nye seti: Modeli informatsionnogo vliyaniya, upravleniya i protivoborstva. M.: Fizmatlit. - 2010. - 228 s.
3. Granovetter M. Threshold models of collective behavior. American Journal of Sociology 83(6). - 1978. - p. 1420-1443.
4. Kempe D., Kleinberg J., Tardos E. Maximizing the Spread of Influence through a Social Network / Proceedings of the 9-th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. - 2003. - p. 137-146.
5. Bakshy E., Rosenn I., Marlow C., Adamic L. The role of social networks in information diffusion / Proceedings of the 21st international conference on World Wide Web. - 2012. - p. 519-528.