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

005007433

Утакаева Ирина Хайрлыевна

Математические модели инфекционной динамики

на основе предфрактальных графов

05.13.18 - Математическое моделирование, численные методы и комплексы программ

1 2 ЯНВ 2012

АВТОРЕФЕРАТ

диссертации на соискание учёной степени кандидата физико-математических наук

Ставрополь-2011

005007433

Работа выполнена в ФГБОУ ВПО «Северо-Кавказская государственная гуманитарно-технологическая академия» (Карачаево-Черкесская Республика, г. Черкесск)

Научный руководитель:

доктор физико-математических наук, профессор

Кочкаров Ахмат Магомедович

Официальные оппоненты:

доктор технических наук, профессор

Копытов Владимир Вячеславович;

доктор физико-математических наук, профессор

Уртенов Махамет Али Хусеевич

Ведущая организация:

Научно-исследовательский институт прикладной математики и автоматизации Кабардино-Балкарского научного центра РАН (г. Нальчик)

Защита состоится « 18 » января 2012 г. в 16 часов 30 минут на заседании совета по защите докторских и кандидатских диссертаций Д 212.256.08 при ФГБОУ ВПО «Ставропольский государственный университет» по адресу:

355009, Россия, г. Ставрополь, ул. Пушкина, д. №1, корпус 1, ауд. 214

С диссертацией можно познакомиться в научной библиотеке Ставропольского государственного университета

Автореферат разослан «15» декабря 2011 г.

Учёный секретарь совета по защите докторских и кандидатских диссертаций, кандидат физико-математических наук Д 212.256.08, доцент

Копыткова Л.Б.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы исследования

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

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

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

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

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

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

Соответствие темы диссертации требованиям паспорта специальности

Диссертация выполнена в соответствие с пунктами 1 «Разработка новых математических методов моделирования объектов и явлений»; 3 «Разработка, обоснование и тестирование эффективных вычислительных методов с применением современных компьютерных технологий»; 6 «Разработка новых математических методов и алгоритмов проверки адекватности математических моделей объектов на основе данных натурного эксперимента»; 8 «Разработка систем компьютерного и имитационного моделирования» «Паспорта специальности 05.13. 18 - математическое моделирование, численные методы и комплексы программ (физико-математические науки)» ВАК Министерства образования и науки РФ.

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

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

Цель и задачи диссертационного исследования

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

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

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

2 Разработка алгоритмов распознавания предфрактальных графов как моделей процессов распространения инфекций;

3 Исследование процессов разрушения предфрактальных графов как моделей процессов затухания инфекционных процессов;

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

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

Методы исследования

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

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

• построена модель динамики инфекций, отличающаяся использованием математического аппарата предфрактальных графов, позволяющая просчитывать количественно определяемый уровень иммунитета каждого человека к конкретному инфекционному заболеванию, а в случае компьютерных сетей - учитывать степень защищённости каждого компьютера в коммуникационной сети;

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

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

• динамическая модель позволяет прогнозировать развитие эпидемии благодаря исследованным свойствам процесса порождения предфрактального графа;

• с помощью модели выявлены кластеры возможного заражения;

• на базе адаптации модели определены возможные очаги эпидемий по заданному графу, отражающему степень заражённости безымунной инфекцией;

• вопреки некоторым существующим моделям, показывающим немедленное

5

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

Теоретическая значимость и практическая ценность результатов исследования заключается в следующем:

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

Личный вклад соискателя

Все теоретические, алгоритмические и программные результаты диссертационного исследования получены автором самостоятельно.

На защиту выносятся следующие основные положения:

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

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

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

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

при моделировании инфекционной динамики;

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

Основные научные и практические результаты работы, полученные автором, докладывались ею и были одобрены на научно-практических конференциях:

1 Международная конференция «Нелокальные краевые задачи и родственные проблемы математической биологии, информатики и физики», г. Нальчик, 2006 г.;

2 У1-ая Международная конференция «Когнитивный анализ и управление развитием ситуаций», г. Москва, 2006 г.;

3 У-ая Международная конференция «Математическое моделирование в образовании, науке и производстве», г. Тирасполь, 2007 г.;

4 У1-ая научно-практическая конференция «Проблемы синергетики в трибологии, трибоэлектрохимии, материаловедении и мехатронике», Новочеркасск, 2007 г.;

5 П-ая Всероссийская научно-практическая конференция «Перспективные системы и задачи управления», г. Таганрог, 2007 г.;

6 Международная конференция, посвященная 100-летию со дня рождения академика И.Н. Векуа, г. Новосибирск, 2007 г.;

7 Ш-я Всероссийская научно-практическая конференция «Перспективные системы и задачи управления», г. Таганрог, 2008 г.;

8 УШ-ая Международная конференция «Методы и алгоритмы прикладной математики в технике, медицине и экономике», г. Новочеркасск, 2008 г.;

9 УШ-ая региональная научно-практическая конференция «Рациональные пути решения социально-экономических и научно-технических проблем региона», г. Черкесск, 2008 г.;

10 Всероссийская электронная научная конференция «Фундаментальные и прикладные проблемы математики», г. Москва, 2008 г.;

11 1Х-ый Всероссийский симпозиум по прикладной и промышленной математике, г. Москва, 2008 г.;

12 Х-ая региональная научно-практическая конференция «Рациональные пути решения социально-экономических и научно-практических проблем региона», г. Черкесск, 2010 г.;

13 У-ая Всероссийская научно-практическая конференция «Перспективные системы и задачи управления», г.Таганрог, 2011 г.;

14 Х1-ая региональная научно-практическая конференция «Рациональные пути

решения социально-экономических и научно-практических проблем региона», г. Черкесск, 2011 г.

Публикации

Основные результаты диссертационного исследования изложены в 24 опубликованных научных работах автора, в том числе 6 статей - в изданиях из Перечня ведущих рецензируемых научных журналов и изданий ВАК Минобрнауки России. Общий объём публикаций составляет 9 пл., в том числе автора 8.3 п.л. Разработанные программные продукты зарегистрированы в Федеральной службе по интеллектуальной собственности, патентам и товарным знакам, что подтверждается тремя свидетельствами о регистрации программ для ЭВМ.

Структура и объем диссертации

Диссертация состоит из введения, четырёх разделов, заключения, списка использованных источников из 191 наименования, трёх приложений на 62 страницах с описанием разработанного программного комплекса. Текст основной части диссертации изложен на 136 страницах, он содержит 23 рисунка, одну таблицу.

ОСНОВНОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИОННОЙ РАБОТЫ

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

В первом разделе «Математический аппарат распознавания и исследования предфрактальных графов как моделей распространения инфекций» рассмотрены основные понятия и определения теории графов, теории сетей, теории фрактальных и предфрактальных графов с операциями над ними.

В основе идеи построения фрактальных графов и их широкого практического распространения лежит операция замены вершины затравкой (ЗВЗ), т.е. некоторым самостоятельным графом. Таким образом, термином «затравка» условимся называть какой-либо связный граф H = {W,Q) и в динамике одного шага распознавания исходный граф будет «прирастать» целым графовым ансамблем - затравкой. Так системно «прирастают» управленческие структуры, инфотелекоммуникацион-ные сети, социальные сети, технические сети и пр. с одним и тем же типажом добавляемых в систему новых составных частей-затравок. Удалось показать, что динамика распространения инфекционных процессов релевантна процессам разрастания (распознавания) предфрактальных графов, а спад эпидемических процессов описывается алгоритмами разрушения предфрактальных графов. Это и обусловило научный и практический интерес к подобным графовым структурам, проведены исследования их специфических топологических и метрических свойств, вплоть до получения минимальных раскрасок с наименьшим хроматическим числом.

Суть «операции ЗВЗ» заключается в следующем. В графе G = (V, Е) у намеченной для замещения вершины ve к выделяется множество F = {v/}cK, j = 1,2,...,|f| смежных ей вершин. Далее из графа G удаляется вершина v и все инцидентные ей рёбра. Затем каждая вершина Vj eV, j = 1,2,...,|f| соединяется ребром с одной из вершин затравки Н. Вершины соединяются произвольно (случайным

образом) или по определённому правилу при необходимости.

Предфрактальный граф обозначим через ={У1,Е1), где Уь - множество вершин графа, а Е1 - множество его рёбер. Определим его рекуррентно, поэтапно, заменяя каждый раз в построенном на предыдущем этапе 1 = 1,2,..., Ь -1 графе =(У1,Е1) каждую его вершину затравкой Н. На этапе 1 = 1 предфрактальному графу соответствует затравка = Н. Об описанном процессе говорят, что предфрактальный граф Оь порождён затравкой Н. Процесс порождения предфракталь-ного графа Оь по существу есть процесс построения последовательности предфрак-тальных графов Сх,02,--;О1,...,С называемый траекторией. Фрактальный граф <7 = (К,£), порождённый затравкой Н, определяется бесконечной траекторией. Поэтому под распознаванием предфрактального графа будем понимать определение траектории построения предфрактального графа при условии, что будут заданы виды и типы затравок. Поскольку распознавание предфрактального графа хорошо изучено и широко известно, ограничимся наиболее важными алгоритмами.

Для предфрактального графа Сь рёбра, появившиеся на /-ом, / е {1,2,..., Ь), этапе порождения, будем называть рёбрами ранга I. «Новыми» рёбрами предфрактального графа назовём рёбра ранга Ь, а все остальные рёбра назовём «старыми».

Будем говорить, что предфрактальный граф = , Еь) вершинно взвешен, если каждой его вершине е Уь приписано действительное число

е (в1~ха,в1~хЬ), где 1 = \,Ь - ранг вершины, а>0,и 9 < —.

Ъ

Рангом вершины предфрактального графа называется наименьший ранг I среди всех инцидентных ей рёбер. Вершину / -го ранга обозначим как , где /е {1,2,...,£}. Вершину 1-го ранга являющуюся очагом заражения, назовем «очагом заражения I -го ранга», где / = 1,2,..., Ь.

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

Рассмотрим следующую задачу. Пусть представлен в явном виде некоторый граф б = (У,Е), обладающий всеми необходимыми (но не являющимися достаточными) признаками предфрактального графа. Для этого надо определить:

• является ли данный граф предфрактальный с определённой затравкой;

• можно ли построить эффективный алгоритм, который гарантированно воспроизведёт процесс порождения предфрактального графа с определённой затравкой.

Некоторые необходимые признаки предфрактальности графа С = (V, Е):

1 Для мощности множества вершин \у\ = N существует непустое множество пар или кортежей длины два <п, Ь> таких, что N = N(>1,1);

2 Для мощности множества рёбер |£| существует хотя бы одна пара (кортеж

длины два) <п, Ь>, удовлетворяющая равенству =

3 Множество рёбер ранга I есть объединение множеств рёбер-затравок, появляющихся после замещения каждой вершины графа ранга ¿-1 затравкой.

Лемма 1.1 Пусть в предфрактальном графе с = (у, е) две вершины V, и принадлежат одной затравке Я = (^,{3) е IV ) и имеет место смежность с некоторой вершиной V е V, тогда вершина V также принадлежит этой затравке н.

Для решения поставленной задачи распознавания предфрактального графа с = (у, е) с непересекающимися «старыми» рёбрами, когда затравка - регулярный граф степени п- 2, предлагается следующий алгоритм аь состоящий из этапов р = 1,2,..., Х-1, которые взаимно и однозначно соответствуют текущим графам в,, I = 2,.., Ь порождающей траектории. На входе этапа р рассматривается текущий граф в,, где 1 = Ь-р +1. Этап р выделяет в й, затравки, состоящие из рёбер ранга 1, после чего каждая из этих затравок стягивается в вершину. Полученный в результате текущий граф С7,_, представляется на вход этапа /-1. В процессе конструктивной

реализации 1-1 этапов алгоритма а1 получаем последовательность .....О,".

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

Теорема 1.1 Всякий предфрактальный граф о = (у, е) с попарно непересекающимися «старыми» рёбрами и регулярной и-вершинной затравкой Я = (IV, д) степени 2 является распознаваемым алгоритмом а,.

Теорема 1.2 Алгоритм в, представляет собой полиномиальный алгоритм распознавания предфрактальности всякого п1 -вершинного графа С=(У,Е), в котором содержится равномощных непересекающихся клик IV0 мощности |^Г°|>2. Верхняя оценка вычислительной сложности алгоритма г(а,) <0(\Е\Ь).

Для распознавания предфрактального графа с непересекающимися «старыми» рёбрами и с двумя чередующимися затравками разработан алгоритм а2.

Теорема 1.3 Всякий предфрактальный граф в = (У,Е), образованный двумя полными чередующимися затравками Л, = (^,<2,) и IIг = (1У2,д2), распознаётся алгоритмом а2, где вычислительная трудоёмкость алгоритма т(аг)=о\Е\ь) в том случае, если «старые» рёбра не пересекаются.

С учётом всего сказанного выше справедлива следующая теорема.

Теорема 1.4 Проблема распознавания свойства предфрактальности данного графа б разрешима алгоритмом а2 при выполнении следующих условий: граф в является предфрактальный графом с непересекающимися «старыми» рёбрами, образованным двумя полными и- и «+/-вершинными чередующимися затравками.

Для распознавания предфрактального графа с пересекающимися «старыми» рёбрами с двумя полными чередующимися затравками разработан алгоритм а,.

Теорема 1.5 Всякий предфрактальный граф с, = (у, , е,) с двумя полными затравками распознается алгоритмом а,, где смежность «старых» рёбер не наруша-

ется, с вычислительной трудоёмкостью алгоритма т(аг)<о\Щ£).

Распознавание предфрактального графа с пересекающимися «старыми» рёбрами, образованного множеством полных затравок с чередованием, осуществляется с помощью алгоритма аА.

Теорема 1.6 Всякий предфрактальный граф в = (у, Е) с пересекающимися «старыми» рёбрами, образованный множеством полных чередующихся затравок, является распознаваемым алгоритмом аА, где вычислительная сложность алгоритма оказывается т(аА) < 0{\Е\1).

Для распознавания предфрактального графа с пересекающимися «старыми» рёбрами, образованного множеством полных затравок, разработан алгоритм а5.

Теорема 1.7 Всякий предфрактальный граф С, = (г,£) с пересекающимися «старыми» рёбрами, образованный множеством полных затравок, является распознаваемым алгоритмом а5, где вычислительная сложность алгоритма г(а5) < 0(\е\ь) .

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

Исследование процессов

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

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

Рисунок 1 - Предфрактальный граф, порождённый двумя полньми чередующимися затравками

Теорема 2.1 Для всякого предфрактального графа О^, порождённого двумя полными чередующимися затравками при сохранении смежности «старых» рёбер, удаление любого количества вершин Ь -го ранга не нарушает его связности, т.е. число компонентов связности остаётся равным единице.

Теорема 2.2 Для всякого предфрактального графа порождённого двумя полными затравками с сохранением смежности «старых» рёбер, удаление к вершин /-го ранга приводит к появлению (Ь -1)к +1 компонент связности при условиях, когда

Теорема 2.3 Для всякого предфрактального графа порождённого двумя полными затравками с сохранением смежности «старых» рёбер, удаление к вершин (¿-1)-го ранга приводит к появлению ¿ + 1 компонент связности, где 1 < к < | -\УЬ_21.

Теорема 2.4 Всякий пред-фрактальный граф Оь, порождённый двумя полными чередующимися затравками с сохранением смежности «старых» рёбер и с очагами заражения (I -1)-го ранга, будет разрушен по критерию 0¡(к), где 1 < к < -\УЬ_2\.

Теорема 2.5 Всякий предфрактальный граф , порождённый двумя полными затравками с сохранением смежности «старых» рёбер и с очагами заражения 1-го ранга, будет разрушен по критерию 0¡(к) при условии 1<¿<|г/_1|-|к/.2|, / = £-1,1-2,...,2.

Теорема 2.6 Всякий предфрактальный граф , порождённый двумя полными затравками с сохранением смежности «старых» рёбер и с очагами заражения первого ранга, будет разрушен по критерию 0¡(к), где 1 < А: < |КХ|.

Теорема 2.7 Всякий предфрактальный граф С;, порождённый множеством полных затравок с сохранением смежности «старых» рёбер и с очагами заражения разных рангов, будет разрушен по критерию 0/(к).

Теорема 2.8 Всякий предфрактальный граф Оь, порождённый двумя полными затравками с сохранением смежности «старых» рёбер и с очагами заражения (1-1)-го ранга, будет разрушен по критерию в2(к,т) для всех т<к +1, где

Теорема 2.9 Всякий предфрактальный граф Сь, порождённый двумя полными затравками с сохранением смежности «старых» рёбер и с очагами заражения /-го ранга, будет разрушен по критерию 02(к,т) для всех т<{Ь-1)к +1, где

в результате разрушения в очагах заражения Ь-го ранга, показанных на рис. 1

!<т<\¥,\ и 1<*<|КЫ|-|Г,_2|, / = £-1,£-2,...,1.

Теорема 2.10 Всякий предфрактальный граф Gi, порождённый двумя полными затравками с сохранением смежности «старых» рёбер, будет разрушен по критерию в3(к,0) при удалении хотя бы одной вершины (£-1)-го ранга для всех 1<£><2/.-1.

Теорема 2.11 Всякий предфрактальный граф С,, порождённый двумя полными затравками с сохранением смежности «старых» рёбер, будет разрушен по критерию в ¡(к,Б) при удалении хотя бы одной вершины 1-го ранга для любого £>>2, где 1<^<|Км|-|К/_2| / = £-1,1-2,...,!.

Теорема 2.12 Всякий предфрактальный граф Оь с двумя полными чередующимися затравками, с сохранением смежности «старых» рёбер и с очагами заражения ¿-го ранга может быть разрушен по критерию в3(к,В) только для Б = 21-2 и £> = 21-3, где, соответственно, к = \Уь\-уь_х\-! и ^ = |7£|-|К£_,|-2.

Теорема 2.13 Всякий предфрактальный граф Сь, порождённый двумя полными затравками с сохранением смежности «старых» рёбер, разрушается по критерию в3(к,0) для всех В>2 при удалении хотя одной вершины первого ранга.

Теорема 2.14 Для всякого предфракгального графа Сь, порождённого двумя полными затравками с сохранением смежности «старых» рёбер, удаление к вершин первого ранга приводит к появлению (Ь - !)к +1 компонент связности для

всех к = 1,2,...,-1 и к появлению (I -1 )к компонент для к = .

Теорема 2.15 Для всякого предфрактального графа С, , порождённого двумя полными затравками с сохранением смежности «старых» рёбер, удаление вершин разных рангов приводит к появлению

1 • к^1'^ + 2 • к(1'~2) +... + (I -1) • +1 компонент связности, число очагов заражения 1-го ранга на одной подграф-затравке г(,) не превышает (я - 2) для всех / е [1 ,£].

В третьем разделе «Исследование метрических и топологических характеристик предфрактальных графов с различными затравками» найден и изучен ряд свойств и характеристик предфрактальных графов, порождённых затравками нескольких типов, представляющими собой:

• регулярный л-вершинный граф степени ^ = п - 2;

• два полных чередующихся графа с сохранением смежности «старых» рёбер;

• два полных чередующихся графа в случае не пересечения «старых» рёбер;

• множество полных затравок с пересечением «старых» рёбер в любом порядке;

• множество полных чередующихся затравок с пересечением «старых» рёбер;

• дерево регулярной степени.

Получены топологические и метрические (радиус, диаметр, хроматическое число) оценки характеристик предфрактальных графов.

О диаметральных цепях в предфрактальных графах. Лемма 3.1 В любом предфрактальном графе С = (V, Е), порождённом регулярной «-вершинной затравкой Н = (Ж, 0 степени я = п - 2, всякая его диаметральная цепь имеет периферийные вершины степени п- 2.

Лемма 3.2 В любом предфрактальном графе й = (V, Е), порождённом ре-

гулярной и-вершинной затравкой Н = (IV, 0) степени з = п-2, всякая его диаметральная цепь содержит два ребра ранга 1, четыре ребра ранга 2, восемь рёбер ранга 3,... ,21 рёбер ранга /, т.е. ¿(00 >2(1(Ок.,) + 1.

Лемма 3.3 В любом предфрактальном графе С = (V, Е) с непересекающимися «старыми» рёбрами, образованном двумя полными затравками Н, = (IV,, и Н2 = 0¥2, ()2), где \Щ = п, \Щ = п + 1, всякая его диаметральная цепь содержит одно ребро ранга 1 и по два ребра остальных рангов.

О диаметре предфрактального графа.

Теорема 3.1 Для всякого предфрактального графа С = (У,Е) с непересекающимися «старыми» рёбрами, порождённого несколькими полными затравками, диаметр с1(0)<2Ь-1.

Теоремы 3.2 и 3.3 Для всякого предфрактального графа й ранга Ь с непересекающимися «старыми» рёбрами, порождённого и-вершинной регулярной затравкой степени л-2, величина диаметра (¡(С) удовлетворяет неравенству

(3.!)

Теорема 3.4 Для всякого предфрактального графа <5 ранга Ь, порождённого затравкой-звездой Я, справедлива следующая оценка величины его диаметра а{ву ¿(С)<21-\ (3.2)

Теоремы 3.5 и 3.6 Для всякого предфрактального графа й ранга I, порождённого я-вершинной регулярной затравкой степени п- 2 с пересекающимися «старыми» рёбрами, величина диаметра ¿{О) удовлетворяет неравенству

2(?-1) >^4£-2 (3.3)

О хроматическом числе предфрактальных графов.

Теорема 3.7 Для хроматического числа всякого предфрактального графа б ранга Ь с непересекающимися «старыми» рёбрами, образованного регулярной п-вершинной затравкой Я степени * = п- 2, справедлива достижимая оценка

М(С)<М{Н)-Ь (3.4)

Теорема 3.8 Для всякого предфрактального графа б ранга I с затравкой-звездой Я справедлива верхняя достижимая оценка хроматического числа < 2Ь.

О степенях вершин предфрактальных графов.

Теорема 3.9 Пусть граф в = (у,е) - предфрактальный граф, он является таким (п,Ь) -графом, в котором «старые» рёбра не пересекаются и его затравка н = (^>в) является однородным графом степени * = 2. Тогда множество его вершин v разбивается на два подмножества у, и у2, где подмножество у1 составляют вершины, степень которых равна п-1, а подмножество у2 составляют вершины, степень которых равна л-2. При этом мощности этих подмножеств определяются соотношениями

„_1-1> (3-5)

^ТГГ"-1- (3.6)

Теорема 3.10 Пусть в = (у,Е) - граф с непересекающимися «старыми» рёбрами чётного ранга Ь, образованный двумя полными затравками и

Л = 0^1> ) > где КI = " > К | = " +1 • Процедура ЗВЗ производится на нечётных этапах затравкой / , = (И',,£>,), а на чётных - затравкой 11=(П'1,()г). Тогда множество вершин графа разбивается на два подмножества - v, и у2, где v, составляют вершины, степень которых равна п +1, а К, составляют вершины, степень которых равна п. При этом мощности этих множеств определяются соотношениями:

1-2 Ь-2

2 (п + 1) 1 -1 "

П^+ярГ "Г , +2"2 (и+1) 2

п(п +1)-1 (37)

1 1 л(л+-1)-1

где = |б,|, яг = \0г\ - количество рёбер-затравок Я, и Я2.

Теорема 3.11 Пусть в = (У,£) - предфрактальный граф нечётного ранга I, тогда множество его вершин v разбивается на два подмножества у1 и у2, где К, составляют вершины, степень которых равна п+1, а К2 составляют вершины, степень которых равна п. Мощности этих множеств определяются соотношениями:

1.-3 ь-з

1У,1=2(Ч,+Чдп)п 2 ;п+;;2 -Чгпчп-ирч,

п(п + 1)-1 о-\

И Ы V • >

|У2| = пМп + 1)^-2(Ч1+Чгп)п2 2 +

п(п + 1)—1

В четвёртом разделе «Математические предфрактальные модели инфекционной динамики» построены модели процессов распространения инфекций (человеческих и компьютерных); сформулированы основные проблемы методологии моделирования эпидемий и перспективы практического решения задач моделирования инфекционных процессов; представлены, построены и исследованы теоретико-графовые модели распространения эпидемий и вирусов в сетях.

Некоторые начальные пояснения. В качестве примера обозначим вершинами V, еК, ¿ = 1,и отдельно взятых членов семьи, состоящей из п человек, которые проживают вместе. Соединим две вершины у,(« = 1,л) и V] Рисунок 3 - Граф как 0' = й) ) ребром е = (у,,^.) в случае, когда между чле-модель бытовых кон- нами семьи « и / имеется тесный бытовой контакт, доста-тактов между членами точный для заражения друг друга исследуемым инфекци-семьи, состоящей из онным заболеванием. В случае заражения людей инфек-четырёх человек ционным заболеванием, передающимся воздушно-капельным путём от одного из членов семьи, риск заражения имеют все остальные члены семьи. Моделью бытовых контактов между членами семьи, состоящей из четырёх человек, будет граф Н^ЦУ^), представленный на рис. 3.

Продолжая процесс моделирования распространения инфекции от человека к человеку, на этапе 1 = 1 граф, описывающий контакты в семье, будет представлять собой и,-вершинный полный граф в^СУ^Е^). На этапе 1 = 2 граф, описывающий контакты семей, проживающих, например, на одной лестничной площадке,

15

представляется как 02 = (У2,Е2), его можно получить из графа О, = (У1,Е1), применяя операцию ЗВЗ к каждой его вершине, причём операцию ЗВЗ будем производить случайным образом при помощи графов Я, = или Я2 = (Ж,,02).

Продолжая этот процесс, можно описать контакты всего многоэтажного дома, жилого квартала, микрорайона, города и т.д. Повторяя этот процесс при /-юо, структура контактов будет представлять собой фрактальный граф й = (У,Е), порождённый двумя полными затравками Я, и Я, = (^2,£>2)(рис. 4). Всякий пред-фракгальный граф в, = (У„Е,), 1 = 1,2,..., взятый из траектории построения фрактального графа С = (У,Е), является структурой контактов на /-м этапе.

Вернёмся к коммуникационным сетям. Любую компьютерную сеть можно представить в виде графа в = (У,Е), в котором V- множество вершин (компьютеров, серверов или узловых коммуникаторов), Е- множество рёбер, соответствующим связям между всеми этими узлами. Обозначим через вершины V,. = отдельно взятые персональные компьютеры локальной сети одного из отделов некоторой организации, всего сеть состоит из п узлов. Соединим две вершины V, (;' = 1^й) и vJ (у = Гп) I*) ребром е = (у„у;) в том случае, когда между компьютерами / и /имеется канал связи, по которому могут распространяться компьютерные вирусы.

Рассмотрим некоторую локальную сеть, например, компьютерную сеть бухгалтерии организации. Не нарушая общности, допустим, что в бухгалтерии имеется 5 компьютеров, соединенных между собой в сеть по топологии «звезда». Моделью каналов связи между компьютерами локальной сети, состоящей из 5 узлов, станет граф Я, = (Щ,д,), представленный на рис. 5.

Предположим, что в данной организации имеется несколько отделов, в которых имеются локальные сети различной топологии. Для определённости назовём эти локальные сети сетями уровня 1. Тогда каналы связи между всеми отделами организации (сети уровня 2) можно представить в виде сле-

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

Рисунок 5 - Предфрактальный граф, описывающий взаимосвязь пяти компьютеров в локальной сети бухгалтерии

дующего графа на рис. 6.

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

тинентов.

Рисунок 7 - Предфрактальный граф, описывающий структуру каналов связи глобальной телекоммуникационной сети (компьютеры в сети третьего уровня)

Исследуемая организация может быть подключена к глобальной сети Интернет через локального поставщика услуг. Известно, что локальные поставщики могут объединять сети на территории района, города. В свою очередь локальные поставщики получают услуги Интернет от региональных провайдеров, которые могут владеть сетями на территории края (округа). Такие каналы связи назовём связями уровня 3. Граф, описывающий каналы связи такой сети, представлен на рис. 7. Региональные поставщики получают услуги от магистральных поставщиков - глобальных операторов, владеющих собственными информационными магистралями, покрывающими крупные регионы уровня стран и кон-

Таким образом, на этапе 1 = 1 граф, описывающий каналы связи локальной сети некоторого отдела организации, будет представлять собой л,-вершинный граф О, = (У,,Е,). На этапе 1 = 2 граф, описывающий каналы связи локальных сетей нескольких отделов одной организации, представляется графом Сг = (У1,Е1), который можно получить из графа С, = (/„£,), применяя операцию ЗВЗ к каждой его вершине, причём операцию ЗВЗ можно будет производить случайным образом графами Я, = (ад),Я2 = (^,&), Я, = (^3,63). Продолжая этот процесс, можно описать каналы связи региональных и национальных провайдеров, магистральных поставщи-структура каналов связи глобальной

ков и т.д. Повторяя такой процесс при / да сети будет представлять собой фрактальный граф а = (У,Е), порождённый тремя затравками я, = ,нг = > = №.&)• Всякий предфрактальный граф О, = (У„Е1), 1 = 1,2,... из траектории построения фрактального графа О = (У,Е) будет моделировать и представлять структуру каналов связи на 1-м этапе.

В заключении сформулированы основные выводы и результаты диссертационной работы.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ, ПОЛУЧЕННЫЕ В ДИССЕРТАЦИОННОМ ИССЛЕДОВАНИИ

В результате выполнения теоретических и практических исследований в диссертационной работе получены следующие основные результаты:

1 Для моделирования распространения инфекций разработан комплекс алгоритмов распознавания предфрактальных графов, порождённых различными классами затравок. Предложены и обоснованы алгоритмы их построения (распознавания);

2 Исследованы основные характеристики предфрактальных графов, служащие базой для конструирования моделей распространения инфекций, порождаемых и моделируемых различными классами затравок. Получены оценки и числовые значения их топологических, метрических, хроматических характеристик;

3 Изучена надёжность (безотказность, ремонтопригодность, долговечность) и условия разрушения предфрактальных графов, порождённых различными классами затравок. Построены соответствующие модели;

4 Модели разрушения предфрактальных графов использованы для представления затухания инфекционных процессов (человеческих и компьютерных);

5 На базе предфрактальных графов построены теоретико-графовые модели:

• структуры бытовых контактов людей в некоторой социальной сети;

• модели связей между операционными узлами в компьютерной сети.

6 Введено понятие «эпидемического порога» на взвешенных предфрактальных графах. Модель позволяет учитывать уровень иммунитета каждого отдельно взятого человека и степень защиты каждого компьютера в сети от определенного вируса -соответственно, человеческого или компьютерного;

7 Рассчитаны условия локализации инфекции на каждом этапе развития эпидемии. Возможно выявление возможных кластеров заражения. Для безымунных эпидемий возможно выявление возможных очагов заражения;

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

ПО ТЕМЕ ДИССЕРТАЦИИ ОПУБЛИКОВАНЫ СЛЕДУЮЩИЕ РАБОТЫ:

Публикации в ведущих рецензируемых журналах и изданиях, определённых ВАК:

1 Найманова И.Х., Кочкаров A.M. Об одной задаче распознавания предфрак-тального графа // Вестник Самарского государственного технического университета.

- 2007. - № 1 . - С. 194-196.0.22 пл., в т.ч. автора 0.20 пл.;

2 Утакаева И.Х. Алгоритм распознавания предфракгального графа с затравкой регулярной степени // Обозрение прикладной и промышленной математики. - 2008.

- Том 15. - Выпуск 3. - С. 531-533.0.22 пл.;

3 Утакаева И.Х., Кочкаров P.A. Алгоритмы распознавания предфрактальных графов с различными затравками // Известия Южного федерального университета (г. Таганрог). - 2010. - Том 102. - № 1. - С. 27-38. 0.88 пл., в т.ч. автора 0.70 пл.;

4 Утакаева И.Х., Кочкаров A.A. К вопросу об алгоритмах распознавания предфрактальных графов // Научно-технические ведомости Санкт-Петербургского государственного политехнического университета. - 2010. - Том 103. - № 4. - С. 139-142. 0.33 пл., в т.ч. автора 0.25 пл.;

1В

Таганрог). - 20П. - Том 115. - № 2. - С. 14-19. 0.44 пл., в т.ч. автора 0.4 пл.; 6 Утакаева И.Х. Структурный алгоритм распознавания предфрактального графа // Вестник Самарского государственного университета. Серия «Физико-математические науки». - 2011. - № 3 (24). - С. 208-211. 0.33 пл. Публикации в других изданиях:

I Найманова И.Х. Задача распознавания предфрактального графа с регулярной «-вершинной затравкой степени s=n-2 II Материалы Ш-ей Международной конференции «Нелокальные краевые задачи и родственные проблемы математической биологии, информатики и физики». - Нальчик: Издательство НИИ ПМА КБНЦ РАН, 2006. - С. 204-206. 0.22 пл.;

8 Найманова И.Х. Распознавание предфрактального графа с регулярной затравкой // Труды V-ой Международной конференции «Математическое моделирование в образовании, науке и производстве». - Тирасполь: Издательство Приднепровского университета, 2007. - С. 23-24. 0.15 пл.;

9 Утакаева И.Х. Распознавание предфрактального графа с двумя затравками, если «старые» рёбра пересекаются // Материалы VI-ой научно-практической конференции «Проблемы синергетики в трибологии, трибоэлектрохимии, материаловедении и мехатронике». - Новочеркасск: Центр оперативной полиграфии ЮРГТУ (НПИ), 2007. - С. 34-35. 0.15 пл.;

10 Утакаева И.Х. Распознавание предфрактального графа с двумя затравками, если «старые» рёбра не пересекаются // Материалы VI-ой научно-практической конференции «Проблемы синергетики в трибологии, трибоэлектрохимии, материаловедении и мехатронике». - Новочеркасск: Центр оперативной полиграфии ЮРГТУ (НПИ), 2007.-С. 36-37.0.15 пл.;

II Утакаева И.Х., Эльканова JI.M. Оценка оптимального потока на предфрак-тальных орграфах // Сборник трудов И-ой Всероссийской научно-практической конференции «Перспективные системы и задачи управления». - Таганрог: Издательство Таганрогского технологического института ЮФУ, 2007. - С. 180-183. 0.33 пл., в т.ч. автора 0.30 пл.;

12 Утакаева И.Х., Эльканова Л.М. Распознавание предфрактального графа с двумя затравками // Сборник трудов 11-ой Всероссийской научно-практической конф. «Перспективные системы и задачи управления». - Таганрог: Издательство Таганрогского технологического ин-та ЮФУ, 2007. - С. 190-191. 0.15 пл., в т.ч. авт. 0.10 пл.;

13 Утакаева И.Х. Об одной модели распознавания предфрактального графа // Тезисы докладов на Международной конференции, посвященной 100-летию со дня рождения академика И.Н. Векуа. - Новосибирск: Редакционно-издательский центр НГУ, 2007. - С. 634-635. 0.15 пл.;

14 Утакаева И.Х. Математические модели задач распознавания предфрактальных графов // Сборник трудов Ш-ей Всероссийской научно-практической конференции «Перспективные системы и задачи управления». - Таганрог: Издательство Таганрогского технологического института ЮФУ, 2008. - С. 231-235.0.40 пл.;

15 Утакаева И.Х. Числовые характеристики предфрактальных графов с различными затравками // Сборник трудов Ш-й Всероссийской научно-практической конференции «Перспективные системы и задачи управления». - Таганрог: Издательство Таганрогского технологического института ЮФУ, 2008. - С. 248-251.0.33 пл.;

16 Утакаева И.Х. Предфрактапьный граф с регулярной затравкой и его распознавание // Современные наукоёмкие технологии. - 2008. Вып. 2. - С. 150-152. 0.22 пл.;

17 Утакаева И.Х. Математическая модель задачи распознавания предфрактально-го графа с регулярной затравкой // Материалы VIII-ой Международной конф. «Методы и алгоритмы прикладной математики в технике, медицине и экономике». - Новочеркасск: Центр операт. полиграфии ЮРГТУ (НПИ), 2008. - С. 19-21. 0.22 пл.;

18 Утакаева И.Х., Болуров H.H. Числовые характеристики предфрактальных графов с различными затравками и алгоритмы их распознавания // Материалы VIII-ой региональной научно-практической конференции «Рациональные пути решения социально-экономических и научно-технических проблем региона». - Черкесск: Издательство Карачаево-Черкесской государственной технологической академии, 2008. -С. 205-206. 0.15 пл., в т.ч. автора 0.10 пл.;

19 Утакаева И.Х. Распознавание предфрактальных графов с полными затравками // Материалы Х-ой региональной научно-практической конференции «Рациональные пути решения социально-экономических и научно-практических проблем региона». - Черкесск: Издательство Карачаево-Черкесской государственной технологической академии, 2010. - С. 46-47.0.15 пл.;

20 Утакаева И.Х., Кочкаров А.М. Моделирование процесса распространения эпидемии и нахождения возможных очагов заражения на предфрактальном графе // Сборник трудов Ш-ей Всероссийской научно-практической конференции «Перспективные системы и задачи управления». - Таганрог: Издательство Таганрогского технологического института ЮФУ, 2011. - С.273-283.0.8 пл., в т.ч. автора 0.7 пл.

21 Утакаева И.Х. Моделирование структуры распространения эпидемии на предфрактальных графах // Материалы XI-ой региональной научно-практической конференции «Рациональные пути решения социально-экономических и научно-практических проблем региона». - Черкесск: Издательство МПЦ Северо-Кавказской государственной гуманитарно-технологической академии, 2011. - С. 77-79.0.22 пл. Свидетельства о государственной регистрации программ для ЭВМ:

22 Утакаева И.Х., Кочкаров A.A. Распознавание предфрактального графа с двумя полными чередующимися затравками. Свидетельство № 2011615242 от 10 мая 2011г., зарегистрировано в Реестре программ для ЭВМ 5 июля 2011г. - 7 е., 0.50 пл., в т.ч. автора 0.30 пл.

23 Утакаева И.Х. Распознавание предфрактального графа с регулярной затравкой. Свидетельство № 2011615243 от 10 мая 2011г., зарегистрировано в Реестре программ для ЭВМ 5 июля 2011г. - 7 е., 0.50 пл.

24 Утакаева И.Х. Моделирование структуры распространения эпидемии на предфрактальных графах. Свидетельство № 201161524 от 10 мая 2011г., зарегистрировано в Реестре программ для ЭВМ 5 июля 2011г. - 23 е., 1.80 пл.

Подписано в печать 13.12.2011 г. Формат 60x84/16. Бумага офсетная. Печать офсетная. Усл. печ. л. 1.0. Заказ № 0670. Тираж 100 экз. Издательство ФГБОУ ВПО «СКГГТА» 369000, КЧР, г. Черкесск, ул. Ставропольская, 36

61 12-1/378

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «СЕВЕРО-КАВКАЗСКАЯ ГОСУДАРСТВЕННАЯ ГУМАНИТАРНО-ТЕХНОЛОГИЧЕСКАЯ АКАДЕМИЯ»

На правах рукописи

Утакаева Ирина Хайрлыевна

Математические модели инфекционной динамики

на основе предфрактальных графов

05.13.18 - Математическое моделирование, численные методы и комплексы программ

ДИССЕРТАЦИЯ

на соискание учёной степени кандидата физико-математических наук

Научный руководитель -доктор физико-математических наук,

профессор

А.М. КОЧКАРОВ

Черкесск-2011

СОДЕРЖАНИЕ.............................................................................2

ВВЕДЕНИЕ...................................................................................5

1 МАТЕМАТИЧЕСКИЙ АППАРАТ РАСПОЗНАВАНИЯ И

ИССЛЕДОВАНИЯ ПРЕДФРАКТАЛЬНЫХ ГРАФОВ КАК

МОДЕЛЕЙ РАСПРОСТРАНЕНИЯ ИНФЕКЦИЙ..............................19

1.1 Фрактальные и предфрактальные графы...................................19

1.2 Распознавание предфрактального графа с регулярной затравкой степени г = п- 2.............................................................26

1.2.1 Алгоритм а! распознавания...................................................27

1.2.2 Описание процедуры рх.........................................................28

1.3 Распознавание предфрактального графа с непересекающимися «старыми» рёбрами, образованного двумя чередующимися затравками......31

1.3.1 Алгоритм а2 распознавания предфрактальных графов.................32

1.3.2 Описание процедуры р21 (выделения затравки Нх = СЮ).......33

1.3.3 Описание процедуры р22 (выделения затравки Н2 = (\У2, СЪ))......34

1.4 Распознавание предфрактального графа с пересекающимися «старыми» рёбрами, образованного двумя полными

чередующимися затравками...........................................................35

1.4.1 Алгоритм а3 распознавания предфрактальных графов.................36

1.4.2 Описание процедуры р31 выделения затравки Щ = (\¥ь С^)..........37

1.4.3 Описание процедуры р32 выделения затравки Н2 = (\¥2, СЬ).........38

1.5 Распознавание предфрактального графа с пересекающимися «старыми» рёбрами, образованного множеством полных затравок

с чередованием.............................................................................41

1.5.1 Алгоритм <Х4 распознавания предфрактальных графов...............41

1.5.2 Описание процедуры р4............................................................42

1.6 Распознавание предфрактального графа с пересекающимися «старыми» рёбрами, образованного множеством полных затравок.......44

1.6.1 Алгоритм а5 распознавания предфрактальных графов...............45

1.6.2 Описание процедуры р5.........................................................45

1.7 Распознавание предфрактального графа, если затравка -

дерево регулярной степени.............................................................47

1.7.1 Алгоритм <Хб распознавания предфрактальных графов................49

Выводы 1.....................................................................................51

2 ИССЛЕДОВАНИЕ ПРОЦЕССОВ РАЗРУШЕНИЯ ПРЕДФРАКТАЛЬНЫХ ГРАФОВ КАК МОДЕЛЕЙ ЗАТУХАНИЯ ЭПИДЕМИЧЕСКИХ ПРОЦЕССОВ................................................53

2.1 Надёжность, живучесть, стойкость..............................................53

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

2.2.1 Разрушение предфрактального графа с эпицентрами

в вершинах Ь-то ранга.....................................................................60

2.2.2 Разрушение предфрактального графа с эпицентрами

в вершинах Ь-1-го ранга..................................................................64

2.2.3 Разрушение предфрактального графа с эпицентрами

в вершинах /-го ранга, где I —1-1, ..., 2................................................68

2.2.4 Разрушение предфрактального графа с эпицентрами

в вершинах первого ранга..............................................................70

2.2.5 Разрушение предфрактального графа с эпицентрами

в вершинах разных рангов.............................................................71

2.3 Структурное разрушение предфрактальных деревьев.....................74

2.3.1 Структурное разрушение предфрактальных деревьев

по критерию связности...................................................................74

2.3.2 Структурное разрушение предфрактальных деревьев

по компонентному критерию...........................................................75

2.3.3 Структурное разрушение предфрактальных деревьев

по диаметральному критерию........................................................76

Выводы 2....................................................................................78

3 ИССЛЕДОВАНИЕ МЕТРИЧЕСКИХ И ТОПОЛОГИЧЕСКИХ ХАРАКТЕРИСТИК ПРЕДФРАКТАЛЬНЫХ ГРАФОВ

С РАЗЛИЧНЫМИ ЗАТРАВКАМИ.....................................................79

3.1 Предфрактальный граф (г = (V, Е) с регулярной затравкой степени « = п-2..............................................................................79

3.2 Предфрактальный граф (г = (V, Е) с непересекающимися «старыми» рёбрами, образованный двумя полными чередующимися затравками Щ = (1Гь (¿1) и Н2 = 0¥2, (¿2).......................................................85

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

не нарушается.............................................................................88

3.4 Предфрактальный граф с затравкой-звездой..............................91

Выводы 3....................................................................................92

4 МАТЕМАТИЧЕСКИЕ ПРЕДФРАКТАЛЬНЫЕ МОДЕЛИ ИНФЕКЦИОННОЙ ДИНАМИКИ..................................................94

4.1 Математическая модель структуры распространения инфекционного заболевания..........................................................94

4.2 Эпидемический порог............................................................102

4.3 Алгоритм поиска порога перколяции предфрактального

графа........................................................................................103

4.4 Карантин............................................................................103

4.5 Структура распространения инфекционного заболевания...........104

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

(компьютерных вирусов) в телекоммуникационных сетях.................106

Выводы 4..................................................................................113

ЗАКЛЮЧЕНИЕ.........................................................................114

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ............................115

ПРИЛОЖЕНИЕ 1.......................................................................137

ПРИЛОЖЕНИЕ 2.......................................................................165

ПРИЛОЖЕНИЕ 3.......................................................................176

ВВЕДЕНИЕ

В настоящее время инфекционные болезни остаются одной из ведущих причин преждевременной смерти людей на Земле. Это происходит в основном из-за высокой смертности в развивающихся странах. В промышленно развитых странах доступность лекарств и вакцин привели к росту уверенности в том, что эта угроза практически преодолена. Однако неожиданное и быстрое распространение таких эпидемий, как малярия, СПИД, туберкулез, грипп снова сделали актуальной борьбу с инфекционными заболеваниями. В современной эпидемиологической динамике инфекционных болезней произошел переход от классического описательного подхода роста или уменьшения числа заражённых к математическому моделированию передачи, распространению и заражению инфекцией. В эпидемиологии моделирование стало применяться в исследовательских целях для прогнозирования характера эпидемического процесса и для определения стратегии действий служб здравоохранения [27-29, 36-37, 39, 41-42, 49, 122, 148, 181].

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

Будем назвать процессы пространственного распространения и вре-

V* 1 \ V/

менного изменения этих двух групп эпидемии инфекционнои динамикои.

Обычно трудно реализуемые пространственные составляющие динамики в предлагаемых моделях берёт на себя топология предфрактального графа, которая наращивается объёмными графами - затравками, а динамика наращения предфрактального графа, называемая его распознаванием, отвечает за временную составляющую процесса. Познавательная роль моделей инфекционной динамики определяется их сущностью, предполагающей выявление взаимосвязей многочисленных параметров эпидемического процесса. Модель должна позволять судить о числе контактов, определять степень риска инфицирования, определять пороги заболевания, исследовать особенности возрастного и территориального распределения заболеваемости. Не менее важной функцией модели должно стать накопление статистики при описании многолетней динамики эпидемия, включая сезонные циклы, что открывает возможность более точного описания и прогнозирования тенденций, уровней развития основных показателей эпидемического процесса. Разумное использование методов математического моделирования эпидемического процесса может стать чрезвычайно полезным при планировании профилактических и противоэпидемических мероприятий, для выбора оптимальных путей борьбы с эпидемическим распространением людских и компьютерных вирусов. Хорошо организованная математическая модель, заменяя эпидемический процесс безопасно и количественно, дисциплинирует исследовательскую работу, систематизирует научные знания, приводит к появлению новых идей [43-45, 115,118-121].

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

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

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

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

При построении эпидемиологической модели различают несколько этапов:

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

• математическая формулировка модели с использованием наиболее экономных способов реализации и эффективных по времени решения;

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

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

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

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

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

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

Элементы того, что мы теперь называем математическим моделированием, использовались с начала появления точных наук и не случайно, что некоторые методы вычислений носят имена таких корифеев науки, как Ньютон и Эйлер, а слово «алгоритм» происходит от имени средневекового арабского ученого Аль-Хорезми. Второе рождение этой методологии пришлось на конец 40-ых - начало 50-ых годов ХХ-го века и было обусловлено, по крайней мере, двумя причинами. Первая из них - появление компьютеров, хотя и скромных по нынешним меркам, но тем не менее избавивших учёных от огромной по объёму рутинной вычислительной работы. Вторая - беспрецедентный социальный заказ - выполнение национальных программ СССР и США по созданию ракетно-ядерного щита, которые не могли быть реализованы традиционными методами. Математическое моделирование справилось с этой задачей: ядерные взрывы и полёты ракет и спутников были предварительно осуществлены в недрах компьютеров с помощью математических моделей и лишь затем претворены на практике. Этот успех во многом определил дальнейшие достижения методологии, без применения которой ни один крупномасштабный технический, экологически или экономический проект в

развитых странах теперь всерьёз не рассматривается.

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

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