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

• Автор: Юдин, Евгений Борисович
• Шифр специальности: 05.13.01
• Научная степень: Кандидатская
• Год защиты: 2012
• Место защиты: Омск
• Количество страниц: 150 с. : ил.

СОДЕРЖАНИЕ
СПИСОК СОКРАЩЕНИЙ
ВВЕДЕНИЕ
ГЛАВА 1. МОДЕЛИРОВАНИЕ СЕТЕВЫХ СТРУКТУР И ПРОЦЕССОВ
1.1. Основные понятия
1.2. Решетки
1.2.1. Моделирование случайных отказов в решетках
1.2.2. Моделирование распространения вируса в решетках
1.3. Случайные графы
1.3.1. Графы Эрдеша-Реньи
1.3.2. Графы Уотса-Строгатса
1.3.3. Безмасштабные графы
1.3.4. Г рафы с нелинейным правилом предпочтительного связывания
1.3.5. Другие классы случайных графов
1.3.6. Моделирование случайных отказов в больших сетях
1.3.7. Моделирование распространения вируса в сетях
Выводы по первой главе
ГЛАВА 2. СТРУКТУРНАЯ ИДЕНТИФИКАЦИЯ
СЕТЕЙ ТИПА ИНТЕРНЕТ
2.1. Ускоренный метод генерации графа БА и графа с НППС
2.1.1. Базовый метод генерации графа БА
2.1.2. Ускоренный метод генерации графа БА
2.1.3. Статистические проверки структурных характеристик графов
2.2. Калибровка графов с НППС
2.2.1. Калибровка графа по эмпирическому РСС узлов
2.2.2. Генерация и калибровка ориентированного сл.г. с НППС
2.2.3. Аппроксимация функции предпочтения
2.2.4. Сепарабельная реконфигурация по коэффициенту кластеризации
Выводы по второй главе

ГЛАВА 3. НОВЫЕ КЛАССЫ СЛУЧАЙНЫХ ГРАФОВ
ЗЛ. Графы декомпозиции
3 Л Л. Г рафы декомпозиции для моделирования граф-схем алгоритмов
3 Л .2. Оценка эффективности редукции граф-схем надежности
3.2. Графы соседства
3.2Л. Генерация графов соседства
3.2.2. Устойчивость графов соседства к случайному удалению вершин/ребер
3.2.3. Моделирование распространения вируса на графе соседства
3.2.4. Модель «хищник-жертва» на графах соседства
Выводы по третьей главе
ГЛАВА 4. ПРОГРАММНЫЕ СРЕДСТВА МОДЕЛИРОВАНИЯ СЕТЕВЫХ СТРУКТУР И ПРОЦЕССОВ
4.1. Система агентного моделирования SIMBIGRAPH
4.1.1. Архитектура системы
4.1.2. Двухэтапный подход в моделировании сетевых процессов
4.1.3. Г енерация случайных графов
4.1.4. Имитационное моделирование сетевых процессов
4.1.5. Демонстрационный пример: моделирование сети Интернет
4.2. Реализация генератора графа соседства в многопроцессорной среде
4.2.1. Распределенное выполнение имитационных экспериментов
4.2.2. Г енерация графа соседства в распределенной среде
Выводы по четвертой главе
ЗАКЛЮЧЕНИЕ
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
Приложение А Исследование связности при случайном удалении вершин/ребер в графах соседства
Приложение Б SIRS модель в системе SIMBIGRAPH
Приложение В Акты внедрения и свидетельства о регистрации

СПИСОК СОКРАЩЕНИЙ
AC - автономная система
БСВ - базовая случайная величина
БСС - большая стохастическая сеть
ВС - вычислительная система
граф БА - граф Барабаши-Альберт
граф с НППС - граф с нелинейным правилом предпочтительного связывания
ГСА - граф-схемы алгоритмов
ГСН - граф-схемы надежности
ГТТК - гранецентрированная кубическая
ДСВ - дискретная случайная величина
ИМ - имитационное моделирование
КМ - конфигурационная модель
PC - распределенные в пространстве статистически од-
нородные структуры
РСС - распределение степени связности
СИМ - система имитационного моделирования
сл.в. - случайная величина
сл.г. - случайный граф
ф.р.в. - функция распределения вероятностей
BGP - Border Gateway Protocol
(протокол граничного шлюза)
MPI - Message Passing Interface
MPMD - Multiple Program Multiple Data
(множество программ - множество потоков данных)
SIRS - Susceptible - Infected - Recovered - Susceptible
(восприимчивый - инфицированный - невосприимчивый - восприимчивый)
SIS - Susceptible-Infected-Susceptible (восприимчивый-
инфицированный - восприимчивый)

3456789 3456789
Рис. 1.17. Гистограммы распределения степени вершин в сл.г. с НППС: а) равномерное; б) треугольное; в) экспоненциальное РСС при выращивании графов из 1000 вершин
В работе [21] В. Н. Задорожным предлагается также граф с НППС со случайным приращением (случайное число ребер для присоединения). Для такого графа также может быть выполнена калибровка по эмпирическому РСС узлов. На рис. 1.18 изображено РСС вершин графа, полученного с помощью генератора сл.г. с НППС путем калибровки параметров генератора в соответствии с данными о РСС сети маршрутизаторов. Используемая функция предпочтения имеет вид f(k) = у-к + ß, где у= 1,493, ß = 0,548. Как можно видеть на рис. 1.18, калиброванные графы с НППС могут иметь РСС вершин значительно лучше согласующееся с РСС узлов реальной сети, чем граф БА, см. рис. 1.15.
Рис. 1.18. РСС вершин в графе с НППС и РСС узлов сети маршрутизаторов Интернет
1.3.5. Другие классы случайных графов
Рассмотренные случайные графы Эрдеша-Реньи, Уотса-Строгатца и Бара-баши-Альберт являются на данный момент самыми распространенными при моделировании сетей. Так, на каждую из работ [73, 117], опубликованных около де-