Распространение эпидемий в реальных сетях: взгляд через собственные значения

Ян Ван, Дипаян Чакрабарти, Чэньси Ван, Христос Фалутсос

Университет Карнеги-Меллон, Питтсбург, США

Аннотация

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

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

1. Введение

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

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

2. Ранние модели и их ограничения

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

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

Pastor-Satorras и Vespignani изучали распространение эпидемий в сетях со степенным законом и предложили свою модель (модель SV) для топологии Барабаши–Альберта (BA). Однако их модель критически зависит от предположения, что показатель степени γ = 3, что не всегда верно для реальных сетей, что приводит к неточным прогнозам.

3. Предлагаемая модель

Наша модель не предполагает ни однородной связности, ни какой-либо конкретной топологии. Мы рассматриваем связную сеть G = (N, E), где N — количество узлов, а E — множество ребер. Мы предполагаем универсальную скорость заражения β для каждого ребра, соединенного с инфицированным узлом, и скорость излечения δ для каждого инфицированного узла.

Мы определяем вероятность p_i,t того, что узел i инфицирован во время t. Вероятность того, что узел i не получит инфекцию от своих соседей во время t, обозначается как ζ_i,t и вычисляется как произведение вероятностей по всем соседям.

На основе этих определений мы выводим рекуррентное соотношение для вероятности того, что узел остается здоровым, и, следовательно, для p_i,t. При заданной топологии сети и значениях β и δ, мы можем численно решить это уравнение и получить эволюцию во времени инфицированной популяции η_t.

Эксперименты на реальных (граф маршрутизаторов Oregon) и синтезированных (BA, Эрдёша–Реньи) сетях показали, что наша модель дает более точные прогнозы, чем модели KW и SV, и является обобщающей для них.

4. Эпидемический порог и собственные значения

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

Мы представляем общую теорию для произвольных графов: эпидемический порог τ определяется как τ = 1 / λ_1,A, где λ_1,A — наибольшее собственное значение матрицы смежности A сети.

Теорема 1 (Эпидемический порог). Если эпидемия затухает, то обязательно верно, что β/δ < 1 / λ_1,A.

Теорема 2 (Экспоненциальное затухание). Когда эпидемия затухает (β/δ < 1 / λ_1,A), вероятность заражения экспоненциально убывает со временем.

Наше условие порога обобщает известные частные случаи:

• Для однородной или случайной сети Эрдёша–Реньи λ_1,A ≈ <k> (средняя степень), и наш порог совпадает с классическим τ = 1/<k>.
• Для звездообразной топологии λ_1,A = √d (где d — степень центрального узла), и наше условие порога дает критическую скорость излечения δ_c = β√d.
• Для бесконечной сети со степенным законом λ_1,A стремится к бесконечности, поэтому порог стремится к нулю, что согласуется с предыдущими исследованиями.

Сравнение с моделью Pastor-Satorras (τ_SV = <k>/<k²>) на реальных данных (граф Oregon) показало, что наше условие порога, основанное на λ_1,A, гораздо точнее отражает реальное поведение системы.

5. Обсуждение — общность нашего условия порога

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

На рисунке 5 показано распространение инфекции во времени в 100-узловой звездообразной сети с β=0.016. Наша модель прогнозирует критическое значение δ_c = 0.16. Экспериментальные данные подтверждают это прогноз: при δ > 0.16 инфекция затухает, при δ < 0.16 — достигает установившегося состояния, а при δ = 0.16 наблюдается фазовый переход, при котором число инфицированных убывает как t^-1.

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

6. Заключение

Основные вклады нашей работы заключаются в следующем:

1. Мы предложили новую, более точную и общую модель распространения вирусов в сетях (уравнение 6).
2. Мы показали, что свойства распространения вируса в произвольном графе можно охарактеризовать одним параметром — наибольшим собственным значением его матрицы смежности. Мы предложили точное условие эпидемического порога τ = 1/λ_1,A, которое верно независимо от топологии сети.
3. Мы доказали, что ниже эпидемического порога количество инфицированных узлов в сети экспоненциально убывает до нуля.

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

Приложение

Лемма 1 (Собственные значения матрицы системы). i-е собственное значение S имеет вид λ_i,S = 1 – δ + βλ_i,A, и собственные векторы S совпадают с собственными векторами A.

Доказательство: Пусть u_i,A — собственный вектор A, соответствующий собственному значению λ_i,A. Тогда по определению Au_i,A = λ_i,Au_i,A. Теперь Su_i,A = (1 – δ)u_i,A + βAu_i,A = (1 – δ)u_i,A + βλ_i,Au_i,A = (1 – δ + βλ_i,A)u_i,A. Таким образом, u_i,A также является собственным вектором S с собственным значением (1 – δ + βλ_i,A).