Методы структурной идентификации стохастических сетей и генерации случайных графов в задачах моделирования сложных систем тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат технических наук Юдин, Евгений Борисович

• Юдин, Евгений Борисович
• кандидат технических наук
• 2012

Оглавление диссертации кандидат технических наук Юдин, Евгений Борисович

СПИСОК СОКРАЩЕНИЙ

ВВЕДЕНИЕ

ГЛАВА 1. МОДЕЛИРОВАНИЕ СЕТЕВЫХ СТРУКТУР И ПРОЦЕССОВ

1.1. Основные понятия

1.2. Решетки

1.2.1. Моделирование случайных отказов в решетках

1.2.2. Моделирование распространения вируса в решетках

1.3. Случайные графы

1.3.1. Графы Эрдеша-Реньи

1.3.2. Графы Уотса-Строгатса

1.3.3. Безмасштабные графы

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

1.3.5. Другие классы случайных графов

1.3.6. Моделирование случайных отказов в больших сетях

1.3.7. Моделирование распространения вируса в сетях 41 Выводы по первой главе

ГЛАВА 2. СТРУКТУРНАЯ ИДЕНТИФИКАЦИЯ

СЕТЕЙ ТИПА ИНТЕРНЕТ

2.1. Ускоренный метод генерации графа БА и графа с НППС

2.1.1. Базовый метод генерации графа БА

2.1.2. Ускоренный метод генерации графа БА

2.1.3. Статистические проверки структурных характеристик графов

2.2. Калибровка графов с НППС

2.2.1. Калибровка графа по эмпирическому РСС узлов

2.2.2. Генерация и калибровка ориентированного сл.г. с НППС

2.2.3. Аппроксимация функции предпочтения

2.2.4. Сепарабельная реконфигурация по коэффициенту кластеризации 61 Выводы по второй главе

ГЛАВА 3. НОВЫЕ КЛАССЫ СЛУЧАЙНЫХ ГРАФОВ

3.1. Графы декомпозиции

3.1.1. Графы декомпозиции для моделирования граф-схем алгоритмов

3.1.2. Оценка эффективности редукции граф-схем надежности

3.2. Графы соседства

3.2.1. Генерация графов соседства

3.2.2. Устойчивость графов соседства к случайному удалению вершин/ребер

3.2.3. Моделирование распространения вируса на графе соседства

3.2.4. Модель «хищник-жертва» на графах соседства 90 Выводы по третьей главе

ГЛАВА 4. ПРОГРАММНЫЕ СРЕДСТВА МОДЕЛИРОВАНИЯ СЕТЕВЫХ СТРУКТУР И ПРОЦЕССОВ

4.1. Система агентного моделирования SI MB I GRAPH

4.1.1. Архитектура системы

4.1.2. Двухэтапный подход в моделировании сетевых процессов

4.1.3. Генерация случайных графов

4.1.4. Имитационное моделирование сетевых процессов

4.1.5. Демонстрационный пример: моделирование сети Интернет

4.2. Реализация генератора графа соседства в многопроцессорной среде

4.2.1. Распределенное выполнение имитационных экспериментов

4.2.2. Генерация графа соседства в распределенной среде 117 Выводы по четвертой главе 121 ЗАКЛЮЧЕНИЕ 122 СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 125 Приложение А Исследование связности при случайном удалении вершин/ребер в графах соседства 136 Приложение Б SIRS модель в системе SIMBIGRAPH 141 Приложение В Акты внедрения и свидетельства о регистрации

СПИСОК СОКРАЩЕНИЙ

АС - автономная система

БСВ - базовая случайная величина

БСС - большая стохастическая сеть

ВС - вычислительная система граф БА - граф Барабаши-Альберт граф с HI 111С - граф с нелинейным правилом предпочтительного связывания

ГСА - граф-схемы алгоритмов

ГСН - граф-схемы надежности

ГЦК - гранецентрированная кубическая

ДСВ - дискретная случайная величина

ИМ - имитационное моделирование

КМ - конфигурационная модель

PC - распределенные в пространстве статистически однородные структуры

РСС - распределение степени связности

СИМ - система имитационного моделирования сл.в. - случайная величина сл.г. - случайный граф ф.р.в. - функция распределения вероятностей

BGP - Border Gateway Protocol протокол граничного шлюза)

MPI - Message Passing Interface

MPMD - Multiple Program Multiple Data множество программ - множество потоков данных)

SIRS - Susceptible - Infected - Recovered - Susceptible восприимчивый - инфицированный - невосприимчивый - восприимчивый)

SIS - Susceptible-Infected-Susceptible (восприимчивыйинфицированный - восприимчивый)

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

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

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

Случайные графы нашли применение в работах Д. Уотса и С. Строгатса [117], А. Барабаши и Р. Альберт [73], М. Ньюмена [107], Ю. Лесковца [102] и др. Так, А. Барабаши в своей работе «Безмасштабные сети: итоги десятилетия» [75] отмечает исключительную роль случайных графов в исследовании сложных систем. Среди публикаций на русском языке можно выделить работы А. И. Олемской [34], Ю. Л. Павлова [39], Д. А. Губанова, Д. А. Новикова, А. Г Чхартишвили [9], А. В. Ко-ганова, А. Н. Сазонова [26] и В. Н. Задорожного [20].

Мощным импульсом к развитию теории случайных графов послужила работа А. Барабаши и Р. Альберт [73], в которой был предложен безмасштабный случайный граф, позднее названный графом Барабаши-Альберт (графом БА). Структурные свойства графа БА позволили успешно на его основе моделировать такие сети, как Интернет, сеть ссылок веб-страниц, сеть участия белков в обменных процессах организма, социальные сети [73, 67, 70, 68, 84]. Пастор-Саторрас и Веспиньяни обнаружили [111], что графу Б А свойствен нулевой порог сопротивляемости распространению вируса, что объясняет необычайную «живучесть» вирусов в биологических и компьютерных сетях. Другое интересное свойство графов БА заключается в том, что они чрезвычайно устойчивы к случайным удалениям вершин/ребер, но чувствительны к целенаправленным «атакам» на концентраторы (вершины с большой локальной степенью связности), что объясняет, в частности, повышенную устойчивость сети Интернет к случайным отказам [68]. В то же время, удалив лишь несколько ключевых концентраторов, можно «расколоть» сеть Интернет на мелкие изолированные компоненты связности. Для графов БА (и, следовательно, для моделируемых ими сетей) предложены и теоретически обоснованы стратегии борьбы с распространением вирусов и способы повышения устойчивости к случайным отказам. Также доказана неэффективность «случайной вакцинации» [67, 88].

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

- в области имитационного моделирования [46, 53, 81, 90];

- в теории перколяции, теории критических явлений [10, 29, 77, 113] и теории случайных графов [68, 91, 102, 117];

- в области агентного моделирования [110].

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

Объектом исследования являются БСС, включающие сети типа Интернет, большие граф-схемы алгоритмов (ГСА) и граф-схемы надежности (ГСН), распределенные в пространстве статистически однородные структуры (РС), и сетевые процессы.

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

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

Задачи работы заключаются в разработке методов структурной идентификации БСС, включающих методы генерации и калибровки:

1) графов предпочтительного связывания для сетей типа Интернет;

2) графов декомпозиции для моделирования ГСА и ГСН;

3) графов соседства для моделирования РС.

Основные положения и результаты, выносимые на защиту

1. В части моделирования сетей типа Интернет разработаны:

- ускоренный метод генерации графов БА и случайных графов с нелинейным правилом предпочтительного связывания (НППС), включающих графы БА в качестве частного случая;

- методы калибровки ориентированных и неориентированных графов с НППС по эмпирическим РСС узлов моделируемых сетей;

- метод калибровки графов с НППС по коэффициенту кластеризации (метод сепарабельной реконфигурации графа).

2. В части моделирования ГСА и ГСН предложены и исследованы:

- новый класс сл.г. - графы декомпозиции;

- метод структурно-параметрической идентификации ГСА и ГСН;

-метод ^-ориентированного измерения эффективности алгоритмов, предназначенных для работы с ГСА и ГСН.

3. В части моделирования РС:

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

- сформулирована, исследована и подтверждена гипотеза о возможности распространения на сл.г. соседства законов теории перколяции, установленных для решеток в части формирования контактных кластеров («задача узлов» и «задача ребер»);

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

Научная новизна работы

1. Ускоренный метод генерации графов с НППС отличается от известных методов разбиением множества вершин графа на слои (подмножества вершин с одинаковыми степенями). Методы калибровки графов по РСС, основанные на известной методике калибровки графов с НППС [20], отличаются математической формализацией всех шагов процесса калибровки и возможностью калибровки ориентированных графов. Метод сепарабельной реконфигурации для калибровки сл.г. по коэффициенту кластеризации отличается от метода сепарабельной калибровки графов БА [24] применимостью к любым сл.г.

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

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

Практическая значимость

1. Ускоренный генератор графов с НППС позволяет генерировать графы сетей, содержащие сотни тысяч узлов и связей, и выполнять их многовариантный анализ, обеспечивающий возможность решения прикладных задач прогнозирования сложных сетевых процессов, а также синтеза и оптимизации принимаемых решений. Методы калибровки случайных графов с НППС по эмпирическим РСС решают задачу структурной идентификации сетей с ненаправленными и направленными связями на более высоком уровне точности, чем графы БА. Метод сепа-рабельной реконфигурации графов решает задачу структурной идентификации БСС в части калибровки их графовых моделей по коэффициенту кластеризации.

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

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

Разработанные в диссертации методы реализованы программно в системе агентного моделирования 81МВЮЫАРН. Разработанная система агентного моделирования позволяет исследовать сетевые процессы и структуры с использованием предложенных в диссертации методов и алгоритмов, что подтверждается актами реализации в СПИИРАН (г. Санкт-Петербург) и в образовательной деятельности ОмГТУ (г. Омск), а также свидетельствами о регистрации программы. Опубликован ряд научных работ, в том числе и без участия авторов программы (Юдина Е. Б. и Задорожного В. Н. [66]), где 81МВЮРАРН используется как базовый инструмент анализа процессов в больших сетях. В частности, 81МВЮКАРН применяется для анализа сетевого вирусного маркетинга в социальной сети «Вконтакте» [60], исследования таких известных моделей, как «сахарный мир» и модель «хищник-жертва» [4]. В 81МВЮЯАРН разработаны модели для исследования сегрегации атомов на поверхности наночастиц сплавов металлов [16]. Примеры перечисленных моделей могут быть получены вместе с программой с сайта проекта. Программа 81МВЮ11АРН зарегистрирована региональным отделением фонда электронных ресурсов «Наука и образование» (ОФЭРНиО), а также федеральным государственным учреждением «Федеральный институт промышленной собственности» (ФИПС). По результатам диссертационной работы получены акты внедрения программы в ОмГТУ, СПИИРАН (Санкт-Петербургский институт информатики и автоматизации).

Апробация работы, публикации

Результаты диссертации апробированы на региональной конференции «Информационные технологии и автоматизация управления» (Омск, 2009, 2010, 2011), всероссийской научно-практической конференции «Имитационное моделирование. Теория и практика» (Санкт-Петербург, 2007, 2009, 2011), всероссийской научно-технической конференции «Россия молодая: передовые технологии -в промышленность!» (Омск, 2008, 2010, 2011), международной конференции «Динамика систем, механизмов и машин» (Омск, 2009).

По теме диссертации опубликовано 13 статей, в том числе 4 статьи во включенном в перечень ВАК журнале «Омский научный вестник».

Личное участие автора

Задачи диссертационного исследования поставлены совместно с научным руководителем В. Н. Задорожным. В совместных публикациях в разделах, посвященных графу БА, научному руководителю принадлежат постановки задач и аналитические результаты; численные эксперименты и моделирование сетевых процессов выполнены автором диссертации. Ускоренный генератор графов БА и графов с НППС, методы калибровки этих графов по эмпирическим РСС и по коэффициенту кластеризации, графы декомпозиции, метод Р - ориентированного измерения эффективности алгоритмов, графы соседства и результаты их исследования принадлежат автору диссертации.

Структура и объем работы

Основная часть диссертации объемом 135 страниц машинописного текста содержит 92 рисунка, 14 таблиц и состоит из введения, четырех глав, заключения и списка использованных источников из 120 наименований. Объем приложений -12 страниц.

Заключение диссертации по теме «Системный анализ, управление и обработка информации (по отраслям)», Юдин, Евгений Борисович

Выводы по четвертой главе

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

2. Разработанная в составе комплекса программ система моделирования больших сетей 81МВЮ11АРН имеет расширяемую подсистему графоаналитической поддержки, позволяет разделить процессы вычислений и процессы визуализации и предоставляет широкие возможности для работы со случайными графами. В системе реализован разнообразный набор средств моделирования решеток, позволяющий описывать взаимодействия агентов в гексагональной, квадратной, треугольной, кубической решетках, а также в гранецентрированной кубической упаковке. Имеется широкий набор генераторов случайных графов, в том числе генераторы сл.г. с НППС, графов БА, графов Эрдеша-Реньи, Эпштейна, конфигурационных версий безмасштабных графов. Система 81МВЮКАРН прошла государственную регистрацию, имеются акты ее внедрения (Приложение В).

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

122

ЗАКЛЮЧЕНИЕ

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

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

- выявление и формализованное описание механизма генезиса сети, определяющего ее основные, качественные характеристики;

- анализ распределения вероятностей для степени связности узлов сети;

- определение коэффициентов кластеризации различного вида;

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

- разработку методов генерации больших сл.г. со структурными характеристиками, соответствующими характеристикам исследуемых БСС.

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

1. В области структурной идентификации БСС, неограниченно растущих за счет добавления новых узлов и связей (БСС типа Интернет), в диссертации на базе теории сл.г. с НППС разработаны:

- ускоренный метод генерации сл.г. с НППС (включая графы БА);

-методы калибровки ориентированных и неориентированных графов с

НППС по эмпирическим РСС узлов моделируемых сетей;

-метод калибровки графов с НППС по коэффициенту кластеризации (метод сепарабельной реконфигурации графа).

Ускоренный метод генерации графов с НППС отличается от известных методов разбиением множества вершин графа на «слои» и позволяет многократно генерировать графы, содержащие сотни тысяч узлов и связей. Этим обеспечивается возможность выполнения многовариантного анализа для решения прикладных задач моделирования и прогноза сетевых процессов, для синтеза и оптимизации принимаемых решений. Методы калибровки графов по РСС, отличаются от известной методики калибровки графов с НППС {Задорожный В.Н., 2010) математической формализацией всех шагов процесса калибровки и возможностью калибровки ориентированных графов. Эти методы решают задачу структурной идентификации сетей на более высоком уровне точности, чем методы подбора подходящих графов БА. Метод сепарабельной реконфигурации сл.г. решает задачу структурной идентификации БСС в части калибровки их графовых моделей по коэффициенту кластеризации и отличается от метода сепарабельной калибровки графов БА {Задорожный В.Н., Юдин Е.Б., 2009) применимостью к любым сл.г.

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

- новый класс сл.г. - графы декомпозиции;

- метод ^-ориентированного измерения эффективности алгоритмов, предназначенных для работы с ГСА и ГСН (включающий метод структурно-параметрической идентификации ГСА и ГСН).

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

3. В области идентификации БСС, описывающих упаковки частиц со случайными размерами (т.е. распределенные в пространстве статистически однородные структуры), в диссертации на базе теории перколяции:

- предложены и исследованы сл.г. соседства в качестве математической модели, расширяющей класс моделей теории перколяции (периодических решеток);

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

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

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

4. Результаты выполненных исследований реализованы в разработанном комплексе программ, включающем систему агентного моделирования БШВЮКАРН и средства генерации графов соседства в многопроцессорной среде.

В системе 81МВЮ11АРН решается сформулированная в отчете AgentLink III (2006) европейского сообщества по развитию агентных вычислений проблема развития сетевых структур взаимодействия агентов. Система 81МВЮБ1АРН предоставляет широкие возможности генерации сл.г. и формирования решеток, а также встроенные средства построения агентных моделей. Алгоритмы генерации графов соседства в многопроцессорной среде ускоряются за счет эффективного распараллеливания вычислений.

Список литературы диссертационного исследования кандидат технических наук Юдин, Евгений Борисович, 2012 год

1. Байцер Б. Микроанализ производительности вычислительных систем. М.: Радио и связь, 1983. - 360 с.

2. Борщев А. В. Практическое агентное моделирование и его место в арсенале аналитика // Exponenta Pro. 2004. - № 3-4. - С. 38-47.

3. Вентцель Е. С., Овчаров Л. А.Теория случайных процессов и ее инженерные приложения. М.: Наука, 1991. - 384 с.

4. Танеева М. И., Огнев Д. А., Пендер Е. А. Построение агентных моделей в системе моделирования SIMBIGRAPH // Информационные технологии и автоматизация управления: матер, региональной науч.-практ. конф. ОмГТУ. Омск: Изд-во ОмГТУ. - 2011.-С. 103-105.

5. Гарбарев А. Ю. Разработка системы моделирования в Web // Информационные технологии и автоматизация управления: матер, региональной науч.-практ. конф. ОмГТУ. Омск: Изд-во ОмГТУ. - 2011. - С. 106-108.

6. ГОСТ 27.301-95. Надежность в технике. Расчет надежности. Основные положения. 1997. - 15 с.

7. ГОСТ Р 51901.14 2005. Метод структурной схемы надежности. - 2005. - 35 с.

8. ГОСТ 53111 2008. Устойчивость функционирования сети связи общего пользования. - 2008. - 15 с.

9. Губанов Д. А., Новиков Д. А., Чхартишвили А. Г. Социальные сети: модели информационного влияния, управления и противоборства / М.: МЦНМО, ФИЗМАТЛИТ. 2010. - 228 с.

10. Де Жен П. Идеи скейлинга в области полимеров. М.: Мир, 1982. - 368 с.

11. Ершов Е. С., Юдин Е. Б. Система имитационного моделирования SIMULAB // Имитационное моделирование. Теория и практика / матер. 4-й Всерос. науч.-практ. конф. СПб: ФГУП ЦНИИТС. - 2009. - Том 1. - С. 257-261.

12. Задорожный В. Н., Юдин Е. Б., Ершов Е. С. Р-ориентированное измерение эффективности алгоритмов редукции // Информационные технологии и автоматизация управления: матер, межвуз. науч.-практ. конф. / ОмГТУ. Омск: Изд-во ОмГТУ. 2009. - С. 177-179.

13. Задорожный В. Н., Юдин Е. Б. Генерация статистически однородных планар-ных графов // Обработка информации и управление. Теория и практика / Сб. докл. науч.-практ. конф. / Омск: Изд-во ОмГТУ. 2008. - С. 27-31.

14. Задорожный В. Н. Имитационное и статистическое моделирование: Учебное пособие / Омск: Изд-во ОмГТУ. 2007. - 120 с.

15. Задорожный В. Н., Юдин Е. Б. Использование мультиагентного моделирования в исследовании сложных сетевых структур // Россия молодая: передовые технологии в про-мьшшенностъ: матер. Всерос. НТК / Омск: Изд-во ОмГТУ. - 2008. - Кн. 2. - С. 27-31.

16. Задорожный В. Н., Юдин Е. Б. Мультиагентное моделирование микромира // Информационные технологии и автоматизация управления: матер, межвуз. науч.-практ. конф. / Омск: Изд-во ОмГТУ. 2009.- С. 186-188.

17. Задорожный В. Н., Юдин Е. Б. Мультиагентный подход в имитационном моделировании клеточных автоматов и сетевых структур // Имитационное моделирование. Теория и практика: матер. 3-й Всерос. конф. СПб: ФГУП ЦНИИТС. -2007. -Т2.- С. 72-77.

18. Задорожный В. Н., Юдин Е. Б. О надежности больших статистически однородных сетей // Информационные технологии и автоматизация управления: матер. межвуз. науч.-практ. конф. / Омск: Изд-во ОмГТУ. 2009. - С. 184-186.

19. Задорожный В. Н., Мызникова Т. А. Рекурсивный анализ чувствительности для метода Байцера. Деп. в ВИНИТИ, 1988, N5490-688. - 28 с.

20. Задорожный В. Н. Случайные графы с нелинейным правилом предпочтительного связывания // Проблемы управления. 2011. - №6. - С. 2-11.

21. Задорожный В. Н., Юдин Е. Б. Статистически однородные случайные графы: определение, генерация, применение // Омский научный вестник. 2009. -№3(83). -С. 7-13.

22. Задорожный В. Н., Юдин Е. Б. Тестирование эффективности алгоритмов на графах // Информационные технологии и автоматизация управления: матер, меж-вуз. науч.-практ. конф. / Омск: Изд-во ОмГТУ. 2009. - С. 180-183.

23. Задорожный В. Н., Юдин Е. Б. Точная теория графа Барабаши-Альберт // Омский научный вестник. 2009. - № 3 (83). - С. 13-19.

24. Карпов Ю. Г. Имитационное моделирование систем. Введение в моделирование с AnyLogic 5. СПб.: БХВ-Петербург. - 2005. - 400 с.

25. Коганов А. В., Сазонов А. Н. Анализ критических точек отказоустойчивости вычислительной среды планетарного типа // Сб. науч. трудов Междунар. науч. конф. «Математика. Компьютер. Образование». 2007. - Т.2. - С. 179-186.

26. Лесковец Ю. Структуры данных, моделирующих большие сети. URL: http://snap.stanford.edu/data/index.html.

27. Ma Ш. Теория критических явлений / М.: Мир, 1980. 296 с.

28. Мандельброт Б. Фрактальная геометрия природы / Бенуа Мандельброт; М.: Институт компьютерных исследований. 2002. - 656 с.

29. Надежность технических систем: Справочник / Ю. К. Беляев, В. В. Болотин и др.; под ред. И. А. Ушакова. М.: Радио и связь. - 1985. - 608 с.

30. Ньюмен М. Структуры данных, моделирующих большие сети. URL: http://www-personal.umicli.edu/~mein/netdata/.

31. Олемской А. И. Статистика сложных сетей (обзор) / А. И. Олемской, И. А. Олемской // "Вюник СумДУ". 2006. - № 6 (90). - С. 21-47.

32. Олзоева С. И. Распределенное моделирование в задачах разработки АСУ // Улан-Удэ. Изд-во ВСГТУ. - 2005 - 219 с.

33. Ольшанский А. Ю. Плоские графы // Соросовский Образовательный Журнал. 1996. - № 11.-С. 117-122.

34. Острейковский В. А. Теория надежности: учеб. для вузов. М.: Высш. шк., 2003.-463 с.

35. Официальный сайт ООО «Экс Джей Текнолоджис» URL: http://xjtek.ru.

36. Павлов Ю. Л., Чеплюкова И. А. Случайные графы Интернет-типа и обобщенная схема размещения // Дискретная математика. 2008. - Т. 20, вып. 3. - С. 3-18.

37. Перечень проектов, использующих JUNG. URL: http://sourceforge.net/apps/trac/iung/wiki/ProiectsUsingJUNG.

38. Прангишвили И. В., Потоцкий В. А., Гинсберг К. С., Смолянинов В. В. Идентификация систем и задачи управления: на пути к современным системным технологиям // Проблемы управления. 2004. - № 4. - С. 2-16.

39. Пригожин И. Р. Сетевое общество // Социологические исследования / пер. Романовского Н. В. 2008. - №1. - С. 24-27.

40. Родионов А. С. Разработка систем дискретного имитационного моделирования информационных сетей : диссертация. доктора технических наук : 05.13.18 Место защиты: Новосибирский государственный университет. Новосибирск. 2002. - 249 с.

41. Рыжиков Ю. И. Имитационное моделирование. Теория и технологии. СПб.: КОРОНА принт. - 2004. - 384 с.

42. Рябинин И. А. Надежность и безопасность структурно-сложных систем. -СПб.: Политехника. 2000. - 248 с.

43. Седжвик Р. Фундаментальные алгоритмы на С++. Алгоритмы на графах / СПб.: ООО «ДиаСофтЮП». 2002. - 496 с.

44. Семенов Ю. А. Алгоритмы телекоммуникационных сетей. Часть 2. Протоколы и алгоритмы маршрутизации в INTERNET/ БИНОМ. Лаборатория знаний, Интернет-университет информационных технологий. 2007. - 460 с.

45. Сеть автономных систем Интернет, воссозданная на основе BGP таблиц URL: http://www-personal.umich.edu/~mejn/netdata/as-22july06.zip (дата обращения: 01.09.2009).

46. Сеть маршрутизаторов Интернет, 2006 г., URL:http://www.cise.ufl.edu/research/sparse/mat/Paiek/internet.mat (дата обращения:0109.2009).

47. Структура сети пользователей программой для безопасного обмена информацией PGPURL: http://deim.urv.cat/~aarenas/data/xarxes/PGP.zip (дата обращения:0202.2010).

48. Скобелев П. О. Открытые мультиагентные системы для оперативной обработки информации в процессах принятия решений // Автометрия. 2002. - №6. - С. 45-61.

49. Тарасевич Ю. Ю. Перколяция: теория, приложения, алгоритмы. М.: УРСС, 2002.- 112 с.

50. Тоффли Т., Маргулис Н. Машины клеточных автоматов. М. Мир. - 1991.

51. Ушаков И. А. Курс теории надежности систем М.: Дрофа. - 2008. - 239 с.

52. Эфрос А. Л. Физика и геометрия беспорядка М.: УРСС. - 1994. - 183 с.

53. Юдин Е. Б., Задорожный В. Н Агентная модель «хищник-жертва» на статистически однородных структурах // Информационные технологии и автоматизация управления: матер, межвуз. науч.-практ. конф. Омск: Изд-во ОмГТУ. - 2009. -С. 205-207.

54. Юдин Е. Б. Алгоритмы генерирования сетевых структур в среде агентного моделирования Кераз18 // Динамика систем, механизмов и машин: матер. VII Междунар. науч.-техн. конф. Омск: Изд-во ОмГТУ. - 2009. - С.341-346.

55. Юдин Е. Б., Задорожный В. Н., Коробов В. В. Генерация больших графов с заданными свойствами // Информационные технологии и автоматизация управления: матер. II межвуз. науч.-практ. конф. 2010. - С. 25-33.

56. Юдин Е.Б. Генерация случайных графов предпочтительного связывания // Омский научный вестник. 2010. - №2 (90). - С. 7-13.

57. Юдин Е. Б. Исследование распространения инфекции на графах соседства // Информационные технологии и автоматизация управления. Матер, межвуз. науч.-практ. конф. 2010. - С. 107 - 109.

58. Юдин Е. Б. Моделирование устойчивости интернет в условиях распространения вирусов и случайных отказов элементов сети // Омский научный вестник. -2010.-№1 (87).-С. 190-194.

59. Юдин Е. Б. Система агентного моделирования SIMBIGRAPH // Россия молодая: передовые технологии в промышленность: матер. III Всерос. науч.-техн. конф. - Омск: Изд-воОмГТУ.-2010.-Кн. 1. - С. 312-316.

60. Юдин Е. Б., Задорожный В. Н. Система агентного моделирования SIMBIGRAPH // Свидетельство о государственной регистрации программы для ЭВМ №2011612193 / Федеральная служба по интеллектуальной собственности, патентам и товарным знакам. 28.01.2011.

61. Albert R., Н. Jeong A. L., Barabasi A. Error and attack tolerance of complex networks // Nature. 2000. V. 406. P. 378-482.

62. Albert R., Barabasi A. Statistical mechanics of complex networks // Rev. Mod. Phys. 2002. V. 74. P. 42-97.

63. Alexandrowicz Z. Critically branched chains and percolation clusters // Phys. Letter A. 1980. V. 80. P. 284-286.

64. Amaral L. A. et. al. Classes of behavior of small-world networks / Proc. Natl. Acad. Sci. U.S.A. V. 97. P. 11149-11152.

65. Anderson R. M. Population Dynamics of Infectious Diseases: Theory and Applications, Chapman and Hall, London-New York, 1982.

66. Badariotti D. et al. Influence of network metrics in urban simulation: introducing accessibility in graph-cellular automata // 15TH European Colloquium on Theoretical and Quantitative Geography. 2007. P. 279-284.

67. Barabasi A., Albert R. Emergence of scaling in random networks // Science. 1999. V. 286. P. 509-512.

68. Barabasi A., Bonabeau E. Scale-Free Networks // Scientific American. 2003. V. 288, P. 60-69.

69. Barabasi A. Scale-Free Networks: A Decade and Beyond // Science. 2009. V. 325. -P. 412-413.

70. Bollobas B., Borgs C., et al. Directed scale-free graphs // Pro ACM-SIAM. 2001. P.132-139.

71. Bollobas B. Random Graphs. Cambridge University Press, 2001.

72. Callaway D. S., et. al. Are randomly grown graphs really random // Phys. Rev. E. V. 64, Article number: 041902. 2001.

73. Castillo C. EFFECTIVE WEB CRAWLING / Ph.D. Thesis, 2004. 180 p.

74. Cooper C., Frieze A. A general Model of Web graphs// Random Struct. Algorithm. 2002. V. 22, P. 132-139.

75. Chakrabarti D. Epidemic Thresholds in Real Networks // ACM Transactions on Information and System Security (TISSEC). 2008. V. 10. P. 1-26.

76. Chang F., Lu L. The valume of Gaint component of random graph with given expected degrees // Descrete Math. 2006. V. 20. P. 395-411.

77. Chen Z., Ji C. A Self-Learning Worm Using Importance Scanning. ACM CCS Workshop on Rapid Malcode (WORM'05), 2005.

78. Clauset A., Shalizi C.R., Newman M.J. Power-law distributions in empirical data // SIAM Rev. 2009. V. 51. P. 661-703.

79. Cohen R., et. al. Breakdown of the Internet under intentional attack / Phys. Rev. Lett. 2001. V. 86. P. 3682-3685.

80. Collier, N. T. and North, M. J. (2011) Repast HPC: A Platform for Large-scale Agent-based Modeling. In: W. Dubitzky, K. Kurowski, and B. Schott, eds., Large-Scale Computing Techniques for ComplexSystem Simulations, Wiley (In Press).

81. Dall Jesper and Christensen Michael Random Geometric Graphs //Phys. Rev. E. 2002. V.66. Article number 016121

82. Dezso Z., Barabasi A. Halting viruses in scale-free // Phys. Rev. E. 2002. V. 65, Article number 055103.

83. Dorogovtsev S.N., Mendes J.F.F., Samukhin A.N. Structure of Growing Networks: Exact Solution of the Barabasi-Albert's Model // Phys. Rev. Lett. 2000. V. 85. P. 46334636.

84. Epstein J. M. Growing Artificial Societies: Social Science from the Bottom Up // Joshua M. Epstein and Robert Axtell; Brooking Institution Press and MIT Press, Washington DC, 1996.

85. Erdos P., Renyi A. On random graphs I // Publ. Math. Debrecen. 1959. V. 6. P. 290297.

86. Faloutsos M., Faloutsos P., Faloutsos C. On Power-Law Relationships of the Internet Topology // ACM SIGCOMM Computer Communication Rev. 1999. V. 29(4). P. 251-262.

87. Grunbaum, B. Tilings and Patterns/ Branko Griinbaum and G. C. Shephard; New York: W. H. Freeman. ISBN 0-716-71193-1, 1987.

88. Gulyas, L. Relational Agent Models—A Framework for Modular and Topology-Independent Simulations. SwarmFest, Notre Dame University, Notre Dame, IN, 2003(o

89. Hammersle, J. M. A generalization of McDiarmid's theorem for mixed Bernoulli percolation // Math. Proc. Camb. Phyl. Soc. 1980. V. 88, P. 167-169.

90. Hang G., Ziff R. M. Percolation thresholds of 2-uniform lattice, 2007.

91. Hoshen J. Percolation cluster distribution. I. Cluster multiple labaling technique & critical concentration algorithm// Phys. Rev. B. 1976. V. 14(8), P. 3438-3445.

92. Howe, T. R. Containing agents: contexts, projections, and agents / T.R. Howe, N.T. Collier, M.J. North, M. T. Parker, J.R. Vos // Proceedings of the Agent 2006 Conference "Social Agents. Results and Prospects". 2006. P. 107-113.

93. Istrate G. et. al. Towards Generative Activity-based Models for Large-scale Socio-technical / Proceedings of the agent 2006 Conference "Social Agents. Results and Prospects". P. 215-230.

94. Leath P. L. Cluster size and boundary by distribution near percolation threshold // Phys. Rev. B. 1976. V. 14. P. 5046-5055.

95. Leskovec J. Dynamics of large networks / PhD Dissertation, Machine Learning Department, Carnegie Mellon University, Technical report CMU-ML-08-111, 2008. (4)

96. Leskovec J, Horvitz E. Planetary-scale views on a large instant-messaging net-work//Proc. WWW. 2008. P. 915-924.

97. Lotka, A. J. Elements of physical biology. Baltimore: Williams & Wilkins Co, 1925.

98. Mahdian, M. Stochastic kronecker graphs. In WAW '07 / M. Mahdian and Y. Xu // Proceedings of the 5th Workshop On Algorithms And Models For The Web-Graph, pages. 2007. P. 179-186.

99. Miiller, M. Lattice. Monte Carlo simulations of FePt nanoparticles: Influence of size, composition, and surface segregation on order-disorder phenomena // Phys. Rev. B. 2005. V. 72. Article number: 094203.

100. Newman M. Networks: An Introduction, M. E. J. Newman, Oxford University Press, 2010.

101. Parker M., Ascape: Abstracting Complexity. SwarmFest Proceedings/ Utah State University, Logan UT., 2000.

102. Price D. Networks of scientific papers // Science. 1965. V. 149. P. 510-515. (1)

103. Roadmap of AgentLink III, the European Coordination Action for Agent-Based Computing (IST-FP6-002006CA) edited by Michael Luck, Peter McBurney, Onn She-hory and Steven Willmott, AgentLink III, 2005.

104. Satorras P., Vespignani A. Epidemic Spreading in Scale-Free Networks // Phys. Rev. Lett. 2001 V. 86. P. 3200-3203.

105. Scopus Электронный ресурс.: Библиотечная и реферативная база данных издательства Elsevier. Электронный текст и данные. - Режам доступа: http://www.scopus.com/results/citedbyresults.url?edit.scft=l.

106. Stauffer D., Scaling Theory of Percolation Clusters // Phys. Report. 1979. V. 54. No. l.P. 1-74.

107. Stauffer D. Aharony A. Introduction to Percolation Theory 2nd ed / Taylor & Francis, 1992.

108. Valiant L. G. The complexity the enumeration and reliability problems // SIAM, J. Computing. 1979. V. 8. P. 410-421.

109. Volterra, V. Variazioni e fluttuazioni del numero d'individui in specie animali conviventi//Mem. R. Accad. Naz. dei Lincei. Ser. VI. 1926.V. 2.

110. Watts D.J., Strogatz S.H. Collective dynamics of «small-world» networks // Nature. 1998. V. 393. P. 440-442.

111. Wolfram, S. A New Kind of Science/S Wolfram; Wolfram Media, 2002.

112. Wu J., Vangala S., Gao L., and. Kwiat К An Effective Architecture and Algorithm for Detecting Worms with Various Scan Techniques. Network and Distributed System Security Symposium, 2004.

113. Ziff R. M. et. al. Generetion of percolation cluster perimeters by random walk // J. Phys. A: Math. Gen. 1984. V. 17. P. 3009-3017.

114. ИССЛЕДОВАНИЕ СВЯЗНОСТИ ПРИ СЛУЧАЙНОМ УДАЛЕНИИ ВЕРШИН/РЕБЕР В ГРАФАХ СОСЕДСТВА

115. А1 Отказ ребер для графов соседства, выращенных с использование равносильных центров