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

• Автор: Каширин, Виктор Валерьевич
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2013
• Место защиты: Санкт-Петербург
• Количество страниц: 121 с. : ил.

СОДЕРЖАНИЕ
Введение

Глава 1 Аналитический обзор и обоснование постановки задачи

1.1. Понятие и примеры комплексных сетей

1.1.1. Терминология теории графов

1.1.2. Характеристики графов и их элементов

1.2. Математические модели комплексных сетей

1.2.1. Статические модели комплексных сетей

1.2.2. Динамические модели комплексных сетей

1.3. Особенности моделирования комплексных сетей

1.3.1. Ограничения традиционных математических моделей КС
1.3.2. Ограничения традиционных подходов к оптимизации КС
1.4. Алгоритмы поисковой оптимизации алгоритмы в задачах моделирования
1.4.1. Алгоритмы поисковой оптимизации
1.4.2. Применение поисковой оптимизации в задачах моделирования
комплексных структур
Выводы по главе
Глава 2 Метод математического моделирования и оптимизации комплексных сетей на основе эвристических алгоритмов
2.1. Решаемые классы задач
2.2. Моделирование комплексной сети как задача многокритериальной оптимизации
2.2.1. Критерии оптимальности
2.2.2. Целевая функция
2.3. Воспроизводимые свойства КС и критерии их оценки
2.3.1. Топологические свойства
2.3.2. Функциональные свойства комплексных сетей
2.4. Обеспечение сходимости процесса моделирования
2.4.1. Ограничения значений характеристик, накладываемые структурой КС.
2.4.2. Корреляции значений характеристик сети

Выводы по главе
Глава 3 Анализ и исследование алгоритмов моделирования и оптимизации комплексных сетей
3.1. Моделирование комплексной сети с помощью алгоритма имитации отжига
3.1.1. Алгоритм 8А моделирования структуры КС
3.1.2. Начальная структура сети
3.1.3. Виды воздействия на сеть
3.1.4. Особенности метода моделирования КС
3.1.5. Воспроизводимость характеристик традиционных моделей
комплексных сетей
3.1.6. Экспериментальное исследование методов моделирования
комплексных сетей на основе алгоритма имитации отжига
3.2. Оптимизация структуры комплексной сети с помощью генетического алгоритма
3.2.1. Алгоритм оптимизации структуры КС на основе ГА
3.2.2. Особенности метода оптимизации КС с помощью ГА
3.2.3. Экспериментальные исследование метода оптимизации КС на основе
генетического алгоритма
Выводы по главе
Глава 4 Приложения методов для исследования социальных сетей и процессов на них
4.1. Моделирование структуры социальных сетей и процессов на них
4.1.1. Моделирование структуры социальных сетей
4.1.2. Внедрение разработанных методов для иммунизации социальной сети.
4.2. Моделирование воздействий на криминальные сети
Выводы по главе
Заключение
Список использованных источников
ПРИЛОЖЕНИЕ А

Введение
Комплексные сети (КС) являются перспективной математической моделью для изучения свойств сложных систем1 (СС), позволяющей формализовать зависимость между их свойствами на микро- и макроуровнях. Работы M.E.J. Newman, A.L. Barabasi, A. Vespignani, S.II. Strogatz, J.M. Kleinberg и ряда других исследователей внесли существенный вклад в развитие теоретических основ и практических решений в области моделирования КС [1-7]. Процесс построения модели КС сводится к двум взаимосвязанным процедурам: статистическому анализу и собственно моделированию. Статистический анализ КС заключается в оценивании различных топологических характеристик сети [8]. На его основе формируется вероятностная модель КС, описывающая основные закономерности изменчивости характеристик узлов сети и связей между ними [9]. Статистическое моделирование сети позволяет, используя вероятностную модель, сформулировать алгоритм, воспроизводящий синтетическую КС необходимого размера с заданными топологическими характеристиками [10]. Недостатком существующих методов моделирования является ориентация воспроизводящих алгоритмов на отдельные классы КС2, что ограничивает свободу их применения в отношении более общих объектов, в первую очередь - неоднородных сетей, содержащих узлы различной природы . Частным случаем задачи моделирования КС является оптимизация структуры сети с учетом специфики информационных процессов в пей. Решение этой задачи осложняется тем, что ввиду неоднородности КС и пелокалыюсти информационных процессов в ней, как правило, отсутствует прямая связь между свойствами узлов и условиями оптимальности [11,12]. Это определяет актуальность развития общего подхода к моделированию КС с заданными топологическими характеристиками и оптимизации структуры сети, неспецифичного к классам неоднородности и видам информационных процессов.
1 Сложная система (complex system), но определению, отличается большим количеством элементов, допускающих дальние связи по принципу «каждый с каждым» и обладающих многомасштабной изменчивостью - с выделением мпкроуровня (отдельных элементов) и макроуровня (сети в целом).
2 Модель малого мира WS (Watts & Strogatz), модель случайного графа ER (Erdos & Renyi), модель предпочтительного добавления BA (Barabasi & Albert), конфигурационная модель и пр.

было получено при анализе данных реальных сетей. Потому рассмотрим целевые функции оценки диаметра сети и средней длины ее кратчайших путей.
Пусть с1°- желаемое значение диаметра сети, а ЕЛат{С) - метрика оценки диаметра сети О. Тогда критерий оптимальности по диаметру сети можно выразить следующим образом:
Аналогично для средней длины кратчайших путей: пусть 1° - желаемое значение средней длины путей, а /ДС) - метрика оценки этой характеристики на сети О. Тогда критерий оптимальности по средней длине кратчайших путей можно выразить следующим образом:
Другой полезной характеристикой, косвенно оценивающей расстояние между вершинами сети, является так называемая эффективность сети. Она оценивается по формуле:
Очевидно, О£(<3) = 1 когда граф является полным и £(0 = 0 когда он полностью разделен. Эффективность сети в общем случае выражает насколько быстро (в смысле расстояния между вершинами) вершины сети могут взаимодействовать друг с другом, передавая информацию по кратчайшим путям.
Пусть Е°— желаемое значение эффективности сети, а ££(С) - метрика оценки этой характеристики па сети в. Тогда критерий оптимальности по эффективности сети можно выразить следующим образом: