Эвристические алгоритмы моделирования и оптимизации структуры неоднородных комплексных сетей тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат наук Каширин, Виктор Валерьевич

• Каширин, Виктор Валерьевич
• кандидат наук
• 2013

Оглавление диссертации кандидат наук Каширин, Виктор Валерьевич

СОДЕРЖАНИЕ

Введение

Глава 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. Применение поисковой оптимизации в задачах моделирования

комплексных структур

Выводы по главе 1

Глава 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. Корреляции значений характеристик сети

Выводы по главе 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. Экспериментальные исследование метода оптимизации КС на основе

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

Выводы по главе 3

Глава 4 Приложения методов для исследования социальных сетей и процессов на них

4.1. Моделирование структуры социальных сетей и процессов на них

4.1.1. Моделирование структуры социальных сетей

4.1.2. Внедрение разработанных методов для иммунизации социальной сети

4.2. Моделирование воздействий на криминальные сети

Выводы по главе 4

Заключение

Список использованных источников

ПРИЛОЖЕНИЕ А

Введение диссертации (часть автореферата) на тему «Эвристические алгоритмы моделирования и оптимизации структуры неоднородных комплексных сетей»

Введение

Комплексные сети (КС) являются перспективной математической моделью для изучения свойств сложных систем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 ^

п

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

Еще одной существенно важной метрикой центральности вершины является сингулярная центральность [25]. В отличии от степенной центральности, которая выражает важность лишь самой вершины, сингулярная центральность позволяет выразить важность узла с учетом важности его узлов-соседей:

где а1п, является (г,уу)-элементом матрицы смежности рассматриваемой сети. В матричном виде предыдущее выражение можно переписать как

где элемент г вектора х равен СЕ{Г).

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

1.1.2.2. Характеристики структуры графа

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

[24].

Ах = Хх,

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

Очевидно, коэффициент Т удовлетворяет неравенству 0 ^ Т <, 1. Если сеть изображается полным графом, то очевидно, что для нее Т = 1.

Коэффициент Г можно интерпретировать, как среднюю вероятность того, что две вершины сети, смежные с одной и той же третьей вершиной, также окажутся смежными.

Свойство кластеризации можно представить и в другом виде. Если Сп

подграф, составленный из вершин, смежных с вершиной г, имеет е1 ребер, то коэффициент С,- можно вичислить как отношение е1 к максимально возможному числу ребер в подграфе С,, которое равно 1)/2, где к1 -

степень вершины I То есть:

Коэффициент кластеризации для всей сети С вычисляют как среднее значение локальных коэффициентов кластеризации С, для всех вершин сети:

По определению: и 0 ^ С 1.

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

3 х число треугольников в СУ

Т =

число вилок в С

С1 = '•

ад-1)

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

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

Распределение степеней является одной из важнейших характеристик комплексной сети. Пусть рк доля всех вершин в сети, имеющих степень к, т.е.

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

График распределения степеней рк = Р(к) как функции от переменной к,

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

Несмотря на простой и ясный смысл распределения степеней, составление соответствующего графика рк = Р{к) для реальных сетей может быть связано со

значительными трудностями. Первый недостаток такого «теоретического» подхода состоит в том, что значения этой функции могут существенно варьироваться для соседних значений к, особенно при больших к. Это выражается в том, что в реальных сетях узлы с конкретными (обычно большими) значениями к могут просто отсутствовать, т.е. соответствующее N{k) = 0, что приводит нас к

^(к^-к^Ит)^'

рк = Р(к) = 0, в то время как для переменных к +1 и к -1 величины Р(к +1) и Р(к -1) могут существенно отличаться от нуля.

Среди множества распределений, применительно к комплексным сетям чаще всего встречаются два вида. Первое - пуассоновское распределение:

А е

Р(к) =

к\

где Я - это некоторая константа, а к - степень (см. рис. 1.2). Это распределение характерно для сетей, в которых связи образованы случайным образом и с равной вероятностью, то есть без выраженной предпочтительности одних узлов другим.

Рисунок 1.2 - Пуассоновское распределение вероятностей с различными

значениями константы Я

Вторым важным распределением при рассмотрении комплексных сетей является степенное (power-law):

Р(к) = Ск~у,

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

к~у

Р(к)ш

Z(Y)

где £(/)- дзета-функция Римана, которая служит для того, чтобы выполнялось

равенство ^рк = 1.

к

В важнейших работах Барабаши и Альберт [3,26] было показано, что во многих реальный сетях распределение степеней вершин подчиняется именно степенному закону. Такие сети, со степенным законом распределения степеней, называются безмасштабными (scale-free), поскольку топологические характеристики таких сетей не зависят от размера сети, и некоторая локальная часть сети будет демонстрировать те же характеристики, что и глобальная сеть.

к

Рисунок 1.3 - Распределение степеней по степенному закону при разных

показателях степени

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

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

Настоящий раздел посвящен обзору традиционных моделей комплексных сетей и их свойств.

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

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

1.2.1.1. Модель случайного графа

В общем случае модель случайного графа предполагает, что определенное множество параметров сети имеет фиксированное значение, в остальном же структура сети случайна [27]. Простейшим примером такой сети является сеть, в которой фиксируется число вершин N и число ребер М, и М ребер расставляются между N вершинами случайным образом. Такая сеть как правило обозначается С(И,М). Эквивалентом данной формы представления является модель С(И,Р), в которой вместо числа ребер фиксируется вероятность, с которой каждая пара сочетаний вершин из V соединена ребром. Алгоритм моделирования формулируется следующим образом:

• фиксируется вероятность р;

• фиксируется число вершин в графе N;

• независимо каждая пары вершин соединяется ребром с вероятностью р .

Подробно сеть С(Ы,Р) была изучена и описана в ряде работ Эрдеша и Ре-

ньи конца пятидесятых и начала шестидесятых годов двадцатого века [28,29], в связи с чем зачастую эта модель именуется моделью случайного графа Эрдеша и Реньи (Егс1о5-Кепу1, далее ЕЙ.).

В случайном графе с вероятностью связности р степень к1 вершины г следует биномиальному распределению с параметрами N -1 и р:

р(к1 = к) = с11рк(\-рГ-1-к

Эта вероятность представляет количество способов, которыми к ребер могут быть проведены из определенной вершины: вероятность для к ребер составляет рк, вероятность отсутствия дополнительных ребер составляет (1 - p)N~l~kk и существует CkN_x эквивалентных способов выбора к конечных точек для этих ребер. Тем более, если вершины i и j являются различными, Р(к[ = к) и P{kj = к) близки к тому, чтобы быть независимыми случайными переменными. Для нахождения распределения степеней графа необходимо изучить количество вершин со степенью к (обозначим Хк). Ожидаемое количество вершин со степенью к составит Е(Хк) = NP(kt = к) = \, где кк = NCk_xpk (1- p)N~[~k. С хорошим приближением для распределения степеней в случайном графе подходит биномиальное распределение Р(к) = Ck_lpk(\ - p)N~l~k, которое для больших п может быть заменено распре-

ЛУ"Я

делением Пуассона: Р(к) =-. Средняя длина кратчайших путей случайного

к\

графа: Г = -1п^ , коэффициент кластеризации: С = р.

In (pN)

1.2.1.2. Конфигурационная модель

Конфигурационная модель (англ. Configuration Model, далее СМ) является обобщением модели случайного графа ER, и позволяет построить случайный граф с заданным распределением степеней вершин [30,31]. Модель описывается следующим образом:

• фиксируется распределение степеней Р(к);

• выбирается N чисел ki согласно распределению (/ = N — число

вершин будущей сети);

• каждой вершине i в графе «приписывается» kt полу-ребер;

• случайно выбираются пары полу-ребер и соединяются их ребром.

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

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

В остальном конфигурационная модель наследует свойства модели случайной сети ЕЯ.

1.2.1.3. Модель малого мира

Модель малого мира была предложена и подробно рассмотрена в 1998 году в работах Ватса и Строгатса ("\^айг-81го§а1г, далее \У^)[5,32]. В данной модели реализована попытка воплотить в сетях два признака, характерных для реальных сетей: высокую кластеризацию и малую среднюю длину кратчайших путей между вершинами. Алгоритм построения модели формулируется следующим образом:

• зафиксируем число вершин в графе ./V;

• зафиксируем число с. Свяжем каждую вершину с с ближайшими соседя-

ми;

• для каждой вершины и перебросим каждое ребро, инцидентное этой вер-

шине, с вероятностью р.

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

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

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

Barabasi и Albert, данная модель (далее ВА) имеет два важных свойства: сети, конструируемые с помощью нее, обладают степенным распределением степеней вершин, а так же, в отличии от других моделей, модель отражает динамику роста

Алгоритм построения сети:

• зафиксировать число т0 начальных вершин. Число ш0 а2 и степень каждой

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

• на каждом шаге в сеть добавляется одна вершина, и соединяется с т уже существующими вершинами с вероятностью, пропорциональной степени существующих вершин. То есть вероятность pi того, что новая вершина свяжется

с вершиной i, равна

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

Распределение степеней воспроизводимых моделью сетей следует степен-

фициент кластеризации: С ~ N 075.

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

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

сети [3,33].

j

—3 hi гi

ному закону распределения: Р(к)~к , средняя длина пути -, а коэф-

lnlnn

1.3.1. Ограничения традиционных математических моделей КС

Множество исследований показало, что для многих видов комплексных сетей, встречающихся в природе, и для социальных сетей в частности, наиболее характерны три свойства: малый диаметр сети, высокая кластеризация и без-масиипабность [4].

Малый диаметр сети, так же называемый «эффектом малого мира» [34], показывает, что средняя длина пути между вершинами растет пропорционально логарифму от числа ее узлов. То есть, независимо от числа индивидов в сети расстояние между ними остается достаточно небольшим. Этот эффект был подробно изучен как «теория шести рукопожатий».

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

Список литературы диссертационного исследования кандидат наук Каширин, Виктор Валерьевич, 2013 год

Список использованных источников

1. Liu Y.-Y., Slotine J.-J., Barabasi A.-L. Controllability of complex networks. //Nature. 2011. Vol. 473, № 7346. P. 167-173.

2. Albert R., Barabasi A.L. Statistical mechanics of complex networks // Rev. Mod. Phys. American Physical Society, 2002. Vol. 74, № 1. P. 47.

3. Barabasi A.L., Albert R. Emergence of scaling in random networks // Science (80-.). American Association for the Advancement of Science, 1999. Vol. 286, № 5439. P. 509.

4. Newman M.E.J. The structure and function of complex networks // SIAM Rev. JSTOR, 2003. Vol. 45, № 2. P. 167-256.

5. Kleinberg J.M. Navigation in a small world // Nature. Nature Publishing Group, 2000. Vol. 406, № 6798. P. 845.

6. Colizza V., Pastor-Satorras R., Vespignani A. Reaction-diffusion processes and metapopulation models in heterogeneous networks // Nat. Phys. 2007. Vol. 3, № 4. P. 276-282.

7. Strogatz S.H. Exploring complex networks // Nature. 2001. Vol. 410, № 6825. P. 268-276.

8. Costa L.D.F. et al. Characterization of complex networks: A survey of measurements // Adv. Phys. Taylor & Francis, 2005. Vol. 56, № l.P. 78.

9. Newman M.E.J. Complex Systems : A Survey // Gene. 2009. № I.

10. Goldenberg A. et al. A survey of statistical network models // Soc. Networks. Now Publishers Inc, 2009. Vol. 2, № December. P. 96.

11. Holme P. et al. Attack vulnerability of complex networks. // Phys. Rev. E. Stat. Nonlin. Soft Matter Phys. 2002. Vol. 65, № 5 Pt 2. P. 056109.

12. Morselli C. Assessing Vulnerable and Strategic Positions in a Criminal Network // J. Contemp. Crim. Justice. 2010. Vol. 26, № 4. P. 382-392.

13. Boccaletti S. et al. Complex networks: Structure and dynamics // Phys. Rep. 2006. Vol. 424, № 4-5. P. 175-308.

14. Newman M. Networks: An Introduction // Book. 2010. P. 720.

15. Barthelemy M. Spatial networks // Phys. Rep. JSTOR, 2010. Vol. 51, № 4. P. 924-939.

16. Dorogovtsev S.N., Mendes J.F.F. Evolution of Networks: From Biological Nets to the Internet and WWW // booksgooglecom. 2003. Vol. 57. P. 280.

17. Czaplicka A., Holyst J. a, Sloot P.M. a. Noise enhances information transfer in hierarchical networks. // Sci. Rep. 2013. Vol. 3. P. 1223.

18. Kuperman M., Zanette D. Stochastic resonance in a model of opinion formation on small-world networks // Eur. Phys. J. B. 2002. Vol. 26, № 3. P. 387-391.

19. Sloot P.M. a. et al. Stochastic simulation of FIIV population dynamics through complex network modelling // Int. J. Comput. Math. 2008. Vol. 85, №8. P. 1175-1187.

20. Nekovee M., Moreno Y. Dynamics of gossip-like information dissemination in complex computer networks // Int. J. Comput. Math. 2008. Vol. 85. P. 1165-1173.

21. Zhao L. et al. SIR rumor spreading model in the new media age // Phys. A Stat. Mech. its Appl. Elsevier B.V., 2013. Vol. 392, № 4. P. 995-1003.

22. Kaluza P. et al. The complex network of global cargo ship movements. // J. R. Soc. Interface. 2010. № January. P. 1093-1103.

23. Lambiotte R., Delvenne J., Barahona M. Laplacian Dynamics and Multiscale Modular Structure in Networks. 2009. P. 1-29.

24. Brandes U. A faster algorithm for betweenness centrality* // J. Math. Sociol. 2001. Vol. 25. P. 163-177.

25. Ruhnau B. Eigenvector-centrality—a node-centrality? // Soc. Networks. 2000. Vol. 22. P. 357-365.

26. Barabasi A.L. Scale-free networks: a decade and beyond. // Science. 2009. Vol. 325, № 5939. P. 412-413.

27. Bollobas B. The evolution of random graphs // Trans. Am. Math. Soc. 1984. Vol. 286. P. 257-257.

28. Erdos P., Renyi A. On random graphs // Publ Math Debrecen. 1959. Vol. 6. P. 290-297.

29. Renyi A., Erdos P. On the strength of connectedness of a random graph // Acta Math. Acad. Sci. Ilungaricae. 1961. Vol. 12. P. 261-267.

30. Bender E.A., Canfield E.R. The asymptotic number of labeled graphs with given degree sequences // J. Comb. Theory, Ser. A. 1978. Vol. 24. P. 296307.

31. Molloy M., Reed B. A critical point for random graphs with a given degree sequence //Random Struct. Algorithms. 1995. Vol. 6. P. 161-180.

32. Watts D.J., Strogatz S.H. Collective dynamics of "small-world" networks. //Nature. 1998. Vol. 393. P. 440^142.

33. Albert R., Barabasi A.L. Statistical mechanics of complex networks // Rev. Mod. Phys. 2002.

34. Travers J., Milgram S. An Experimental Study of the Small World Problem // Sociometry. 1969. Vol. 32. P. 425-443.

35. Fan Z., Chen G., Zhang Y. Using topological characteristics to evaluate complex network models can be misleading // arXiv.TOl 1.0126vl. 2010.

36. Borgatti S.P., Carley K.M., Krackhardt D. On the robustness of centrality measures under conditions of imperfect data // Soc. Networks. Elsevier, 2006. Vol. 28, № 2. P. 124-136.

37. Kirkpatrick S., Gelatt C.D., Vecchi M.P. Optimization by simulated annealing. // Science. 1983. Vol. 220. P. 671-680.

38. Cunha M., Sousa J. Water Distribution Network Design Optimization: Simulated Annealing Approach // J. Water Resour. Plan. Manag. 1999. Vol. 125. P. 215-221.

39. Dougherty D.E., Marryott R.A. Optimal groundwater-management. 1. simulated annealing // Water Resour. Res. 1991. Vol. 27. P. 2493-2508.

40. Back T., Schwefel FI.-P. Evolutionary computation: an overview // Proc. IEEE Int. Conf. Evol. Comput. 1996.

41. Back T., Fogel D.B., Michalewicz Z. Handbook of Evolutionary Computation//Evol. Comput. 1997. Vol. 2. P. 1-11.

42. Srinivas M., Patnaik L.M. Genetic algorithms: a survey // Computer (Long. Beach. Calif). 1994. Vol. 27.

43. Ngatchou P., Zarei A. Pareto Multi Objective Optimization. 2005. P. 8491.

44. Tan K.C., Lee T.H., Khor E.F. Evolutionary algorithms for multi-objective optimization: performance assessments and comparisons // Proc. 2001 Congr. Evol. Comput. (IEEE Cat. No.01TH8546). Ieee, 2001. Vol. 2. P. 979-986.

45. Ghosh A. Evolutionary Algorithms for Multi-Criterion Optimization : A Survey. 2004. Vol. 2, № 1. P. 38-57.

46. Konak A., Coit D.W., Smith A.E. Multi-objective optimization using genetic algorithms: A tutorial // Reliab. Eng. Syst. Saf. 2006. Vol. 91, № 9. P. 992-1007.

47. Meunier H., Talbi E., Reininger P. A multiobjective genetic algorithm for radio network optimization // Congr. Evol. Comput. (CEC '00). 2000. Vol. 1. P. 317-324.

48. Newman T.R. Multiple Objective Fitness Functions for Cognitive Radio Adaptation. 2008.

49. Editors S. et al. Design of Modern Heuristics Principles and Application.

50. Giuma T., Walker P. PSpice circuit generation through the method of simulated annealing // IEEE Trans. Educ. 1992. Vol. 35.

51. Lam Y.Y.H. Simulated annealing based analog circuit synthesizer // 2002 IEEE Reg. 10 Conf. Comput. Commun. Control Power Eng. TENCOM '02. Proceedings. 2002. Vol. 1.

52. Durbin F. et al. Integrated circuit performance optimization with simulated annealing algorithm and SPICE-PAC circuit simulator // [Proceedings] EURO ASIC "90. 1990.

53. Gielen G.G.E., Walscharts FI.C.C., Sansen W.M.C. Analog circuit design optimization based on symbolic simulation and simulated annealing // IEEE J. Solid-State Circuits. 1990. Vol. 25.

54. Sharma S., Mathew T. V., Ukkusuri S. V. Pareto Optimal Multiobjective Optimization for Robust Transportation Network Design Problem // Transp. Res. Rec. J. Transp. Res. Board. 2009. Vol. 2090. P. 95-104.

55. Friesz T.L. et al. The multiobjective equilibrium network design problem revisited : A simulated annealing approach. 1993. Vol. 65. P. 44-57.

56. Banerjee N., Kumar R. Multiobjective network design for realistic traffic models // Proc. 9th Annu. Conf. Genet. Evol. Comput. - GECCO '07.

2007. P. 1904.

57. Murray S., Ventura D. Algorithmically Flexible Style Composition Through Multi-Objective Fitness Functions. 2012. P. 55-62.

58. Newman M.E.J. Power laws, Pareto distributions and Zipf s law. № 1.

59. Clauset A., Shalizi C.R., Newman M.E.J. Power-law distributions in emperical data // arXiv:phys. 2007. P. 1-26.

60. Milo R. et al. Network motifs: simple building blocks of complex networks. // Science. 2002. Vol. 298, № 5594. P. 824-827.

61. Kima H. et al. On realizing all simple graphs with a given degree sequence. 2008. № April 2008.

62. Clauset A., Newman M.E.J., Moore C. Finding community structure in very large networks // Phys. Rev. E. 2004.

63. Ahn Y., Bagrow J.P., Lehmann S. Link communities reveal multi-scale complexity in networks //Nature. 2010.

64. Gulbahce N., Lehmann S. The art of community detection // Bioessays.

2008. Vol. 30, № 10. P. 934-938.

65. Mucha P.J. et al. Community Structure in Time-Dependent, Multiscale, and Multiplex Networks // Science (80-. ). 2010.

66. Clauset A., Moore C., Newman M.E.J. Hierarchical structure and the prediction of missing links in networks. // Nature. 2008. Vol. 453, № 7191. P. 98-101.

67. Moreno Y., Nekovee M., Pacheco A.F. Dynamics of rumor spreading in complex networks. // Phys. Rev. E. Stat. Nonlin. Soft Matter Phys. 2004. Vol. 69. P. 066130.

68. Mendes J.F.F. et al. Statistical mechanics of rumour spreading in network communities // Procedia Comput. Sci. 2010. Vol. 1. P. 2331-2339.

69. Daley D.J., Kendall D.G. Epidemics and rumours. // Nature. 1964. Vol. 204. P. 1118.

70. Daley D., Kendall D. Stochastic rumours // IMA J. Appl. Math. 1965. Vol. l.P. 42-55.

71. Resnick M.D. et al. Protecting adolescents from harm: findings from the National Longitudinal Study on Adolescent Health // J. Am. Med. Assoc. 1997. Vol. 278. P. 823-832.

72. Miura LI., Yamamoto M. On the Location of Routers with Network Support in Content Distribution Networks // 6th Asia-Pacific Symp. Inf. Telecommun. Technol. 2005.

73. Hou B., Yao Y., Liao D. Identifying all-around nodes for spreading dynamics in complex networks // Phys. A Stat. Mech. its Appl. Elsevier B.V., 2012. Vol. 391, № 15. P. 4012^017.

74. Tao Z., Zhongqian F., Binghong W. Epidemic dynamics on complex networks // Prog. Nat. Sci. 2006. № 70471033.

75. Barabasi A.L. The origin of bursts and heavy tails in human dynamics // Nature. Nature Publishing Group, 2005. Vol. 435, № 7039. P. 207-211.

76. Pastor-Satorras R., Vazquez A., Vespignani A. Dynamical and correlation properties of the Internet // Time. 2008. P. 1-4.

77. Newman M.E.J., Forrest S., Balthrop J. Email networks and the spread of computer viruses. // Phys. Rev. E. Stat. Nonlin. Soft Matter Phys. 2002. Vol. 66. P. 035101.

78. Potterat J.J. et al. Risk network structure in the early epidemic phase of HIV transmission in Colorado Springs. // Sex. Transm. Infect. 2002. Vol. 78 Suppl 1. P. il59-il63.

79. Dunne C., Shneiderman B. Motif Simplification : Improving Network Visualization Readability with Fan , Connector, and Clique Glyphs. 2013.

80. Rocha L.E.C., Blondel V.D. Flow Motifs Reveal Limitations of the Static Framework to Represent Human interactions. 2013.

81. Villas Boas P.R. et al. Chain motifs: The tails and handles of complex networks // Phys. Rev. E. 2008. Vol. 77, № 2. P. 026106.

82. Dijk D. Van et al. Identifying potential survival strategies of HIV-1 through virus-host protein interaction networks. 2010.

83. V. Knyazkov K. et al. CLAVIRE: e-Science infrastructure for data-driven computing // J. Comput. Sci. Elsevier B.V., 2012. Vol. 3, № 6. P. 504510.

84. Xu J. et al. Analyzing and Visualizing Criminal Network Dynamics: A Case Study // Manag. Inf. Syst. P. 1-29.

85. Tremblay P., Morselli C. Patterns in Criminal Achievement: Wilson and Abrahamse Revisited // Criminology. Wiley Online Library, 2000. Vol. 38, №2. P. 633-657.

86. Marshall B. Using Importance Flooding to Identify Interesting Networks of Criminal Activity // Office. 2008. Vol. 59, № 13. P. 2099-2114.

87. Kerschbaum F., Schaad A. Privacy-Preserving Social Network Analysis for Criminal Investigations // Network. 2008.

88. Schwartz D.M., Rouselle T.D.A. Using social network analysis to target criminal networks // Organ, The. 2009. P. 188-207.

89. Lampe K. Von. Human capital and social capital in criminal networks : introduction to the special issue on the 7th Blankensee Colloquium // Critique. 2009. P. 93-100.

90. Fard A., Ester M. Collaborative mining in multiple social networks data for criminal group discovery H ... Sei. Eng. 2009. CSE'09.....2009.

91. Xu J., Chen H. Fighting organized crimes: using shortest-path algorithms to identify associations in criminal networks // Decis. Support Syst. 2004. Vol. 38, №3. P. 473-487.

92. Xu J .J., Chen IT. Using Shortest Path Algorithms to Identify Criminal Associations // Phoenix Usa. 2002. № 520.

93. Xu J.J., Chen H. CrimeNet Explorer: A Framework for Criminal Network Knowledge Discovery // ACM Trans. Inf. Syst. 2005. Vol. 23, № 2. P. 201-226.

94. Berk R. How you can tell if the simulations in computational criminology are any good // J. Exp. Criminol. 2008. Vol. 4, № 3. P. 289-308.

95. Flu D., Kaza S., Chen H. Identifying Significant Facilitators of Dark Network Evolution // J. Am. Soc. Inf. Sei. Technol. Wiley Online Library, 2009. Vol. 60, № 4. P. 655-665.

96. Yoshiharu M., Ohsawa Y. Analyzing covert social network foundation behind terrorism disaster Yoshiharu Maeno Yukio Ohsawa // Int. J. Serv. Sei. 2009. Vol. 2. P. pp.125-141.

{ I

97. Carley K.M., Reminga J., Kamneva N. Destabilizing Terrorist Networks. 1998.

98. Memon N. Detecting Terrorist Activity Patterns using Investigative Data Mining Tool // Data Process. JAIST Press, 2005.

99. David A. Bright, Catherine Greenhill N.L. Dismantling criminal networks: can node attributes play a role. 2011. Vol. 2011, № version 6.

100. Gottschalk P. Value configurations in organised crime // Polic. Soc. Routledge, 2009. Vol. 19, № 1. P. 47-57.

101. Calvo-Armengol A., Zenou Y. Social Networks And Crime Decisions: The Role Of Social Structure In Facilitating Delinquent Behavior // Int. Econ. Rev. (Philadelphia). Wiley Online Library, 2004. Vol. 45, № 3. P. 939-958.

102. Reichardt J., White D.R. Role models for complex networks // Eur. Phys. J. B. 2007. Vol. 60, № 2. P. 217-224.

103. Morselli C. Paths for Criminal Network Disruption // Security. 2009. № November. P. 0-15.

104. Morselli C., Giguere C. Legitimate strengths in criminal networks // Soc. Change. 2006. P. 185-200.

105. Laurent H. et al. Global efficiency of local immunization on complex networks // arXiv:1208.5768vl. 2012. P. 1-7.

106. Morselli C., Gigu C., Petit K. The efficiency / security trade-off in criminal networks // Soc. Networks. 2006. P. 1-11.

107. Tsvetovat M., Carley K. Bouncing back: Recovery mechanisms of covert networks // NAACSOS Conf. 2003.

108. Kleemans E.R., Van De Bunt H.G. the social embeddedness of organized crime // Transnatl. Organ. Crime. Urlv http://www. frankcass. com, 1999. Vol. 5, № l.P. 19-36.

109. Chau M., Xu J.J., Chen H. Extracting Meaningful Entities from Police Narrative Reports // Manag. Inf. Syst.

110. Morselli C. Entrepreneurial opportunities and brokerage positioning in the cannabis trade // Crime, Law Soc. Chang. Springer, 2001. Vol. 35, № December. P. 203-244.

111. LindelaufB.R., Borm P., Hamers H. One-mode projection analysis and design of covert affiliation networks // Analysis. 2010.

112. Newman M.E.J. Assortative mixing in networks // Structure. Vol. 2, № 4. P. 1-5.

113. Morselli C., Roy J. Brokerage Qualifications in Ringing Operations. 2006. № November.

114. Morselli C. Brokerage Qualifications in Ringing Scripts. New York, NY: Springer New York, 2009. Vol. 8. P. 103-121.

Публикации автора Статьи в журналах из перечня ВАК

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

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

117. Kashirin V.V., Dijkstra L.J. A Heuristic Optimization Method for Mitigating the Impact of a Virus Attack // Procedia Computer Science. 2013. Vol. 18. P. 2619-2628.

Другие статьи автора

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

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

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