Содержание к диссертации
Введение
Глава 1 Аналитический обзор и обоснование постановки задачи 7
1.1. Понятие и примеры комплексных сетей 7
1.1.1. Терминология теории графов 8
1.1.2. Характеристики графов и их элементов 10
1.2. Математические модели комплексных сетей 16
1.2.1. Статические модели комплексных сетей 16
1.2.2. Динамические модели комплексных сетей 18
1.3. Особенности моделирования комплексных сетей 19
1.3.1. Ограничения традиционных математических моделей КС 20
1.3.2. Ограничения традиционных подходов к оптимизации КС 22
1.4. Алгоритмы поисковой оптимизации алгоритмы в задачах моделирования 24
1.4.1. Алгоритмы поисковой оптимизации 24
1.4.2. Применение поисковой оптимизации в задачах моделирования комплексных структур 29
Выводы по главе 1 30
Глава 2 Метод математического моделирования и оптимизации комплексных сетей на основе эвристических алгоритмов 31
2.1. Решаемые классы задач 31
2.2. Моделирование комплексной сети как задача многокритериальной оптимизации 31
2.2.1. Критерии оптимальности 31
2.2.2. Целевая функция 32
2.3. Воспроизводимые свойства КС и критерии их оценки 33
2.3.1. Топологические свойства 33
2.3.2. Функциональные свойства комплексных сетей 40
2.4. Обеспечение сходимости процесса моделирования 43
2.4.1. Ограничения значений характеристик, накладываемые структурой КС 43
2.4.2. Корреляции значений характеристик сети 44
Выводы по главе 2 46
Глава 3 Анализ и исследование алгоритмов моделирования и оптимизации комплексных сетей 47
3.1. Моделирование комплексной сети с помощью алгоритма имитации отжига 47
3.1.1. Алгоритм SA моделирования структуры КС 47
3.1.2. Начальная структура сети 50
3.1.3. Виды воздействия на сеть 52
3.1.4. Особенности метода моделирования КС 58
3.1.5. Воспроизводимость характеристик традиционных моделей комплексных сетей 61
3.1.6. Экспериментальное исследование методов моделирования комплексных сетей на основе алгоритма имитации отжига 65
3.2. Оптимизация структуры комплексной сети с помощью генетического алгоритма 72
3.2.1. Алгоритм оптимизации структуры КС на основе ГА 72
3.2.2. Особенности метода оптимизации КС с помощью ГА 76
3.2.3. Экспериментальные исследование метода оптимизации КС на основе генетического алгоритма 77
Выводы по главе 3 82
Глава 4 Приложения методов для исследования социальных сетей и процессов на них 83
4.1. Моделирование структуры социальных сетей и процессов на них 83
4.1.1. Моделирование структуры социальных сетей 83
4.1.2. Внедрение разработанных методов для иммунизации социальной сети 90
4.2. Моделирование воздействий на криминальные сети 94
Выводы по главе 4 107
Заключение 108
Список использованных источников 110
Приложение А 121
- Алгоритмы поисковой оптимизации
- Топологические свойства
- Экспериментальное исследование методов моделирования комплексных сетей на основе алгоритма имитации отжига
- Внедрение разработанных методов для иммунизации социальной сети
Введение к работе
Актуальность темы. Комплексные сети (КС) являются перспективной математической моделью для изучения свойств сложных систем (СС), позволяющей формализовать зависимость между их свойствами на микро- и макроуровнях. Работы M.E.J. Newman, A.L. Barabasi, A. Vespignani, S.H. Strogatz, J.M. Kleinberg и ряда других исследователей внесли существенный вклад в развитие теоретических основ и практических решений в области моделирования КС. Процесс построения модели КС сводится к двум взаимосвязанным процедурам: статистическому анализу и собственно моделированию. Статистический анализ КС заключается в оценивании различных топологических характеристик сети. На его основе формируется вероятностная модель КС, описывающая основные закономерности изменчивости характеристик узлов сети и связей между ними. Статистическое моделирование сети позволяет, используя вероятностную модель, сформулировать алгоритм, воспроизводящий синтетическую КС необходимого размера с заданными топологическими характеристиками. Недостатком существующих методов моделирования являет-ся ориентация воспроизводящих алгоритмов на отдельные классы КС , что ограничивает свободу их применения в отношении более общих объектов, в первую очередь - неоднородных сетей, содержащих узлы различной природы. Частным случаем задачи моделирования КС является оптимизация структуры сети с учетом специфики информационных процессов в ней. Решение этой задачи осложняется тем, что ввиду неоднородности КС и нелокальности информационных процессов в ней, как правило, отсутствует прямая связь между свойствами узлов и условиями оптимальности. Это определяет актуальность развития общего подхода к моделированию КС с заданными топологическими характеристиками и оптимизации структуры сети, неспецифичного к классам неоднородности и видам информационных процессов.
Предметом исследования является технология моделирования и оптимизации КС применительно к задачам исследования сложных распределенных систем и динамики процессов, протекающих в них.
Целью работы является разработка и оптимизация методов построения неоднородных КС, неспецифичных к классам неоднородности и видам информационных процессов в них, на основе эвристических алгоритмов.
1 Сложная система (complex system), по определению, отличается большим количеством элементов, допускаю
щих дальние связи по принципу «каждый с каждым» и обладающих многомасштабной изменчивостью - с вы
делением микроуровня (отдельных элементов) и макроуровня (сети в целом).
2 Модель малого мира WS (Watts & Strogatz), модель случайного графа ER (Erdos & Renyi), модель предпочти
тельного добавления ВА (Barabasi & Albert), конфигурационная модель и пр.
3 Под эвристическими понимаются, в частности, метод спуска, алгоритм имитации отжига и генетический алго
ритм.
4 Задачи исследования:
анализ и обоснование требований к методу моделирования неоднородных КС общего вида, исходя из обзора существующих математических моделей КС с заданными характеристиками;
разработка и обоснование метода построения КС на основе эвристических алгоритмов;
разработка и обоснование метода оптимизации топологических и функциональных характеристик КС на основе эвристических алгоритмов;
экспериментальное исследование характеристик разработанных методов и их сравнение с существующими аналогами для моделирования и оптимизации КС;
оценка возможности применения предложенных решений для исследования, моделирования и оптимизации структуры социальных сетей в Интернете и сетей криминальных сообществ.
Методы исследования включают в себя методы анализа СС, теории КС, теории графов, поисковых алгоритмов оптимизации, искусственного интеллекта, теории вероятностей и математической статистики.
Научная новизна заключается в использовании эвристических алгоритмов для моделирования и оптимизации КС, что позволяет унифицировать процедуру модельного воспроизведения структуры КС с заданными топологическими характеристиками, с учетом вида их неоднородности и особенностей протекания информационных процессов.
Практическую ценность работы составляют программный комплекс моделирования и оптимизации структуры неоднородных КС, а также результаты применения разработанных моделей, методов и алгоритмов в части исследования устойчивости сетей криминальных сообществ .
На защиту выносятся:
алгоритм моделирования структуры неоднородной КС с помощью алгоритма имитации отжига;
алгоритм оптимизации структуры КС на основе генетического алгоритма.
Достоверность научных результатов и выводов подтверждается обоснованностью применения математического аппарата, строгостью наложенных ограничений, оценкой адекватности математических моделей, результатами тестирования алгоритмов и программного обеспечения, сопоставлением результатов моделирования с экспериментальными данными, а также успешным применением разработанных математических, алгоритмических и программных методов и средств для решения прикладных задач.
4 Данные предоставлены управлением внутренних дел Королевства Нидерланды.
Внедрение результатов работы. Результаты использованы при выполнении следующих НИОКР: «Разработка web-ориентированного производственно-исследовательского центра в области социодинамики и ее приложений» ФЦП «Исследования и разработки по приоритетным направлениям развития научно-технического комплекса России на 2007-2013 гг.», «Распределенные экстренные вычисления для поддержки принятия решений в критических ситуациях», «Исследования и разработки по приоритетным направлениям развития научно-технологического комплекса России на 2007-2013 гг.» в рамках реализации постановления Правительства РФ № 220 «О мерах по привлечению ведущих ученых в российские образовательные учреждения высшего профессионального образования».
Апробация работы. Основные результаты работы обсуждались на международных и всероссийских конференциях, семинарах, совещаниях и круглых столах, включая XIV Всероссийскую объединенную научную конференцию «Интернет и современное общество» (Санкт-Петербург, 2011), XI Всероссийскую конференцию «Высокопроизводительные параллельные вычисления на кластерных системах» (Нижний Новгород, 2011), Международную научно- практическую конференцию молодых ученых и специалистов «Технологии высокопроизводительных вычислений и компьютерного моделирования» (Амстердам, 2012), XV Всероссийскую объединенную конференцию «Интернет и современное общество» (Санкт-Петербург, 2012), «International Conference of Computational Science» (Барселона, 2013), XX Всероссийскую научно-методическую конференцию «Телематика'2013» (Санкт-Петербург, 2013).
Публикации. По материалам диссертации опубликовано 6 печатных работ, в том числе 3 - в изданиях из перечня ВАК РФ и 1 свидетельство о регистрации программы для ЭВМ.
Личный вклад автора в работах, выполненных в соавторстве, заключается в выполнении аналитического обзора в проблемной области диссертационной работы; обосновании требований к методам моделирования и оптимизации КС на основе эвристических алгоритмов; проведении экспериментальных исследований и интерпретации их результатов. Из работ, выполненных в соавторстве, в диссертацию включены результаты, которые соответствуют личному участию автора.
Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы (120 наименований) и 1 приложения; содержит 121 страницу текста, включая 45 рисунков и 11 таблиц.
Алгоритмы поисковой оптимизации
Среди алгоритмов решения задач поисковой оптимизации простейшим является метод спуска. Процесс поиска начинается со случайно выбранной точки из пространства поиска решений задачи. На каждой итерации рассматриваются точки, соседние с текущей. Если некоторая из этих точек представляет собой улучшенное решение по сравнению с текущей, то она становится текущей на следующей итерации. В противном случае поиск считается оконченным, а текущая точка — оптимальным решением.
Главным недостатком метода спуска является то, что найденное решение будет являться локальным оптимумом, который может оказаться существенно хуже глобального.
Еще одним вариантом метода спуска является метод спуска на основе случайных мутаций. В данном методе к текущему решению на каждом шаге применяется случайное локальное изменение (мутация), и полученное решение сравнивается с текущим. Если оно не оказывается не хуже, то оно становится текущим. Если в течение некоторого числа итераций не происходит улучшения значения функции приспособленности, то происходит перезапуск алгоритма.
Поисковый процесс продолжается до тех пор, пока не будет выполнен критерий остановки алгоритма (достигнуто определенное значение функции приспособленности или с момента запуска алгоритма прошел определенный промежуток времени).
1.4.1.2. Алгоритм имитации отжига
В 1983 году Киркпатрик и другие [37] предложили инновационную идею использования метода моделирования отжига (англ. Simulated Annealing, далее SA) для решения масштабных оптимизационных задач. С тех пор, метод имитации отжига был применен во множестве инженерных оптимизационных задач [38,39]. Простейший алгоритм процесса отжига заключается в нагревании объекта из твердого состояния в жидкое, и затем медленного охлаждения этого объекта. По мере уменьшения температуры, энергия атомов тела уменьшается, а в момент кристаллизации энергия объекта будет минимальной. На основе концепции отжига, для решения оптимизационных задач был разработан метод имитации отжига. Для избегания попадания решения в состояние локального оптимума в процедуре SA используется критерий Метрополиса .
Общая схема работы алгоритм SA изображена на рис. 1.5. На первом шаге моделирования производится генерация начального решения, взятого из произвольной точки пространства поиска. Данное решение принимается за текущее оптимальное. На втором шаге текущее оптимальное решение модифицируется так, чтобы получить некоторую точку пространства поиска из небольшой окрестности текущего оптимального решения. Если полученное решение лучше предыдущего, или же если полученное решение удовлетворяет критерию Метрополиса, то оно принимается за текущее лучшее решение. В противном случае продолжается модификация текущего оптимального решения. Как правило, после определенного количества итераций алгоритма температура понижается согласно фактору понижения температуры R, даже если не было получено никакого улучшения текущего решения.
Критерий Метрополиса применяется для того, чтобы гарантировать относительно высокую вероятность того, что система не окажется в области локального оптимума.
Схема охлаждения системы является одной из важнейших характеристик применяемого метода. Охлаждение должно быть спланировано таким образом, чтобы система не остыла слишком рано, оказавшись тем самом в положении локального оптимума, но при этом стремилась к достижению глобального оптимума со скоростью более высокой, чем случайный поиск.
Работа алгоритма заканчивается когда SA получает решение, удовлетворяющее критерию остановки. Как правило, критерий остановки выполняется когда температура опускается до или разница между оптимальным значением оптимизируемой функции и полученным на данной итерации решением достигает или не достигает определенного значения.
1.4.1.3. Генетический алгоритм
Генетический алгоритм (ГА) являет собой метод оптимизации, использующий принцип естественного отбора для получения наилучшего решения [40-42].
В общем виде принцип естественного отбора формулируется следующим образом: наименее приспособленные особи умирают раньше, а наиболее приспособленные выживают и дают потомство. Потомство выживших особей оказывается в среднем более приспособленным, но среди них опять выделяются более приспособленные особи, и т. д.
В генетических алгоритмах оптимизации используется аналогичный принцип. В качестве особей выступают элементы пространства возможных решений некоторой задачи (маршруты коммивояжера, строение некоторого физического объекта и т. п.). Задан набор генетических операций, с помощью которых из существующих особей формируются новые. Кроме этого определена так называемая функция приспособленности, которая показывает насколько «хорошим» решением задачи является особь.
Генетические алгоритмы, в отличие от метода спуска и метода имитации отжига, ведут поиск решений не в одной, а в нескольких точках пространства поиска. Вначале работы алгоритма случайным образом генерируется некоторое число решений-особей, из которых формируется поколение. Существует множество стратегий отбора особей для следующего поколения: некоторые из них обеспечивают попадание наилучших особей в следующее поколение, другие Далее, особи текущей популяции скрещиваются между собой и мутируют, формируя новое поколение. Скрещивание особей является фундаментальной операцией в генетических алгоритмах, обеспечивающий обмен генетическим материалом между особями. Такой же по важности является операция мутации, которая позволяет получать новый генетический материал, а также предотвращать алгоритм от остановки в области локального оптимума.
Процесс работы генетического алгоритма состоит в генерации поколений особей до тех пор, пока не будет выполнено некоторое условие останова (например, достигнуто целевое значение функции приспособленности или сгенерировано заданное число поколений). На рис. 1.6 приведена общая схема работы генетического алгоритма.
В классическом генетическом алгоритме особь кодируется строкой над небольшим алфавитом (как правило, это битовая строка), по аналогии с хромосомой, кодирующей наследственную информацию в живых организмах. По этой причине особь генетического алгоритма нередко также называют хромосомой. Для битовых строк известно несколько стандартных операций скрещивания и мутации.
1.4.1.4. Многокритериальная оптимизация
Большинство сложных систем представляют собой совокупность нескольких субъектов, сложным образом взаимодействующих друг с другом. Зачастую, рассмотрение задачи оптимизации такой системы подразумевает наличие множества целевых функции, отвечающих определенным целям, и необходимость в определенной степени удовлетворить всем из них. При этом, получение решения, при котором удовлетворяются все целевые функции, как правило невозможно, поскольку целевые функции могут находиться в конфликте друг с другом [43].
Потому, решение задачи оптимизации предполагает наличие не одного решения, а множества решений, в разной степени удовлетворяющих множеству целевых функций. Такое множество решений называют множеством решений, оптимальных по критерию Парето, что означает, что из каждого решения, входящего в это множество, невозможно получить решение, лучшее хотя бы по одної! из целевых функций, не уменьшив оптимальность хотя бы по одной из других целевых функций.
Существует множество методов решения задачи многокритериальной оптимизации с помощью эволюционных алгоритмов, алгоритма имитации отжига [44-46]. Различия заключаются в способах получения решений на фронте Паре-то. Наиболее простым методом является использование взвешенной целевой функции, которая представляет собой сумму значений целевых функций, каждому из которых присвоен определенный вес. Задание весов определяет предпочтительность достижения оптимума по тому или иному критерию оптимальности [45,47-49].
Топологические свойства
2.3.1.1. Число компонент связности и плотность
Простейшим критерием оптимальности может служить число компонент связности сети. Пусть с0- желаемое число компонент связности, a F (G) метрика числа компонент связности сети G. Тогда критерий оптимальности по числу компонент связности можно выразить следующим образом.
Однако, в таком виде критерий оптимальности оказывается полезен только при с0 = 1, поскольку в таком случае обеспечивается полная связность сети и отсутствие узлов со степенью 0. Как показало моделирование, при с" 1 алгоритм склонен удовлетворять критерию за счет создания изолированных вершин. Однако вызванной необходимости в получении сети с определенным числом компонент связности, большим чем одна, как правило, нет. В дальнейшем, подразумевая что с = 1, будем писать.
Еще одним простым критерием оптимальности является плотность сети. Пусть - желаемое значение плотности, a Fdenslt(G) - метрика плотности сети G. Тогда критерий оптимальности по плотности сети можно выразить следующим образом.
2.3.1.2. Кластеризация (транзитивность)
Другим важным критерием оптимальности служит коэффициент кластеризации. Пусть С0- желаемое значение кластеризации сети, a Fclllsterisalim(G) метрика значения кластеризации сети G. Тогда критерий оптимальности по значению кластеризации можно выразить следующим образом. Здесь стоит обратить внимание на тот факт, что для оценки кластеризации используется метрика значения глобальной кластеризации сети, а не среднее значение локальной кластеризации узлов. Эти два метода оценки кластеризации дают существенно разные значения на большинстве типов сетей, и более точным считается первый способ [14].
2.3.1.3. Диаметр, средняя длина кратчайших путей и эффективность сети
В некоторых задачах может понадобиться воспроизведение сети, характеризующейся конкретным значением диаметра сети, или средней длины кратчайших путей. Так, эффект малого мира может быть выражен просто как минимальное значение длины кратчайших путей при заданных характеристиках сети , но также может быть задано конкретное значение этой характеристики, которое было получено при анализе данных реальных сетей. Потому рассмотрим целевые функции оценки диаметра сети и средней длины ее кратчайших путей.
Пусть d- желаемое значение диаметра сети, a Fdbm(G) - метрика оценки диаметра сети G. Тогда критерий оптимальности по диаметру сети можно выразить следующим образом:
Аналогично для средней длины кратчайших путей: пусть Т- желаемое значение средней длины путей, a Ft(G) - метрика оценки этой характеристики на сети G. Тогда критерий оптимальности по средней длине кратчайших путей можно выразить следующим образом.
Другой полезной характеристикой, косвенно оценивающей расстояние между вершинами сети, является так называемая эффективность сети. Она оценивается по формуле.
Очевидно, Os(G)sl, (G) = 1 когда граф является полным и E(G) = 0 когда он полностью разделен. Эффективность сети в общем случае выражает насколько быстро (в смысле расстояния между вершинами) вершины сети могут взаимодействовать друг с другом, передавая информацию по кратчайшим путям.
Пусть Е— желаемое значение эффективности сети, a FE(G) - метрика оценки этой характеристики на сети G. Тогда критерий оптимальности по эффективности сети можно выразить следующим образом.
2.3.1.4. Распределение степенен
Воспроизведение распределения степеней вершин сети является важнейшей задачей моделирования, поскольку оно во многом отражает принцип, по которому организуются связи в сети. Для создания воспроизводства желаемого распределения предлагается использовать два взаимозаменяемых подхода.
Первый подход базируется на оценке распределения с помощью метода наилучшего правдоподобия (англ. maximum likelihood estimation, MLE). В частности, использование такого подхода для оценки распределения степеней узлов на соответствие степеппому закону распределения было обосновано в работах Ныомана [58], и является наиболее подходящим, по сравнению с ранее предложенными методами [59].
При использовании данного подхода для определения параметров степенного распределения на выходе дается две оценки - показатель степени и p-value. Их и предлагается использовать в функции критерия оптимальности. Пусть А -желаемый показатель распределения степеней вершин, a AG и ра - оценки, полученные с помощью MLE, где Ас это реальный показатель распределения степеней, а рс - p-value из расчетов критерия Колмогорова-Смирнова. Тогда критерий оптимальности сети G по признаку распределения степеней вершин па основе MLE определяется как.
Как следует из этого равенства, чем выше p-value и чем меньше разница между текущим и желаемым показателем степени распределения, тем ближе текущее решение к оптимальному.
В качестве второго подхода для оценки воспроизведения распределения предлагается использовать сравнение степенной последовательности моделируемой сети со степенной последовательностью, сформированной на основе того распределения, которое необходимо воспроизвести в сети. Этот подход напоминает конфигурационную модель, но с тем отличием, что степени вершин в начале моделирования не фиксированы и определены лишь конфигурацией сети, взятой в качестве начальной из всего пространства поиска.
Пусть DS(! = {k,k,....,kN} - желаемая степенная последовательность, отсортированная по не убыванию, a DS(G) = {kl,k2,....,kN} - степенная последовательность сети в текущем состоянии, так же отсортированная по не убыванию. Различие между текущей и желаемой степенной последовательностью будем оценивать с помощью расстояния Хэмминга: d(DS,DS(G)) = J -JX" ,-)2, при этом, поскольку степень к любой вершины в графе без кратных ребер и петель ограничена 0 и N, то 0 s d(DS0,DS(G)) s N.
Тогда критерий оптимальности по признаку степенной последовательности оценивается.
Экспериментальное исследование методов моделирования комплексных сетей на основе алгоритма имитации отжига
Для проверки возможностей предложенного алгоритма моделирования КС предлагается рассмотреть задачи генерации сети с топологическими и функциональными свойствами, не заложенными в традиционные модели КС.
3.1.6.1. Моделирование сетей малого мира
Рассматривается задача генерации сети со свойствами высокой кластеризации и эффектом малого мира, характерными для многих социальных сетей. Традиционно для получения сетей с такими свойствами используется модель WS, которая на основе сети в виде регулярной решетки и с помощью процедуры перевязки ребер позволяет получить сеть с относительно высокой кластеризацией и малой средней длиной кратчайших путей. Путем варьирования вероятности осуществления перевязки каждого ребра структура получаемой комплексной сети может представлять собой различные промежуточные варианты сети между состоянием «регулярная решетка» (при/? = 0) до случайного графа (при/? = /).
Моделировалась сеть с фиксированным числом ребер т = Nc, при с = 2. Для наглядной визуализации число вершин N = 50. На рис. 3.7 представлено множество найденных с помощью моделей WS и SA решений, оптимальных по критерию Парето. Стоит подчеркнуть, что все решения обладают одинаковым количеством ребер и вершин.
Видно, что SA позволяет получить более выраженный эффект малого мира при аналогичных значениях кластеризации. Более того, SA позволяет получить решения с более высокой кластеризацией, которые невозможно получить с помощью модели WS. При этом данные решения не являются регулярной структурой (рис. 3.86), в отличие от решения с наибольшим значением кластеризации WS (рис. 3.8а).
3.1.6.2. Моделирование безмасштабных сетей
Аналогичные результаты наблюдаются при моделировании безмаштабных сетей с нестандартными характеристиками. На рис. 3.9 показан фронт Парето решений, полученных при моделировании безмасштабной сети с показателем степени 3 и числом узлов и ребер равным ста и двумстам соответственно, с максимальными значениями кластеризации при различной допустимой средней длине пути. Маркером ВА аннотированы характеристики кластеризации и средней длины путей у сети модели ВА с тем же числом ребер и вершин.
Стоит обратить внимание на тот факт, что в модели ВА заложена возможность получения сети с эффектом малого мира лишь одного типа - с относительно невысокой кластеризацией и малой средней длиной пути. Использование алгоритма SA позволяет получить ансамбль сетей с различной степенью выраженности той или иной характеристики. Визуализация структур получаемых сетей и их характеристик приведена на рисунке 3.10 (а-г).
3.1.6.3. Моделирование сети по функциональным характеристи кам
В качестве другого примера возможностей алгоритма SA рассматривается задача получения структуры сети на основе известных данных о ее функциональных характеристиках, то есть о ее макро-свойствах. Алгоритм проверки следующий:
1. Рассмотреть образцовую сеть и получить функциональные характеристи ки некоторого процесса на ней.
2. С помощью алгоритма SA построить структуру комплексной сети, достаточно точно воспроизводящей полученные на шаге 1 функциональные характеристики.
3. Сравнить характер протекания других процессов на образцовой сети, и структуре, полученной с помощью SA. Также получить результаты для случайной сети с той же плотностью, что и у образцовой сети. В качестве модельной сети была взята уже упомянутая ранее сеть аэропортов США из 500 узлов и 2980 ребер, а в качестве функциональных характеристик был рассмотрен процент зараженных узлов при протекании вируса, моделируемого с помощью SIR. Как показало моделирование, данных об одном функциональном процессе недостаточно для получения сети, с удовлетворительной способностью воспроизводить другие функциональные характеристики модельной сети, поэтому для построения были взяты две точки (см. табл. 3.4).
На рис. 3.11 показан контурный график, показывающий процент покрытия сети вирусом в зависимости от параметров модели SIR, а так же отображены точки X и Y, на основе которых осуществляется моделирование структуры сети.
На рис. 3.12а показан результат моделирования SIR на структуре сети, построенной с помощью алгоритма SA по точкам X и Y. В целевую функцию были включены только характеристики протекания SIR с параметрами X и Y, то есть никаких данных о топологических характеристиках сети задано не было.
На рис. 3.126 показано моделирование SIR на сети, полученной с помощью случайной сети, число ребер которой равняется числу ребер в образцовой сети. Сравнение рис. 3.126 с рисунком 3.12а показывает, что модели сети, полученной с помощью алгоритма SA, удается точнее воспроизводить характеристики протекания процесса SIR с различными параметрами по сравнению со случайной сетью. Таким образом, имея сведения лишь о функциональных характеристиках сети, применение алгоритма SA позволяет построить сеть, пригодную для осуществления предсказания поведения иных динамических процессов на сети.
Стоит отметить, что структура сети, полученной с помощью алгоритма SA, имеет большее число ребер по сравнению с оригинальной сетью, а именно 3221 против 2980. Более того, распределение степеней вершин такой сети соответствует распределению случайной сети, то есть пуассоновскому распределению, а не безмасштабному распределению степеней в сети аэропортов. Однако этот факт нельзя отнести к недостаткам алгоритма, поскольку в задачу входило воспроизведение структуры сети, имеющей те же функциональные характеристики, что и оригинальная сеть. При наличии гипотез или данных о топологических особенностях оригинальных сетей их также можно включать в целевую функцию, получая тем самым более точігую структуру комплексной сети.
Внедрение разработанных методов для иммунизации социальной сети
В данном разделе рассматривается задача исследования распространения инфекций в обществе. Многие инфекционные заболевания (СПИД, гепатит-С, туберкулез) носят ярко выраженный социальный характер, связанный с тем, что их распространение внутри разных слоев населения происходит по-разному и описываются различными моделями [78,82]. Данная проблема, в частности, может быть рассмотрена на примере распространения ВИЧ в гомо- и гетеросексуальной популяции. При этом ключевую значимость имеют механизмы передачи инфекции между разными слоями и средства противодействия им.
Связи в сетях такого типа указывают на наличие между людьми контактов, которые могут приводить к новым случаям заражения. При этом в ходе эволюции сети связи могут изменяться как за счет внешних факторов (демография, смертность и пр.), так и за счет внутренних, обусловленных сменой партнеров. Для противодействия развитию эпидемии используются различные стратегии вакцинации, которые в рамках модели комплексной сети сводятся к различным схемам цензурирования, т.е. удаления ряда узлов и (или) ребер в соответствии с задаваемыми правилами.
Как было сказано ранее, особенностью моделирования контактных сетей является существование различных их типов. Так, сети половых контактов людей гомо- и гетеро-сексуалыюй ориентации представляют собой безмасштабные сети с показателями степени 1.5 н 2.5 соответственно [19]. Из этого следует, что в сети половых контактов гомосексуалистов присутствует большое число так называемых супер-спридеров, и плотность такой сети выше, чем в сети гетеро-сексуалов. На основании этого можно сделать вывод, что для моделирования динамики процесса распространения вируса необходимо учитывать нсоднород ность структуры сети данного типа, а при решении задачи оптимизации - пользоваться эвристическим алгоритмом оптимизации для определения стратегии воздействия на сеть данного типа.
Моделирование на КС позволяет рассчитывать оптимальную стратегию вакцинации, адаптированную к заданной модели структуры сети и процессу распространения вируса, а так же оценивать эффективность выработанной стратегии в зависимости от числа вакцинируемых узлов.
Пример результатов моделирования процесса распространения вируса на безмасштабных сетях с одинаковым распределением степеней вершин но различными характеристиками кластеризации и ассортативности приведен на рис. 4.5.
Для выработки оптимальной стратегии вакцинации, и сравнения с традиционными стратегиями, основанными на метриках центральности, используется платформа облачных вычислений CLAVIRE [83]. Поиск оптимальной стратегии реализован в виде композитного приложения, которое позволяет разделить задачи моделирования и оптимизации сети между вычислительными узлами.
На рис. 4.6 приведена структура композитного приложения в CLAVIRE. Видно, что оно состоит из нескольких конкурирующих ветвей, каждая из которых реализует типовые стратегии вакцинации (включая поиск оптимальной стратегии с помощью ГА).
На рис. 4.7 приведен результат исполнения композитного приложения. Результатом работы этого композитного приложения является визуализация динамики возникновения зараженных и иммунных узлов в сети (см. рис. 4.8). Другим результатом работы является собственно профиль вакцинации в форме распределения доли вакцинируемых по количеству связей в сети.
На рис. 4.9 приведена характеристика эффективности стратегии вакцинации в зависимости от доли вакцинируемых узлов в общей сети, а на рис. 4.10 -полученные оценки профиля вакцинации для разного количества вакцинируемых. В частности, из рис. 4.9 видно, что при доле вакцинируемых более 7% эффективность уже не возрастает.
Профиль вакцинации, изображенный на рис. 4.10, и является конечной целью моделирования, показывая, на какие типы вершин необходимо ориентироваться при выборе стратегии вакцинации. Из рис. 4.10 следует, что для такого количества следует использовать профиль вакцинации с одномодальным распределением, пик которого соответствует узлам, имеющим 12 связей (при среднем числе связей в сети к 5).
