2.5 Математическая модель процесса заражения компьютеров пользователей социальных информационных сетей на основе теории случайных графов

Пусть Z₁,…,Z_t,… - независимые пуассоновские величины с одним и тем же средним . Предположим

.

Представить описанный только что процесс можно так. В начальный момент времени есть одна ЗК СИС. Потом она может заразить Z₁ новых компонент СИС. Заметим, что она может и не заразить ни одной новой компоненты СИС, т.к. величина Z₁ равна нулю с положительной вероятностью. На следующем шаге все повторяется: какая-то компонента (порядок роли не играет) может заразить Z₂ новых компонент СИС. И так далее. Имеют место следующие утверждения (из теории ветвящихся процессов) [98].

Теорема: Пусть . Тогда с вероятностью 1 процесс Y_t вырождается, т.е. .

Теорема: Пусть . Пусть - единственное решение уравнения . Тогда процесс Y_t вырождается с вероятностью , т.е. .

Пусть дана СИС, которая определяется графом G=(V,E): конкретный граф, не случайный, где V – множество вершин графа (множество пользователей СИС), Е – множество ребёр графа (множество связей между пользователями СИС). Зафиксируем какую-нибудь его вершину . Назовем её «заражённой», а все остальные вершины - «нейтральными». Выберем среди нейтральных вершин всех соседей вершины v₁. После этого объявим её соседей – «подверженными заражению», а все остальные вершины - нейтральными. Снова зафиксируем какую-нибудь подверженную заражению вершину V₂. Выберем всех ее соседей среди нейтральных. Продолжая этот ветвящийся процесс, мы, в конце концов получим множество подверженных заражению вершин [83,84].

Обозначим число зараженных вершин в момент времени t через Y_t, число нейтральных вершин - через N_t, а число подверженных заражению от очередной заражённой вершины - через Z_t. Тогда,

.

Разумеется, все введенные величины зависят от графа G и от последовательности выбираемых вершин v₁,... Если граф G считать случайным, то при любом выборе вершин v₁,... получатся случайные величины Y_t, N_t, Z_t на пространстве G(n,p). Сразу понятно, что Z_t не является пуассоновской. Тем не менее, она похожа на пуассоновскую, а именно, имеет биномиальное распределение с «числом испытаний» N_t и вероятностью «успеха» р. Здесь имеет место равенство для Y_t

.

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

Рассмотрим случай при с < 1. Предположим , где - константа. Будем доказывать, что с большой вероятностью каждая из компонент случайного графа имеет размер не больше t₀. Но размер компоненты - это момент вырождения процесса Y_t на случайном графе. Значит, интересующее нас утверждение можно записать в следующем виде:

.

Поскольку

достаточно найти такое , при котором

;

(с учетом асимптотики )

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

.

Поскольку с < 1, нижний предел интегрирования имеет порядок . Значит, весь интеграл не превосходит величины . Выберем таким, чтобы оказалось меньше, чем .

Теперь рассмотрим случай с > 1.

Этот случай гораздо сложнее предыдущего. Здесь ветвящийся процесс на графе нужно «запускать» не один раз, а несколько. Нужно, чтобы вет­вящийся процесс на графе не вырождался даже при . Иными словами, необходимо, чтобы

.

Здесь . Значит, при выполнено

.

Применим центральную предельную теорему к

.

Интегрирование пойдет от минус бесконечности до

.

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