Geum.ru
Авторефераты по всем темам  >>  Авторефераты по техническим специальностям  

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

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

Математические модели

инфекционной динамики

на основе

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

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

численные методы и комплексы программ

АВТОРЕФЕРАТ

диссертации на соискание учёной степени

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

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

Работа выполнена в ФГБОУ ВПО Северо-Кавказская

государственная гуманитарно-технологическая академия

(Карачаево-Черкесская Республика, г. Черкесск)

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

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

профессор

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

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

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

профессор

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

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

профессор

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

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

Научно-исследовательский институт

прикладной математики и автоматизации

Кабардино-Балкарского научного центра РАН

(г. Нальчик)

Защита состоится л 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. Построение на предфрактальных графах математических моделей структуры распространения человеческих эпидемий, возможно, эпидемий диких и домашних животных, а также динамики вирусных атак в компьютерных сетях.

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

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

Достоверность и обоснованность

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

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

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

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

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

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

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

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

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

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

Апробация результатов исследования:

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

  1. Международная конференция Нелокальные краевые задачи и родственные проблемы математической биологии, информатики и физики, г. Нальчик, 2006 г.;
  2. VI-ая Международная конференция Когнитивный анализ и управление развитием ситуаций, г. Москва, 2006 г.;
  3. V-ая Международная конференция Математическое моделирование в образовании, науке и производстве, г. Тирасполь, 2007 г.;
  4. VI-ая научно-практическая конференция Проблемы синергетики в трибологии, трибоэлектрохимии, материаловедении и мехатронике, Новочеркасск, 2007 г.;
  5. II-ая Всероссийская научно-практическая конференция Перспективные системы и задачи управления, г. Таганрог, 2007 г.;
  6. Международная конференция, посвященная 100-летию со дня рождения академика И.Н. Векуа, г. Новосибирск, 2007 г.;
  7. III-я Всероссийская научно-практическая конференция Перспективные системы и задачи управления, г. Таганрог, 2008 г.;
  8. VIII-ая Международная конференция Методы и алгоритмы прикладной математики в технике, медицине и экономике, г. Новочеркасск, 2008 г.;
  9. VIII-ая региональная научно-практическая конференция Рациональные пути решения социально-экономических и научно-технических проблем региона, г. Черкесск, 2008 г.;
  10. Всероссийская электронная научная конференция Фундаментальные и прикладные проблемы математики, г. Москва, 2008 г.;
  11. IX-ый Всероссийский симпозиум по прикладной и промышленной математике, г. Москва, 2008 г.;
  12. X-ая региональная научно-практическая конференция Рациональные пути решения социально-экономических и научно-практических проблем региона, г. Черкесск, 2010 г.;
  13. V-ая Всероссийская научно-практическая конференция Перспективные системы и задачи управления, г.Таганрог, 2011 г.;
  14. XI-ая региональная научно-практическая конференция Рациональные пути решения социально-экономических и научно-практических проблем региона, г. Черкесск, 2011 г.

Публикации

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

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

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

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

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

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

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

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

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

Для предфрактального графа рёбра, появившиеся на -ом, , этапе порождения, будем называть рёбрами ранга . Новыми рёбрами предфрактального графа назовём рёбра ранга , а все остальные рёбра назовём старыми.

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

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

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

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

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

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

  1. Для мощности множества вершин существует непустое множество пар или кортежей длины два <n, L> таких, что ;
  2. Для мощности множества рёбер существует хотя бы одна пара (кортеж длины два) <n, L>, удовлетворяющая равенству
  3. Множество рёбер ранга есть объединение множеств рёбер-затравок, появляющихся после замещения каждой вершины графа ранга затравкой.

емма 1.1 Пусть в предфрактальном графе две вершины и принадлежат одной затравке () и имеет место смежность с некоторой вершиной , тогда вершина также принадлежит этой затравке

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

Теорема 1.1 Всякий предфрактальный граф с попарно непересекающимися старыми рёбрами и регулярной -вершинной затравкой степени является распознаваемым алгоритмом .

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

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

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

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

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

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

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

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

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

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

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

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

Рисунок 1 - Предфрактальный граф,

порождённый двумя полными

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

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

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

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

Рисунок 2 Ц  Граф , полученный из в результате разрушения в очагах заражения L-го ранга, показанных на рис. 1

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

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

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

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

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

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

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

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

-го ранга, будет разрушен по критерию 2(k,m) для всех , где и , .

Теорема 2.10 Всякий предфрактальный граф , порождённый двумя полными затравками с сохранением смежности старых рёбер, будет разрушен по критерию 3(k,D) при удалении хотя бы одной вершины -го ранга для всех .

Теорема 2.11 Всякий предфрактальный граф , порождённый двумя полными затравками с сохранением смежности старых рёбер, будет разрушен по критерию 3(k,D) при удалении хотя бы одной вершины -го ранга для любого , где .

Теорема 2.12 Всякий предфрактальный граф с двумя полными чередующимися затравками, с сохранением смежности старых рёбер и с очагами заражения -го ранга может быть разрушен по критерию 3(k,D) только для и , где, соответственно, и .

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

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

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

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

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

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

О диаметральных цепях в предфрактальных графах.

емма 3.1 В любом предфрактальном графе G = (V, E), порождённом регулярной n-вершинной затравкой H = (W, Q) степени s = n - 2, всякая его диаметральная цепь имеет периферийные вершины степени .

емма 3.2 В любом предфрактальном графе G = (V, E), порождённом регулярной n-вершинной затравкой H = (W, Q) степени s = n - 2, всякая его диаметральная цепь содержит два ребра ранга 1, четыре ребра ранга 2, восемь рёбер ранга 3, Е , 2l рёбер ранга l, т.е. d(Gk) 2d(Gk-1) + 1.

емма 3. 3 В любом предфрактальном графе G = (V, E) с непересекающимися старыми рёбрами, образованном двумя полными затравками H1 = (W1, Q1) и H2 = (W2, Q2), где , , всякая его диаметральная цепь содержит одно ребро ранга 1 и по два ребра остальных рангов.

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

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

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

42L - 2 (3.1)

Теорема 3.4 Для всякого предфрактального графа ранга , порождённого затравкой-звездой , справедлива следующая оценка величины его диаметра :  (3.2)

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

2(2L - 1)   (3.3)

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

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

  (3.4)

Теорема 3.8 Для всякого предфрактального графа G ранга L с затравкой-звездой справедлива верхняя достижимая оценка хроматического числа.

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

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

, (3.5)

. (3.6)

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

(3.7)

где  , - количество рёбер-затравок и .

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

(3.8)

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

Рисунок 3 - Граф как модель бытовых контактов между членами семьи, состоящей из четырёх человек

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В ДИССЕРТАЦИОННОМ ИССЛЕДОВАНИИ

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

  1. Для моделирования распространения инфекций разработан комплекс алгоритмов распознавания предфрактальных графов, порождённых различными классами затравок. Предложены и обоснованы алгоритмы их построения (распознавания);
  2. Исследованы основные характеристики предфрактальных графов, служащие базой для конструирования моделей распространения инфекций, порождаемых и моделируемых различными классами затравок. Получены оценки и числовые значения их топологических, метрических, хроматических характеристик;
  3. Изучена надёжность (безотказность, ремонтопригодность, долговечность) и условия разрушения предфрактальных графов, порождённых различными классами затравок. Построены соответствующие модели;
  4. Модели разрушения предфрактальных графов использованы для представления затухания инфекционных процессов (человеческих и компьютерных);
  5. На базе предфрактальных графов построены теоретико-графовые модели:
  • структуры бытовых контактов людей в некоторой социальной сети;
  • модели связей между операционными узлами в компьютерной сети.
  1. Введено понятие лэпидемического порога на взвешенных предфрактальных графах. Модель позволяет учитывать уровень иммунитета каждого отдельно взятого человека и степень защиты каждого компьютера в сети от определенного вируса - соответственно, человеческого или компьютерного;
  2. Рассчитаны условия локализации инфекции на каждом этапе развития эпидемии. Возможно выявление возможных кластеров заражения. Для безымунных эпидемий возможно выявление возможных очагов заражения;
  3. Для реализации полученных моделей и описанных характеристик с целью прогнозирования инфекционной динамики разработан программный комплекс.

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

СЛЕДУЮЩИЕ РАБОТЫ:

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

  1. Найманова И.Х., Кочкаров А.М. Об одной задаче распознавания предфрактального графа // Вестник Самарского государственного технического университета. - 2007. - № 1 . - С. 194-196. 0.22 п.л., в т.ч. автора 0.20 п.л.;
  2. Утакаева И.Х. Алгоритм распознавания предфрактального графа с затравкой регулярной степени // Обозрение прикладной и промышленной математики. - 2008. - Том 15. - Выпуск 3. - С. 531-533. 0.22 п.л.;
  3. Утакаева И.Х., Кочкаров Р.А. Алгоритмы распознавания предфрактальных графов с различными затравками // Известия Южного федерального университета (г. Таганрог). - 2010. - Том 102. - № 1. - С. 27-38. 0.88 п.л., в т.ч. автора 0.70 п.л.;
  4. Утакаева И.Х., Кочкаров А.А. К вопросу об алгоритмах распознавания предфрактальных графов // Научно-технические ведомости Санкт-Петербургского государственного политехнического университета. - 2010. - Том 103. - № 4. - С. 139-142. 0.33 п.л., в т.ч. автора 0.25 п.л.;
  5. Утакаева И.Х., Кочкаров Р.А. Алгоритмы распознавания предфрактальных графов с полными затравками // Известия Южного федерального университета (г.

Таганрог). - 2011. - Том 115. - № 2. - С. 14-19. 0.44 п.л., в т.ч. автора 0.4 п.л.;

  1. Утакаева И.Х. Структурный алгоритм распознавания предфрактального графа // Вестник Самарского государственного университета. Серия Физико-математические науки. - 2011. - № 3 (24). - С. 208-211. 0.33 п.л.

Публикации в других изданиях:

  1. Найманова И.Х. Задача распознавания предфрактального графа с регулярной n-вершинной затравкой степени s=n-2 // Материалы III-ей Международной конференции Нелокальные краевые задачи и родственные проблемы математической биологии, информатики и физики. - Нальчик: Издательство НИИ ПМА КБН - РАН, 2006. - С. 204-206. 0.22 п.л.;
  2. Найманова И.Х. Распознавание предфрактального графа с регулярной затравкой // Труды V-ой Международной конференции Математическое моделирование в образовании, науке и производстве. - Тирасполь: Издательство Приднепровского университета, 2007. - С. 23-24. 0.15 п.л.;
  3. Утакаева И.Х. Распознавание предфрактального графа с двумя затравками, если старые рёбра пересекаются // Материалы VI-ой научно-практической конференции Проблемы синергетики в трибологии, трибоэлектрохимии, материаловедении и мехатронике. - Новочеркасск: Центр оперативной полиграфии ЮРГТУ (НПИ), 2007. - С. 34-35. 0.15 п.л.;
  4. Утакаева И.Х. Распознавание предфрактального графа с двумя затравками, если старые рёбра не пересекаются // Материалы VI-ой научно-практической конференции Проблемы синергетики в трибологии, трибоэлектрохимии, материаловедении и мехатронике. - Новочеркасск: Центр оперативной полиграфии ЮРГТУ (НПИ), 2007. - С. 36-37. 0.15 п.л.;
  5. Утакаева И.Х., Эльканова Л.М. Оценка оптимального потока на предфрактальных орграфах // Сборник трудов II-ой Всероссийской научно-практической конференции Перспективные системы и задачи управления. - Таганрог: Издательство Таганрогского технологического института ЮФУ, 2007. - С. 180-183. 0.33 п.л., в т.ч. автора 0.30 п.л.;
  6. Утакаева И.Х., Эльканова Л.М. Распознавание предфрактального графа с двумя затравками // Сборник трудов II-ой Всероссийской научно-практической конф. Перспективные системы и задачи управления. - Таганрог: Издательство Таганрогского технологического ин-та ЮФУ, 2007. - С. 190-191. 0.15 п.л., в т.ч. авт. 0.10 п.л.;
  7. Утакаева И.Х. Об одной модели распознавания предфрактального графа // Тезисы докладов на Международной конференции, посвященной 100-летию со дня рождения академика И.Н. Векуа. - Новосибирск: Редакционно-издательский центр НГУ, 2007. - С. 634-635. 0.15 п.л.;
  8. Утакаева И.Х. Математические модели задач распознавания предфрактальных графов // Сборник трудов III-ей Всероссийской научно-практической конференции Перспективные системы и задачи управления. - Таганрог: Издательство Таганрогского технологического института ЮФУ, 2008. - С. 231-235. 0.40 п.л.;
  9. Утакаева И.Х. Числовые характеристики предфрактальных графов с различными затравками // Сборник трудов III-й Всероссийской научно-практической конференции Перспективные системы и задачи управления. - Таганрог: Издательство Таганрогского технологического института ЮФУ, 2008. - С. 248-251. 0.33 п.л.;
  10. Утакаева И.Х. Предфрактальный  граф с регулярной затравкой и его распознавание // Современные наукоёмкие технологии. - 2008. Вып. 2. - С. 150-152. 0.22 п.л.;
  11. Утакаева И.Х. Математическая модель задачи распознавания предфрактального графа с регулярной затравкой // Материалы VIII-ой Международной конф. Методы и алгоритмы прикладной математики в технике, медицине и экономике. - Новочеркасск: Центр операт. полиграфии ЮРГТУ (НПИ), 2008. - С. 19-21. 0.22 п.л.;
  12. Утакаева И.Х., Болуров Н.Н. Числовые характеристики предфрактальных графов с различными затравками и алгоритмы их распознавания // Материалы VIII-ой региональной научно-практической конференции Рациональные пути решения социально-экономических и научно-технических проблем региона. - Черкесск: Издательство Карачаево-Черкесской государственной технологической академии, 2008. - С. 205-206. 0.15 п.л., в т.ч. автора 0.10 п.л.;
  13. Утакаева И.Х. Распознавание предфрактальных графов с полными затравками // Материалы X-ой региональной научно-практической конференции Рациональные пути решения социально-экономических и научно-практических проблем региона. - Черкесск: Издательство Карачаево-Черкесской государственной технологической академии, 2010. - С. 46-47. 0.15 п.л.;
  14. Утакаева И.Х., Кочкаров А.М. Моделирование процесса распространения эпидемии и нахождения возможных очагов заражения на предфрактальном графе // Сборник трудов III-ей Всероссийской научно-практической конференции Перспективные системы и задачи управления. - Таганрог: Издательство Таганрогского технологического института ЮФУ, 2011. - С.273-283. 0.8 п.л., в т.ч. автора 0.7 п.л.
  15. Утакаева И.Х. Моделирование структуры распространения эпидемии на предфрактальных графах // Материалы XI-ой региональной научно-практической конференции Рациональные пути решения социально-экономических и научно-практических проблем региона. - Черкесск: Издательство МП - Северо-Кавказской государственной гуманитарно-технологической академии, 2011. - С. 77-79. 0.22 п.л.

Свидетельства о государственной регистрации программ для ЭВМ:

  1. Утакаева И.Х., Кочкаров А.А. Распознавание предфрактального графа с двумя полными чередующимися затравками. Свидетельство № 2011615242 от 10 мая 2011г., зарегистрировано в Реестре программ для ЭВМ 5 июля 2011г. - 7 с., 0.50 п.л., в т.ч. автора 0.30 п.л.
  2. Утакаева И.Х. Распознавание предфрактального графа с регулярной затравкой. Свидетельство № 2011615243 от 10 мая 2011г., зарегистрировано в Реестре программ для ЭВМ 5 июля 2011г. - 7 с., 0.50 п.л.
  3. Утакаева И.Х. Моделирование структуры распространения эпидемии на предфрактальных графах. Свидетельство № 201161524 от 10 мая 2011г., зарегистрировано в Реестре программ для ЭВМ 5 июля 2011г. - 23 с., 1.80 п.л.

Подписано в печать 13.12.2011 г. Формат 60х84/16.

Бумага офсетная. Печать офсетная. Усл. печ. л. 1.0.

Заказ № 0670. Тираж 100 экз.

Издательство ФГБОУ ВПО СКГГТА

369000, КЧР, г. Черкесск, ул. Ставропольская, 36

Авторефераты по всем темам  >>  Авторефераты по техническим специальностям