Методическое обеспечение моделирования эпидемических процессов в социальных сетях

3.1 Микромоделирование эпидемического процесса инфицирования пользователя социальной сети

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

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

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

3. В начальный момент времени формируется множество пользователей-вершин сети согласно статистическим данным. Свойства и параметры пользователей определяются на стадии формирования всего множества.

4. Все вершины разбиваются на типы, определяющие его отношение к инфицированию.

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

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

Опираясь на также известные переходы между состояниями [73-90], формализуем состояния, которые будем использовать в микрофрактале:

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

2. Стадия, когда пользователь позитивно воспринимает контент (состояние латентного заражения E) или остается к нему равнодушным, т.е. пребывает в исходном состоянии S.

3. Далее из состояния E пользователь может перейти в другие состояния: иммунизированное, приобретенное самостоятельно (состояние M) или посредством модерации (состояние A); состояние, когда он становится распространителем инфекции (состояние I). При этом пользователь может остаться в состоянии E.

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

Определим основные множества состояний эпидемического процесса:

– мощность множества восприимчивых вершин ;

– мощность множества вершин, находящихся в латентной стадии ;

– мощность множества инфицированных вершин ;

– мощность множества неактивных вершин ;

– мощность множества иммунизированных вершин ;

– мощность множества вершин выздоровевших с помощью администратора .

Тогда микро-фрактал эпидемического процесса примет вид, представленный на рисунке 3.1.

1-PAM-PI

1-PE

1-PR

PAM

Рисунок 3.1 – Микро-фрактал эпидемического процесса

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

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

(3.1)

Рисунок 3.2 – Эквивалентный граф эпидемического процесса

Здесь уместно провести проверку корректности предложенной модели, просуммировав полученные в формуле (3.1) вероятности. В результате имеем:

что и требовалось доказать.

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

M|AM|=[k ]=[k ];

(3.2)

M|E|=[k

]=[k

];

M|I|=[k ]=[k ];

M|R|=[k ]=[k ];

M|S|=[k ]=[k( )],

где [.] – оператор извлечения целой части; М[.] – оператор математического ожидания.

При этом для выражений (3.2) очевидно должно выполняться условие, что:

M|AM|+M|E|+M|I|+M|R|+M|S|=k.

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

Отметим, что в малоразмерных (с точки зрения степени k) слоях произведение kp<1 и [kp]=0. Так, для сети Facebook по рубрике «Политика» P₃@24•10^-5должно быть k≥10⁴[]. Только в случае введения контента в такой слой можно рассчитывать на 2 зараженные вершины. В свою очередь, для сети YouTube по рубрике «Люди» имеем P₃@0,01, и надо использовать слой с k≥100, чтобы получить хотя бы одну инфицированную вершину. Можно заметить, что, чем больше сеть, тем меньше искомые вероятности, и тем более высокостепенные слои требуется использовать для инфицирования.

Составим матрицу разрешенных переходов для микромодели.

В данной микромодели состояния AMи R являются конечными, и в динамики эпидемии не рассматриваются.

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

Таблица 3.1 – Разрешенные переходы

Стартовое состояние контактирующей с инфекцией вершины	Итоговое состояние после контакта с инфекцией
AM	AM
E	E, I, AM
I	I, R
R	R
S	S, E

Таблицу 3.1 можно обосновать следующими умозаключениями. При контакте инфекции с вершиной в состоянии AM, вершина имеет иммунитет к данной инфекции и, следовательно, она останется в своем состоянии. Если вершина находится в латентном состоянии E, то подразумевается, что она уже была подвержена инфицированию. В данном случае вершина может передать инфекцию другой вершине, при этом перейти в зараженное состояние I, либо получить иммунитет к инфекции или подвергнуться удалению со стороны администратора, либо же остаться в латентном состоянии E. Зараженная инфекцией вершина, находящаяся в состоянии I, продолжит излучать инфекцию и обусловит переходы смежных вершин в инфицированное состояние. Также допустимо, что в состоянии I вершина может перейти в состояние Rсамостоятельно, либо под воздействием модерации. Вершины в состоянии R не участвуют в процессе распространения эпидемического процесса и не изменяют своего состояния при контакте. При восприимчивом состоянии вершины S она может подвергнуться инфекции и перейти в состояние латентного заражения E, либо остаться в здоровом состоянии S, при условии, что инфекция е коснулась данной вершины или же вершина оказалась невосприимчивой к данному типу инфекции.

– вероятность остаться в восприимчивом состоянии;

– вероятность перехода восприимчивого узла в латентное состояние (состояние заражения);

– вероятность перехода узла из латентного состояния в зараженное;

– вероятность остаться в латентном состоянии

– вероятность продолжения распространения инфекции от зараженного;

– вероятность перехода из латентного состояния в выздоровевшее, с иммунитетом;

– вероятность перехода из инфицированного состояния в неактивное состояние;

- доля восприимчивых вершин в s – слое.

где – количество узлов в слое ;

Множество восприимчивых вершин определяется на входе эпидемического процесса.

Общая вероятность инфицирования с входа на выход будет равна:

или

Так как замкнутые контуры в данном случае отсутствуют.

Тогда число вторичных источников инфекции на выходе слояs будет равно:

где - количество атакуемых (из k - слоя) вирусом вершины s - слоя.

На основе данного программного обеспечения можно исследовать социальные сети на предмет определения вероятностей перехода состояний эпидемического процесса. Анализ источников [73-90] позволяет свести все полученные вероятности в таблицы 3.2-3.8.

Таблица 3.2 – Сети для общения [73, 79, 81, 89].

Тематика
Кошки	5.98 ·	4.33 ·	2.68 ·	9.49 ·
Музыка	3.36 ·	1.34	4.98 ·	6.43 ·
Еда	3.43 ·	1.53 ·	8.23 ·	5.47 ·
Открытые рейсы	3.27 ·	8.09 ·	2.71 ·	1.54

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

Таблица 3.3 – Сети для обмена медиа-контентом [76, 84].

Тематика
Пейзаж	0,081	0,127	0,0061	0,00771
Битва	0,313	0,0575	0,0278	0,0472

Продолжение таблицы 3.3

Люди	0,33	0,0783	0,1037	0,119
Альбом	0,171	0,6319	0,6203	0,0724
Жанр	0,136	0,1314	0,0094	0,0369

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

Таблица 3.4 – Сети для отзывов и обзоров [74, 78].

Тематика
Товар	0.1794	0.099	0.501	0.00924
Ресторан	0.1266	0.045	0.453	0.0087
Билеты	0.152	0.083	0.428	0.0081
Место	0.19992	0.1494	0.402	0.0076
Низкая цена	0.1082	0.083	0.209	0.0415

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

Таблица 3.5 – Сети для коллективных обсуждений [80, 83, 85, 86, 87].

Тематика
Цена на акции	0.6798	0.0045	0.6198	0.1226
Продажи	0.7270	0.0081	0.6320	0.1388
Низкая цена	0.7506	0.0059	0.7262	0.1419
Удобства	0.7914	0.0078	0.6433	0.1230
Здравоохранение	0.7677	0.0065	0.7190	0.1361
Трудовой кодекс	0.7433	0.0088	0.7510	0.1324
Заработная плата	0.6000	0.0053	0.5209	0.1524

В сетях коллективных обсуждений (анализ таблицы 3.5) высокие вероятности заражения и удаления (более 0.5 – 0.6). Это объясняется тем, что каждый пользователь имеет право высказаться на форуме или блоге и его рассуждения будет использовано в репосте, как с негативной, так и позитивной стороны. Однако пользователи сетей коллективных обсуждений не приемлют навязчивого контент, поэтому и вероятность удаления также высока.

Таблица 3.6 – Сети для авторских записей [80, 88, 90].

Тематика
Ядерное оружие	0.0062	0,9500	0,4379	0.0034
Война в Ираке	0.0180	0,9115	0,4739	0.2565
Здравоохранение	0.0039	0,5696	0,5761	0.2995
Барак Обама	0.0034	0,2212	0,7929	0.0937
Джон Маккейн	0.0076	0,8078	0,7190	0.2232

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

Таблица 3.7 – Сети социальных закладок [75, 82].

Тематика
Разработка	0.267	0.082	0.055	0.102
Открытые ресурсы	0.192	0.026	0.052	0.032
Статья	0.134	0.014	0.055	0.014
Бизнес	0.268	0.166	0.070	0.136
Социум	0.291	0.086	0.058	0.066
Совместная работа	0.090	0.036	0.025	0.029

Таблица 3.8 – Сети по интересам [77, 79, 89].

Тематика
Статьи	0.109	0.023	0.032	0.027
Ресурсы	0.206	0.036	0.048	0.026
Сотрудничество	0.167	0.083	0.049	0.060
Композитор	0.081	0.011	0.033	0.007
Сообщество	0.192	0.026	0.052	0.032

Анализ таблицы 3.7 и 3.8 позволяет сделать вывод, что в сетях социальных закладок в сетях социальных закладок и в сетях по интересам все вероятности соизмеримы и эпидемический процесс распространения контента протекает равномерно.

3.2 Микромоделирование процесса инфицирования пользователя в противоборстве двух контентов

Рассмотренная выше микромодель относится к моно-ситуации, когда в сети распространяется один контент. Очевидно, что возможны и другие варианты, например – появление второго(даже альтернативного) контента, что является нормой сетевого противоборства. Здесь надо рассматривать вероятность (рисунок 3.9) переходов для разнотипных контентов. К примеру, для сети Facebook можно проанализировать таблицу 3.9.

Таблица 3.9 – Вероятности переходов для сети Facebook

Рубрики	Вероятности P₃
Политика	@24•10^-5
Наука	@24•10^-7

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

1. В ходе эпидемического процесса вершина может принимать и распространять только один контент, а, следовательно, находиться только в одном состоянии.

2. В ходе эпидемического процесса вершина может принимать и распространять несколько контентов, а, следовательно, находиться в нескольких состояниях.

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

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

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

Вход эпидемии

Рисунок 3.3 – Модель противоборства контентов при одном состоянии вершины

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

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

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

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

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

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

Рисунок 3.4 – Модель противоборства контентов при возможности нескольких состояний вершины

Иммунизация сети также требует анализа. Здесь возможны две ситуации:

1. Вершина, иммунизированная к одной инфекции, сталкиваясь с другой инфекцией, теряет иммунитет и становится уязвима к обеим инфекциям.

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

Второй подход опять-таки увеличивает количество состояний и переходов.

Рассмотрим эти ситуации. Пусть вершина имеет иммунитет по отношению к инфекции (рисунок 3.5), тогда при воздействии инфекции она потеряет свой иммунитет и снова станет восприимчива к инфекции . Такой вариант возможен только, если вершина может находиться в одном состоянии. Если потерявшая иммунитет вершина имеет смежную вершину с инфекцией то имеет место сценарий противоборства представленного на рисунке 3.3. Если имеем дело со случаем, когда иммунитет сохраняется (рисунок 3.6), о противоборстве стоит забыть. Однако вершина одновременно может иметь иммунитет по отношению к одной инфекции, но при этом стать излучателем по отношению к другой, что представляет более сложную задачу с точки зрения моделирования. Помимо этого, вершина может не стать излучателем и получить иммунитет к обеим инфекциям, либо стать неактивной и перейти в состояние R.

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

Вход эпидемии

Рисунок 3.5 – Модель с потерей иммунитета

Вход эпидемии

Рисунок 3.6 – Модель с сохранением иммунитета

Таблица 3.10 – Результаты столкновения контентов в вершине сети

Состояние вершины сети, индуцированные контентом К1	Ожидаемые состояние вершины сети при контакте с контентом К2	Результирующее состояние вершины сети при столкновении контентов К1 и К2	Условия получения рассматриваемого результата
1	2	3	4
АМ₁	АМ₂	АМ₁	состояние AM – конечное в рассмотрении эпидемии
	Е₂	АМ₁
	I₂	АМ₁
	R₂	АМ₁
	S₂	АМ₁

Продолжение таблицы 3.10

1	2	3	4
Е₁	АМ₂	Е₁
		I₁	>
		АМ₁
	Е₂	Е₁
		I₁	>
		АМ₁
	I₂	Е₁
		Е₂
		I₁
		АМ₁
	R₂	Е₁
		I₁	>
		АМ₁
	S₂	Е₁
		I₁	>
		АМ₁

Продолжение таблицы 3.10

1	2	3	4
I₁	АМ₂	I₁
	АМ₂	R₁
	Е₂	I₁
	Е₂	R₁
	I₂	I₁

			>
	R₂	I₁
	R₂	R₁
	S₂	I₁
	S₂	R₁
R₁	АМ₂	R₁	состояние R – конечное рассмотрении эпидемии
	Е₂	R₁
	I₂	R₁
	R₂	R₁
	S₂	R₁
S₁	АМ₂	S₁	АМ₂ – конечное состояние
	Е₂	S₁	Вершина в Е₂не излучает
	I₂	S₁
	I₂	Е₂	>
	R₂	S₁	R₂ – конечное состояние
	S₂	S₁	Обе вершины здоровы

Анализ таблицы 3.3 позволяет сказать, что динамика развития противоборства не зависит от состояний AMи R, так как они конечны. Она зависит от сопротивления состояний Iи Eв вершине. Отметим, что противоборство будет иметь место не только для здоровых вершин S, но и для вершин в состояниях латентного заражения и инфицирования. При этом вероятности принять и распространять другой контент уменьшается, так как имеет место произведение вероятностей, каждая из которых менее 1.

3.3 Алгоритмы макромоделирования эпидемического процесса в сети и его риск-анализ

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

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

Рисунок 3.7 – Многослойное представление неоднородных сетей

Количественную оценку слоев можно определить через общее количество вершин сети N и P(k) – законом распределения степени ее вершин:

. (3.3)

Так, k_min может достигать 1, а k_max представляется возможным найти из следующего соотношения:

. (3.4)

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

k_max = lnN. (3.5)

Для степенного закона:

, (3.6)

где .

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

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

(3.7)

Усредним эти данные:

(3.8)

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

Отразим сущность разбиения взвешенной сети по степени вершин на рисунке (Рисунок 3.8).

Рисунок 3.8 – Разбиение на слои взвешенной сети

Разброс ценности вершин во взвешенной сети можно определить по формуле:

где и ,в свою очередь, определяются по формулам:

(3.9)

(3.10)

показывает, что через вершину трафик не проходит, а, следовательно, вершина «оторвана» от сети, то есть находится в закрытом кластере. Такая ситуация не рассматривается при моделировании. Значение показывает максимальный нормированный трафик, проходящий через вершину. Он равен единице в случае если в сети присутствует только одна вершина. Такой вариант, тоже выходит за рамки рассмотрения.

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

, (3.11)

где n – это количество вершин слоя k.

Для реальных сетей послойная формализация взвешенной сети иерархичный вид. Все вершины располагаются по убыванию степеней сверху вниз. Отразим на рисунке произвольную сеть (рисунок 3.9) и ей послойную формализацию. (Рисунок 3.10).

Рисунок 3.9 – Произвольная сеть

Рисунок 3.10 – Послойная формализация произвольной сети

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

- каскадно вверх (от инфицированного узла слоя k к узлам высших слоев (k+1), … ,k_max;

- каскадно вниз (от инфицированного узла k-слоя к узлам низших слоев (k-1), … ,k_min;

- вдоль слоев доступа (от одного инфицированного узла k-слоя к другим узлам соседних слоев доступа);

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

Рассмотрим варианты распространения эпидемий, а также оценим риски инфицирования сети и шансы.

Как было уже оговорено, время модели дискретно. Это относится и к макромоделированию. Каждая из вершин находится в одном из состояний. Напомним, к ним относятся:

– мощность множества восприимчивых вершин ;

– мощность множества вершин, находящихся в латентной стадии ;

– мощность множества инфицированных вершин ;

– мощность множества неактивных вершин ;

– мощность множества иммунизированных вершин ;

– мощность множества вершин выздоровевших с помощью администратора .

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

При рассмотрении эпидемического процесса, необходимо, прежде всего, отметить, что вероятности переходов между состояниями вершины k-слоя будут равны:

для инфицирования

для латентного заражения

Для удаления вершины

Для иммунизации

Во взвешенной сети ценность вершины определяется также количеством кратчайших путей проходящих через нее. Чем больше кратчайших путей проходит через вершину, тем выше ее важность во взвешенной неоднородной социальной сети и тем она интересней, при вредоносной атаке[85]. Ценность вершины можно найти по следующей формуле:

где – кратчайший путь, проходящий через вершину i;

– кратчайший путь между всеми вершинами сети.

Таким образом, можно сказать, что объектом атаки целесообразно выбирать вершины, для которых ценность стремится к единице ( ).

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

- для вершины (3.12)

где – все входящие и выходящие ребра вершины .

Проиллюстрируем ситуацию рисунком 3.11

Р_k

…

k-слой

Рисунок 3.11 – Модель поражения вирусом вершины в k-слое

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

(3.13)

где для каждого K следует выполнить округление с тем, чтобы

(3.14)

Степень s будет находиться в границах

(3.15)

Если , то вершины k-слоя тяготеют в своих связях к слоям большей, чем k, степени (s>k). Когда , , они тяготеют к слоям s<k. Первый случай характерен для социальных сетей, а второй – чаще наблюдается в технологических сетях.

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

-для каскадно-вверх ориентированной инфекции

(3.16)

-для каскадно-вниз ориентированной инфекции

(3.17)

-для веерно расходящейся инфекции

(3.18)

-наконец, для ориентированной вдоль слоя инфекции: s=k.

Последний случай имеет место быть, если в k-слое больше, чем k вершин, т.е.

(3.19)

Теперь обратим наше внимание, что в рамках нашего моделирования все вероятности переходов между состояниями априорно известны. Для нас требуется оценить долю трафика, контролируемого каждой вершиной и группами вершин для каждого из состояний S, E, I, R, AM. По аналогии обозначим оператор взвешивания . Тогда будем иметь взвешенный трафик:

для множества восприимчивых вершин ,

для множества латентно зараженных вершин ,

для множества инфицированных вершин ,

для множества неактивных вершин ,

для множества иммунизированных вершин .

3.4 Методическое обеспечение риск-анализа

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

(3.20)

Учитывая формулу (3.44) риск можно переписать в другом виде:

(3.21)

Соответственно шанс можно выразить как:

(3.22)

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

(3.23)

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

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

Интересно заметить, что сумма шансов и риска представляет собой инвариант, заданный точностью репрезентативной выборки из сети. Так, в случае, когда мы при выборке допускаем 5% утрату трафика, вышеуказанный инвариант составит 0,95.

Когда же мы рассматриваем конкурирующие контенты, при оценке шанса и риска суммирование следует осуществлять по множествам вершин, состояние которых определяется по отношению к конкретному контенту. Так, для двух конкурирующих контентовК₁и К₂ можно записать:

(3.24)

(3.25)

Прогноз сравнительной привлекательности контентов в сети будет складываться из разности

(3.27)

на каждом шаге моделирования процесса.

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

(3.28)

которая также характеризует шансы дальнейшего распространения конкурирующих контентов.

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

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

3.5 Методическое обеспечение осуществление репрезентативности выборки

Пусть дан связный ориентированный простой нагруженный граф G=(V,E, U) с неотрицательной вещественной весовой функцией на ребрах U, представленный уже квадратной матрицей взвешенной центральности . Требуется пересортировать матрицу таким образом, чтобы можно было легко удалить вершины с наименьшим проходящим через них трафиком. То есть для которых выполняется условие:

(3.29)

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

а) достоверность – сжатие должно сохранять информацию о свойствах исходной сети;

б) скорость – выполнение всех этапов в сумме должно требовать меньше времени, чем решение задачи известными способами на исходной сети.

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

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

	j	s	k

i

s

k

будет выполняться условие:

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

Теперь требуется определить общий трафик сети. Он будет определяться как сумма всех диагональных элементов.

Где - объем трафика сети, n–количество вершин сети.

Тогда если задать количество трафика равное 5%, которое можно потерять в результате репрезентативности сети, получим трафик репрезентативной сети

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

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

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

Рисунок 3.12 – Трехмерная иллюстрация исходной сети

Так как по сути при получении репрезентативной выборки мы делаем усечение, то для выборки контур сместится по оси аппликат вверх, оставляя под собой вершины с малым удельным трафиком. Эту картину иллюстрирует рисунок 3.13. Сплошной линией опять-таки показывается контур сети.

Рисунок 3.13 – Трехмерная иллюстрация репрезентативной выборки

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

(3.30)

Так как доля малостепенных вершин в выборке уменьшается по сравнению с исходной сетью, то, очевидно, закон распределения степеней также претерпевает изменения. Начальный участок закона должен стать ниже исходного. Однако, изменение количества малостепенных вершин влечет за собой изменение среднестепенных вершин (рисунок 3.14).

Рисунок 3.14 – Мутация закона распределения степени вершин при осуществлении репрезентативной выборки

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

Дата добавления: 2018-04-04; просмотров: 346; Мы поможем в написании вашей работы!

Поделиться с друзьями:

⇐ Предыдущая 1 2 345 6 7 8 Следующая ⇒

Мы поможем в написании ваших работ!