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

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

Каширин Виктор Валерьевич

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

Специальность: 05.13.18 — Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

28 НОЯ 2013

Санкт-Петербург 2013

005540555

005540555

Работа выполнена на кафедре информационных систем и в НИИ Наукоемких компьютерных технологий Санкт-Петербургского национального исследовательского университета информационных технологий, механики и оптики (НИУ ИТМО)

Научный руководитель: Бухановский Александр Валерьевич,

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

Официальные оппоненты: Гергель Виктор Павлович,

доктор технических наук, профессор, ННГУ им. Н.И. Лобачевского

Хоружников Сергей Эдуардович, кандидат физико-математических наук, доцент, НИУ ИТМО

Ведущая организация: Институт проблем передачи информации

им. A.A. Харкевича РАН, Москва

Защита состоится 19 декабря 2013 г. в 14:00 на заседании диссертационного совета Д 212.227.06 в Санкт-Петербургском национальном исследовательском университете информационных технологий, механики и оптики по адресу: 197101, Санкт-Петербург, Кронверкский пр., д. 49.

С диссертацией можно ознакомиться в библиотеке НИУ ИТМО.

Автореферат разослан 19 ноября 2013 г.

Ваши отзывы и замечания по автореферату (в двух экземплярах), заверенные печатью, просим направлять по адресу университета: 197101, Санкт-Петербург, Кронверкский пр., д. 49, ученому секретарю диссертационного совета Д 212.227.06.

Ученый секретарь диссертационного совета, кандидат физико-математических наук Лобанов И. С.

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

Актуальность темы. Комплексные сети (КС) являются перспективной математической моделью для изучения свойств сложных систем1 (СС), позволяющей формализовать зависимость между их свойствами на микро- и макроуровнях. Работы M.E.J. Newman, A.L. Barabasi, A. Vespignani, S.H. Strogatz, J.M. Kleinberg и ряда других исследователей внесли существенный вклад в развитие теоретических основ и практических решений в области моделирования КС. Процесс построения модели КС сводится к двум взаимосвязанным процедурам: статистическому анализу и собственно моделированию. Статистический анализ КС заключается в оценивании различных топологических характеристик сети. На его основе формируется вероятностная модель КС, описывающая основные закономерности изменчивости характеристик узлов сети и связей между ними. Статистическое моделирование сети позволяет, используя вероятностную модель, сформулировать алгоритм, воспроизводящий синтетическую КС необходимого размера с заданными топологическими характеристиками. Недостатком существующих методов моделирования является ориентация воспроизводящих алгоритмов на отдельные классы КС , что ограничивает свободу их применения в отношении более общих объектов, в первую очередь — неоднородных сетей, содержащих узлы различной природы. Частным случаем задачи моделирования КС является оптимизация структуры сети с учетом специфики информационных процессов в ней. Решение этой задачи осложняется тем, что ввиду неоднородности КС и нелокальности информационных процессов в ней, как правило, отсутствует прямая связь между свойствами узлов и условиями оптимальности. Это определяет актуальность развития общего подхода к моделированию КС с заданными топологическими характеристиками и оптимизации структуры сети, неспецифичного к классам неоднородности и видам информационных процессов.

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

Целью работы является разработка и оптимизация методов построения неоднородных КС, неспецифичных к классам неоднородности и видам информационных процессов в них, на основе эвристических3 алгоритмов.

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 таблиц.

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

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

Первая глава посвящена аналитическому обзору и обоснованию постановки задачи. Аппарат КС является эффективным инструментом изучения и моделирования СС. С помощью модели КС могут быть описаны сеть Интернет, физические и виртуальные социальные сети, эпидемиологические контактные сети, дорожно-транспортные сети, электрические схемы и пр. Исследование таких сетей показало, что для большинства из них характерны определенные общие свойства, а именно: высокая кластеризация, безмасштабность5 и свойство малого мира. Для воспроизведения этих характеристик было разработаны такие модели КС, как модель малого мира WS (Watts & Strogatz), модель случайного графа ER (Erdos & Renyi), модель предпочтительного добавления ВА (Barabasi & Albert), конфигурационная модель СМ и др. Построенные на основе таких априорных моделей алгоритмы генерации КС с разной степенью адекватности воспроизводят структуру сети в границах, соответствующих выбранному модельному описанию; при этом свойства сети, не заложенные в модель, воспроизводятся алгоритмом генерации со значительными искажениями.

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

Таким образом, проведенный анализ показывает, что применительно к КС общего вида путь, основанный на использовании априорных моделей сетей (WS, ВА, ER, СМ и др.) и априорных метрик эффективности, является, по-видимому, тупиковым. Особенно ярко это проявляется для неоднородных сетей, составленных из нескольких частично связанных между собой комплексных сетей. Несмотря на то что каждая из подсетей КС теоретически может быть описана одной из априорных моделей, задача кластеризации КС на подсети яв-

5 Scale-free property.

6 От англ. degree centrality, betweenness centrality, eigenvector centralily.

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

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

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

(для задачи моделирования);

- мера эффективности протекания заданного информационного процесса на

КС (для задачи оптимизации структуры).

Комплексная сеть представляется в виде графа С(у,Е), состоящего из непустого и конечного множества элементов V (вершин) и множества пар элементов Е (ребер). Характеристики КС выражаются через метрики, т.е. функции, заданные на графах или их элементах. Пусть задана функция - метрика графа б. Все возможные метрики такого вида можно разделить на топологические и функциональные. Топологические метрики выражают некоторое структурное свойство КС; их примерами являются диаметр графа; число вершин, не имеющих связей; число компонент связности; распределение степеней вершин; коэффициент кластеризации; средняя длина кратчайших путей между вершинами, число сообществ, модулярность и пр. Функциональные метрики отражают характеристики протекания определенного процесса в КС (например, среднее время доставки сообщения в сети); они целиком определяются спецификой моделируемого явления.

При решении задачи моделирования сети задается набор метрик Ф = ...,/<"„}, которые должны принимать соответствующие значения

П = {р1,р2,...,рп} на моделируемой сети О. На основе этих наборов определяется множество целевых функций:

П° = (1)

где (£?) = 1 при ^ (О = /о, и 0 £ (в) * 1, / = 1,2,..., п.

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

Задача моделирования КС сводится к построению графа G(V, Е) ранга N, на котором значение взвешенной суммы имеет глобальный максимум:

yV(G)='^jF0i{G)o,l. (2)

M

Здесь F°i(G),i = \,2,...,n — множество целевых функций, a mi, / = 1,2,..,п -множество весов, выражающих приоритетность метрик по отношению друг к другу:

О s 0,- s 1, i = 1,2.,.., и, а»! + а>2 + ...+ ft>„ = 1.

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

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

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

7 Motifs

Моделирование структуры сети

Задача: воспроизведение структуры сети с определенными топологическими свойствами.

Математические модели •Случайный граф •Конфигурационная модель

•Модель малого мира •Модель

предпочтительного добавления

Эвристические алгоритмы

Метод хшшат отжига

Моделирование структуры сети

Задача: воспроизведение структуры настоящей сети.

Построение сети, . ■*

Сбор данных

краулинг, анализ источников открытых данных

Анализ топологических характеристик

Распределение степеней узлов, кластеризация, ассортативность, средняя длина кратчайших путей, число сообществ.

Анализ функциональных характеристик

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

I

Оптимизация структуры сети

Модификация структуры сети или атрибутов ее элементов с целью достижения желаемых структурных или функциональных свойств.

Подход на основе метрик центральности: •Степенная »Промежуточная •Близостная •Сингулярная

Вьаделение значимых узлов с помощью поисковых методов

Генетический алгоритм

Рис. 1. Этапы построения и исследования модели КС

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

Третья глава посвящена исследованию методов и алгоритмов моделирования и оптимизации структуры КС.

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

поставление нескольких начальных состояний с выбором лучшего в соответствии с (2).

Для моделирования структуры сети от заданного начального состояния используется алгоритм имитации отжига (SA), включающий следующие шаги.

1. Задать эвристический параметр оптимизации - начальную «температуру системы» Т„.

2. Рассчитать текущую энергию системы - КС G: Ecurrent = 1 - 'lr(G).

3. Произвести воздействие на КС, получив новое решение G'.

4. Рассчитать новое значение энергии системы Enew = 1 - ^(G1).

5. Принять решение, полученное на шаге 3, с вероятностью

Paccept = ехР[~ J^j max (0> ^new ~ Еcurrent (3)

6. Понизить «температуру системы» Г согласно «схеме охлаждения». Если энергия системы больше заданного значения с (критерий сходимости), или температура не опустилась до предельно возможной, то увеличить номер итерации t и перейти на шаг 2. В противном случае - остановка алгоритма.

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

Г(Г) = -^-, (4)

1 + rt

где г — скорость охлаждения. Выбранная схема позволяет быстро перейти от грубого поиска в начале процесса моделирования к более детальному. Для обеспечения наилучшей сходимости в качестве параметров были выбраны значения Та = 0.03 и г =0.001.

Механизмы воздействия на КС в шаге 3 алгоритма включают в себя следующие процедуры:

1) удаление ребра между парой случайных вершин. Для случайной пары индексов вершин i и J, / * j : Ay = 0, где А - матрица смежности графа G;

2) добавление ребра между парой случайных вершин: для случайной пары индексов вершин / и j, i * j: Ay = 1;

3) добавление ребра между парой случайных вершин, разделенных путями длины 2, 3 или 4, т.е. соединение «друзей друзей»;

4) перевязка случайных ребер. Для двух пар вершин, соединенных ребром, i и j, шип: Ay = Am„ = 0,Aim = Ajn = 1;

5) перевязка ребер, инцидентных случайному ребру. Для вершин i,j, тип, таких что Ay = Ат, = Ajn = 1 и Атп = 0: Ami = А]п =0uAmj =Ат=\.

На каждом шаге алгоритма выполняется несколько воздействий одного типа (для каждой итерации тип выбирается случайным образом). Число воздействий на одном шаге зависит от конечной плотности КС: при недостаточном

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

Таблица 1

Зависимость оптимального числа воздействий на сеть от конечного числа _ребер при моделировании без.масштабной сети__

Число ребер сети 500 1000 2500 5000 6000 10000 15000

Оптимальное число воздействий 10 25 50 100 130 170 240

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

Проверка работоспособности алгоритма осуществляется следующим образом: а) исследуется воспроизводимость сетей с характеристиками, аналогичными характеристикам сетей на основе априорных моделей; б) исследуются возможности метода генерации сетей с расширенным, по сравнению с априорными моделями, диапазоном характеристик. Рассматривается задача генерации сети со свойствами высокой кластеризации и эффектом малого мира. Традиционно для получения сетей с такими свойствами используется модель которая на основе сети в виде регулярной решетки и с помощью процедуры перевязки ребер позволяет получить сеть с относительно высокой кластеризацией и малой средней длиной кратчайших путей. На рис. 2а представлено множество найденных с помощью моделей WS и 8А решений, оптимальных по критерию Парето. Видно, что ЗА позволяет получить более выраженный эффект малого мира при аналогичных значениях кластеризации. Более того, 8А позволяет получить решения с более высокой кластеризацией, которые невозможно получить с помощью модели WS. При этом данные решения не являются регулярной структурой (рис. 2в), в отличие от решения с наибольшим значением кластеризации \У8 (рис. 26). Аналогичные эффекты наблюдаются при моделировании безмаштабных сетей и сетей малого мира с нестандартными характеристиками.

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

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

При поиске подмножества узлов V', оказывающих наибольшее влияние на определенный информационный процесс, используется генетический алгоритм (ГА), который в принципе не использует априорные знания о топологических характеристиках узлов, или же использует их лишь для сужения пространства поиска решений. Хромосома индивида ГА состоит из подмножества V узлов V сети С(У,Е). Фитнес-функция индивида оценивается с помощью функционала Ч*(0'), рассчитываемого на графе полученном из б после удаления из него вершин, включенных в хромосому индивида: С'= С \ {V} ■

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

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

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

Эффективность решения демонстрируется на нескольких КС различного происхождения. В частности, рассматривается задача распространения эпидемии, в которой информационный процесс представляет собой распространение инфекции в контактной сети, и описывается с помощью модели SIR8. Целью оптимизации является определение стратегии вакцинации, т.е. выбор группы узлов, которые необходимо устранить из сети, чтобы минимизировать число зараженных узлов®. Для сравнения используются стратегии вакцинации на основе удаления узлов с наибольшей степенной (Со), промежуточной (Си) и сингулярной (СЕ) центральностями, а также без применения вакцинации. Во всех случаях вакцинации подвергалось только 10% узлов сети. Результаты сопоставления приведены в табл. 2.

Таблица 2

Сопоставление стратегий вакцинации узлов КС с помощью ГА и оценок цен-тралъностей в % зараженных узлов от общего числа узлов. В числителе указано среднее значение, в знаменателе - СКО_

Сеть Эффективность стратегии, %

название параметры ГА CD Св сЕ Без вакцинации

Социальная сеть школьников |V|=147 |Е|=202 3.21 3.84 4.53 10.94 15.7

2.54 3.03 4.32 10.42 14.38

Сеть аэропортов США |V|=500 |Е|=2980 3.1 4.38 13.8 9.6 78.6

2.23 3.57 11.7 6.8 14.85

Сеть роутеров |V|=11174 |Е|=23409 0.45 0.77 3.39 22.46 77.9

1.22 1.51 5.1 15.17 11.45

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

8 Susceptible - Infected - Removed.

9 Под заражением понимается успешный процесс передачи заданной информации от одного узла другому, вследствие чего состояние узла изменяется.

разбросу числа зараженных вершин по сравнению с другими стратегиями вакцинации, основанными на различных оценках центральностей. При этом средние значения количества зараженных узлов по стратегии вакцинации ГА и по стратегии на основе Со близки, что отражает природу процесса распространения инфекции: наиболее опасны узлы, имеющие большое число связей (т.н. су-перспридеры10), что отражено на рис. 3 и 4.

Степень узла

Рис. 3. Распределение степеней узлов, выбранных ГА для вакцинации в сети аэропортов США

Рис. 4. Сравнение стратегий на основе степенной центральности и ГА: А - узлы, выбранные обеими стратегиями; ■ -узлы, выбранные только ГА; □ - выбранные только Со (социальная сеть школьников)

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

В четвертой главе рассматриваются приложения предложенных методов и алгоритмов для изучения КС различной природы.

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

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

10 Super-spreaders

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

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

Получение информации о криминальных сетях связано с определенными рисками, поэтому объем таких данных, как правило, невелик и характеризуется избирательностью. Для статистически достоверного исследования путей разрушения сетей такого типа применяется алгоритм БА, который позволяет построить модельный ансамбль сценариев разрушения сетей, наследующих признаки исходной КС, воспроизведенной на основе реальных данных. Целевая функция строится на основе метрики «ассортативность»'1 по роли, отражающей характер формирования связей агентов с различными ролями.

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

На рис. 5 сравниваются стратегии вмешательства (стратегия на основе: 1 - степенной центральности узла; 2 — ответственности узла для процесса производства, характеризуемой числом ключевых элементов цепи - ребер, инцидентных данной вершине; 3 - стратегии, полученной на основе ГА). Как видно, применение традиционных стратегий только повышает эффективность сети, заставляя ее адаптироваться к измененной топологии, тогда как стратегия ГА позволяет снизить эффективность, поскольку не вызывает серьезных перестроений. Анализ ролей агентов (рис. 6), выбранных стратегиями для удаления из сети, показал, что традиционные стратегии выбирают агентов с ответственными и редкими ролями (координация, финансирование, экспорт), при потере связи с которыми узлы начинают искать им замену. В то же время ГА выбирает агентов, находящихся между центральными и периферийными узлами, роли которых (уход за плантацией, размещение плантации, продажа кофешопам) не исключительны, но удаление которых влечет уменьшение общей эффективности сети.

/^опапут

10 15 20 Число удаленных вершин

/ЩЩ?'

Рис. 5. Зависимость эффективности криминальной сети от выбора стратегии для ее разрушения

Рис. 6. Роли агентов, выбранных стратегиями для удаления

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

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

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

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

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

Дни

Рис. 7. Динамика процесса распространения вируса гриппа при различном числе вакцинируемых узлов, выраженном в процентах от общего числа узлов сети

На рис. 7 приведены результаты моделирования распространения инфекции, полученные по модели SIR на контактных сетях из 1000 узлов с различной долей узлов, вакцинированных с помощью ГА. Из рисунка видно, что при осуществлении наилучшей стратегии вакцинации достаточно 7% вакцинированных узлов для двадцатикратного уменьшения возможного числа заражений, при этом вакцинация большего числа вершин (9-11 %) не приводит к улучшению данного показателя, а лишь сокращает время процесса распространения.

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

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

- разработаны метод и алгоритм построения КС с заданными топологическими характеристиками на основе алгоритма имитации отжига;

- разработаны метод и алгоритм оптимизации топологических и функциональных характеристик КС на основе генетического алгоритма;

- экспериментально исследованы характеристики разработанных методов с целью оценки их эффективности по сравнению с существующими аналогами для моделирования и оптимизации КС;

- выполнена апробация разработанных методов для исследования криминальных и эпидемиологических КС.

Публикации по теме диссертационной работы

1. Kashir'm V. V., Dijkstra L.J. A Heuristic Optimization Method for Mitigating the Impact of a Virus Attack // Procedia Computer Science. 2013. Vol. 18. P. 26192628 [Входит в перечень ВАК].

2. Каширин В.В., Иванов С. В., Бухановский A.B., Слоот П.М.А. Планирование воздействия на криминальные системы на основе аппарата комплексных сетей // Информационно-измерительные и управляющие системы. 2012. № 11. С. 34-39 [Входит в перечень ВАК].

3. Иванов C.B., Болгова Е.В., Каширин В.В., Якушев A.B., Чугунов A.B., Бухановский А В. Web-ориентированный производственно-исследовательский центр «Социодинамика» // Изв. вузов. Приборостроение. 2011. № 10. С. 65-71 [Входит в перечень ВАК].

4. Каширин В.В. Метод выделения топологически значимых узлов комплексной сети на основе генетического алгоритма // XX Всероссийская научно-методическая конференция «Телематика'2013». СПб, 2013. С. 263-264.

5. Иванов C.B., Болгова Е.В., Каширин В.В., Якушев A.B., Чугунов A.B., Бухановский А. В., Слоот П.М.А. Веб-ориентированный центр в области социо-динамики: концепция и принципиальная архитектура // Тр. XIV Всеросс. объединенной конф. «Интернет и современное общество» (IMS-2011). СПб, 2011. С. 75-80.

6. Программная система анализа и моделирования информационных процессов в социальных сетях «SD/Dynamics» / B.B. Каширин, E.B. Болгова, A.B. Бухановский, П.М.А. Слоот. Св-во о гос. регистрации программы для ЭВМ № 2012617949 от 03.09.2012 г.

Подписано в печать « 19 » ноября 2013 г. Формах 60x84/16 Бумага офсетная. Печать офсетная. Усл.печ.л. 1,3- Тираж 110 экз. Заказ № 2

Типография «Восстания -1» 191036, Санкт-Петербург, Восстания, 1.

Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики ФГБОУ ВПО «НИУ ИТМО»

04201452928

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

Каширин Виктор Валерьевич

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

Специальность: 05.13.18 «Математическое моделирование, численные методы и

комплексы программ»

ДИССЕРТАЦИЯ на соискание ученой степени кандидата технических наук

Научный руководитель: д.т.н. Бухановский А.В.

Санкт-Петербург — 2013

СОДЕРЖАНИЕ

Введение..............................................................................................................................4

Глава 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. Алгоритм 8А моделирования структуры КС..............................................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

Введение

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

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

2 Модель малого мира WS (Watts & Strogatz), модель случайного графа ER (Erdos & Renyi), модель предпочтительного добавления ВА (Barabasi & Albert), конфигурационная модель и пр.

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

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

3

онных процессов в них, на основе эвристических алгоритмов.

Задачи исследования:

- анализ и обоснование требований к методу моделирования неоднородных КС общего вида, исходя из обзора существующих математических моделей КС с заданными характеристиками;

- разработка и обоснование метода построения КС на основе эвристических алгоритмов;

- разработка и обоснование метода оптимизации топологических и функциональных характеристик КС на основе эвристических алгоритмов;

- экспериментальное исследование характеристик разработанных методов и их сравнение с существующими аналогами для моделирования и оптимизации КС;

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

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

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

3 Под эвристическими понимаются, в частности, метод спуска, алгоритм имитации отжига и генетический алгоритм.

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

На защиту выносятся:

- алгоритм моделирования структуры неоднородной КС с помощью алгоритма имитации отжига;

- алгоритм оптимизации структуры КС на основе генетического алгоритма.

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

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

4 Данные предоставлены управлением внутренних дел Королевства Нидерланды.

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

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

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

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

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

С помощью моделей комплексных сетей решаются следующие задачи: воспроизведение структуры социальной сети с сохранением большинства нетривиальных топологических характеристик; масштабирование сети, то есть воспроизведение сети большего размера с сохранением ее характеристик; проверка гипотез с применением полученной структуры [9].

В качестве гипотез могут выступать самые различные исследовательские вопросы: устойчивость сети при удалении узлов, скорость распространения информации, избыточность сети, ассоциативность связей, устойчивость сообщений, передаваемых между узлами сети, к помехам и другие [17-23]. Однако для получения достоверных результатов необходимо максимально точно воспроизвести структуру сети, что подразумевает сохранение в структуре комплексной сети нетривиальных топологических характеристик, свойственных социальным сетям.

Рисунок 1.1- Составляющие эксперимента по исследованию комплексной

сети

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

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

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

Неориентированный (ориентированный) граф ОУ,Е) состоит из двух множеств У{Сг) и Е((3), таких что V * ф и Е(С) — конечное множество неупорядоченных (упорядоченных) пар элементов из У(С). Будем называть У(С) множеством вершин, а Е{р) — множеством ребер графа С. Число эле-

ментов в К(<7) и Е(С) будем обозначать как N и М, соответственно. В графе размера N число ребер М более либо равно 0, и менее либо равно -.

Граф О называется редким, если М « УУ2, и плотным, если М = 0(Ыг). Граф

N

называется полным, если М = ( ) = -1) / 2 .

2

О каждом ребре вида (и, у) говорят, что оно соединяет вершины и и v. Условимся, что граф С не может содержать ребер-петель вида {и, и), и любые две вершины могут быть соединены не более чем одним ребром, то есть в графе отсутствуют кратные ребра.

Про ребро (и, у) неориентированного графа й говорят, что оно инцидентно вершинам и и у. Если в неориентированном графе имеется ребро {и,у), то говорят, что вершины и и V смежные.

Граф С(У,Е) можно представить в виде матрицы смежности

А(С) = {а^У , элемент которой = равен 1, если между верши-

нами г и есть ребро, в противном случае он равен нулю. Для неориентированных графов матрица А(Ст) симметрична.

Путь длины к из вершины и в вершину V определяется последовательностью вершин {и = у0,у,,...,уд. = у}, в которой (ум,у^ЕЕ для всех / = 1,2

Если для вершин и и V существует путь из и в у, то говорят, что вершина V достижима из и по этому пути.

Неориентированный граф называется связным, если для любой пары вершин существует путь из одной в другую.

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

Диаметром графа называется максимальное значение , достигаемое на

данном графе, и обозначается как й .

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

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

1.1.2.1. Характеристики вершин графа

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

n

н

Средняя степень вершин сети:

Степенной последовательностью графа называется список степеней вершин.

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

Степень вершины является одним из наиболее важных показателей важности узла, и называется степенной нейтральностью узла:

Со(0 = кг

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

с.(0- 2 ^

п

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