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

005013493

ЮДИН Евгений Борисович

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

Специальность 05.13.01 - Системный анализ, управление и обработка информации

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

1 5 н* ° 2012

Сургут-2012

005013493

Работа выполнена на кафедре «Автоматизированные системы обработки информации и управления» в Федеральном государственном бюджетном образовательном учреждении высшего профессионального образования «Омский государственный технический университет»

Научный руководитель:

Официальные оппоненты:

кандидат технических наук, доцент ЗАДОРОЖНЫЙ Владимир Николаевич

доктор технических наук, профессор ИНЮТИН Сергей Арнольдович

кандидат технических наук, доцент МЫЗНИКОВА Татьяна Александровна

Ведущая организация:

Учреждение Российской академии наук Санкт-Петербургский институт информатики и автоматизации РАН (СПИИРАН), г. Санкт-Петербург.

Защита диссертации состоится 30 марта 2012 г. в 14.00 часов на заседании совета по защите докторских и кандидатских диссертаций Д 800.005.06 при ГОУ ВПО «Сургутский государственный университет ХМАО - Югры» по адресу: 628400, Тюменская обл., ХМАО - Югра, г. Сургут, ул. Ленина, 1.

С диссертацией можно ознакомиться в научной библиотеке университета.

Автореферат разослан «29» февраля 2012 г.

Ученый секретарь совета по защите докторских и кандидатских диссертаций Д 800.005.06

В.С. Микшина

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

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

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

В вышеупомянутой работе Альберта Барабаши и Реки Альберт предложены так называемые безмасштабные сл.г., позднее названные графами Барабаши-Альберт (графами БА). Структурные свойства графов БА позволяют успешно моделировать такие БСС как Интернет, сеть ссылок веб-страниц, сеть участия белков в обменных процессах организма, сети сотовой связи и многие другие. Установлено (Pastor-Satorras R., Vespignani A., 2001), что графам БА свойствен нулевой порог сопротивляемости распространению вируса, что объясняет необычайную выживаемость вирусов в биологических и компьютерных сетях. Другое важное свойство графов БА заключается в том, что их «целостность» надежно сохраняется при случайных удалениях вершин/ребер, но легко нарушается при целенаправленных атаках на концентраторы (вершины с большой локальной степенью связности), что объясняет аналогичные свойства сети Интернет {Albert, Jeong, and Barabasi, 2000). На основе графов БА для моделируемых ими сетей предложены и теоретически обоснованы стратегии борьбы с распространением вирусов и способы повышения устойчивости к отказам узлов и связей.

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

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

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

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

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

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

Различные классы случайных графов в разное время предложили Ю. Лесковец (2006), М. Ньюмен (2001), Д. Уотс и С. Строгатц (1998). Среди российских ученых, работающих в области теории сл.г., следует отметить A.B. Коганова, Ю.Л. Павлова, А.Н. Сазонова, В.Н. Задорож-ного. В области исследования устойчивости и надежности широко известны работы Б.В. Гнеденко, И.Н. Коваленко, A.C. Можаева, В.А. Острейковского, И.А. Рябинина. Модели распространения эпидемий исследуют О.В. Бароян, Л.А. Рвачев, теорию сетевых игр развивают Д.А. Губанов, Д.А. Новиков, А.Г. Чхартишвили. Имитационное моделирование (ИМ) как универсальный численный метод исследования сложных систем широко используется и развивается в работах О.И. Кутузова, Ю.Г. Полляка, Ю.И. Рыжикова, P.M. Юсупова.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Научная новизна

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

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

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

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

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

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

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

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

Разработанные в диссертации методы реализованы программно в системе агентного моделирования ЗМВЮЯАРН.

Достоверность и обоснованность результатов подтверждается строгостью математических выкладок, статистическими и численными экспериментами, примерами решения задач калибровки сл.г., согласованностью результатов аналитического и ИМ сетевых процессов, положительными внедрениями результатов диссертации в СПИИРАН (г. Санкт-Петербург), в ОмГТУ (г. Омск), в ОАО «АйПро» (г. Омск).

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

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

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

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

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

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

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

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

В первой главе выполняется аналитический обзор проблем структурной идентификации БСС и методов моделирования сетевых процессов. Распространенными моделями топологии БСС являются решетки и случайные графы. Рассматриваются графы Эрдеша-Реньи (Erdas Р., RenyiA., 1959), Уотса-Строгатса (Waits D., Strogatz S., 1998), графы БА (BarabäsiA., Albert R., 1999), конфигурационные графы Ньюмена (Newman, 2001), графы Купера-Фрези (Cooper С., Frieze А., 2002), Чан-га-Лу (Chang F., Lu L„ 2006), графы с НППС (Задорожный В.Н., 2010).

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

p,= k,/Zjkj. (1)

Граф БА имеет асимптотически степенное РСС {Qk} вершин: при к-* °о вероятность Qk того, что случайно выбранная вершина имеет степень

связности к, сходится к ск где с, а > 0 константы. На рис. 1 представлены РСС узлов в реальных сетях и РСС вершин в графах БА.

Рис. 1. Графики РСС вершин в графах БА (сплошные линии) и РСС узлов (маркеры) в сетях:

а) маршрутизаторов Интернет; б) пользователей программы PGP; е) автономных систем Интернет; г) адресов электронной почты; д) ссылок веб-страниц; е) товаров Amazon.com.

На каждом шаге генерации графа с НППС к графу добавляется вершина со случайным числом x(g<x<h) ребер. Вероятность р, связывания нового ребра с /-й вершиной пропорциональна значению функции предпочтения f(k) в точке к = к,:

p^m/Zj/ikj). (2)

Функцию/да можно задать рядом весов fg,fg-U ...,fk, ... (конечным или бесконечным), в котором fs=f{g) >0 иft= f(k) >0 при к>g. Графы БА являются частным случаем графов с НППС, который определяется выбором функции предпочтения f{k) = к при g = h = т. Обнаружены гибкие возможности калибровки графов с НППС по эмпирическим РСС узлов в широком диапазоне распределений (Задорожный В.Н., 2010).

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

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

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

Бесконечно

большая

решеггка

Решетка

конечнот

размера

Рис. 2. Изменение вероятности Рис. 3. Максимальные кластеры в трех опытах на Р(р) в окрестности критиче- квадратной решетке (задача узлов),

ской точки рс. Меньшие кластеры не показаны.

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

На основе выполненного аналитического обзора уточняются задачи диссертационной работы.

Вторая глава посвящается разработке методов структурной идентификации БСС на основе графов с НППС.

1) Предлагается метод калибровки графов с НППС по эмпирическим РСС узлов сетей. Задача калибровки сводится к выбору подходящего распределения вероятностей rg, ...,rf, сл.в. х е {g, ...,h} - числа ребер в приращениях графа, и выбору весов fg,fg+ ь • ••,/м ДЛЯ реализации правила (2). Вероятности {г,} и веса {fk} должны быть такими, что-

бы РСС вершин графа совпадаю с известным РСС. >()к) узлов моделируемой сети.

Область допустимых решений для вероятностей {г,} определяется условиями (Задорожный В. Н., 2010):

о<^.<1, i=g,h и (3)

1! -Йг (4)

h (5)

'-g i i

(6)

i=g ¡=g

где m = (к)/2 - среднее число ребер в приращениях графа, (к) = Y,kQk -средняя степень узлов сети, g - наименьшая степень узлов.

Обозначим через FQ(t) функцию распределения (ф.р.) вероятностей Qk- Fç{t) = YjQk > чеРез Fr(t) ~ ф.р. вероятностей r,\ Fr(t) = Yr .

i<t

Функции FQ(t) и Fr(t), как ф.р. дискретных сл.в., однозначно определяются своими значениями в точках t е {g, g + 1, ...}. Условия (4) и (6) в терминах ф.р. принимают вид F ЛИ) = 1 и Fr(t) > FQ(t). Этим требованиям в общем случае удовлетворяет множество функций F,.(t) при разных h. Из (5) и неравенства Fr{t) > F0(t) вытекает ограничение снизу для h\

h-1 ~ ),-А

Sr=Y[\-Fr(i)} = m => Se=£[l-F0(i)]âm. (7)

1=0 i=0 Разработанный метод выбора подходящих вероятностей {г,} описывается следующей последовательностью шагов.

1. Определяем наименьшее Л, удовлетворяющее неравенству (7).

2. Полагаем Fr(iy= /^(Д / = ..., А-1; Рг(к) = 1.

3. Вычисляем 5е по формуле (7); А = - т. Если А = 0, переходим к 5.

4. Разделяя А на добавки к значениям ..., Р^-Х), наращиваем их так, чтобы для получаемой ф.р. Fr(í) в (7) выполнялось равенство = т.

5. Полагаем п = - /урМ), i = g,И.

Шаг 4 может быть выполнен различными способами. Например, можно просто увеличить Рг(И-\) на А (рис. 4). В этом случае на шаге 5 получаем % = ..., гИ_2=0М, гь_х = + А, г„ = 1 - Гв(Л-1)~ А. Другой возможный способ - увеличивать до выполнения равенства т (увеличивая, при необходимости, и ^(¿+1), ... , что-

бы выполнялось требование неубывания ф.р. -РД/)). В этом случае несколько подряд вероятностей ... могут стать равными нулю.

Рис. 4. Простейший способ nocí роения ф.р. Fr(t) no РСС \Qt} узлов.

Подбор весов fg,fg+\, ...Ju для правила (2) выполняется по формулам теории случайных графов с НППС (Задорожный В. Н., 2010):

Л=тМ; k=g+i,...,M-, (8)

(Jg Ук {¿к

2) Калибровку ориентированного графа с НППС в диссертации предлагается реализовать по известным распределениям полустепени исхода (РПИ) и полустепени захода (РПЗ) узлов сети с направленными связями. Разработанный метод калибровки демонстрируется на примере моделирования сети товаров электронного магазина Amazon (рис. 5).

Рис. 5. Распределения иолустепеней захода и исхода в графе с ИППС и в моделируемой сети товаров магазина Amazon.

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

При выращивании орграфа с НППС приращения графа представляют собой вершины со случайным числом х исходящих дуг (заходящие дуги у приращений отсутствуют). Распределение {г,} сл.в. х совпадает с РПИ {Q~k} узлов реальной сети, предопределяя точно такое же РГ1И у вершин выращиваемого графа. Требуемое РПЗ вершин сформируется при этом автоматически, если веса {fk} определить по формуле (8).

3) Предлагается ускоренный метод генерации графов БА и графов с НППС. Основные затраты времени на генерацию этих графов определяются числом итераций, выполняемых при каждом выборе вершины в соответствии с правилом (1) или (2). Для уменьшения среднего числа итераций выбор вершины выполнятся в разработанном методе в два этапа: вначале разыгрывается степень вершины, а затем из множества (слоя) вершин с этой степенью выбирается любая вершина равновероятно. При генерации графа БА с N вершинами общее число итераций при этом резко снижается, поскольку число слоев К значительно меньше числа вершин: К = 0{Nm) (Задорожный В.Н., Юдин Е.Б., 2009). Показано, что в базовом методе генерации графов БА, основанном на непосредственном выборе вершины для связывания с новым ребром, общее число итераций выбора вершин равно 0(N2), а в ускоренном методе - лишь 0(NlnN).

На рис. 6 представлены результаты измерения времени генерации графа БА предложенным ускоренным методом и методами, реализованными в широко распространенных системах моделирования JUNG и AnyLogic 6.

4) Для калибровки графа по коэффициенту кластеризации (без изменения РСС вершин) предлагается метод реконфигурации графа. Коэффициент кластеризации С в общем случае определяется как утроенное отношение среднего числа ид «треугольников» в графе к среднему числу nv «вилок» (т.е. путей длины 2): C = 3nA/nv. Для увеличения числа «треугольников» в графе циклически необходимое число раз используется следующая процедура, иллюстрируемая рисунком 7 (аналогичная процедура позволяет уменьшать число треугольников).

500

250 -

t(c)

Генератор AnyLogic 6

Генератор с использованием слоев

10000 20000 30000

Рис. 6. Зависимость времени / генерации графа БА (т = 2) от числа вершин /V.

Эксперименты проведены в АпуЦ^ю 6.1.

1. Случайно выбираем ребро /?, не входящее в треугольник. Определяем степени связности / и т вершин, инцидентных й.

2. Случайно выбираем вершину а, и среди смежных ей вершин отыскиваем две несвязные вершины Ь и с. Если таких нет, возвращаемся к 2.

3. Определяем степени связности / и у вершин Ь и с соответственно. Ребро Я переносим - ставим его между найденными вершинами бис. В результате этой операции количество вершин со степенями связности I, т, /,у уменьшается, а количество вершин со степенями /- 1, т - 1, / + ], ] + 1 увеличивается (вследствие чего изменяется РСС).

4. Компенсируем изменение РСС:

- выбираем случайное ребро Т (отличное от К) со степенями связности / + 1,./+ 1;

- находим случайные вершины со степенями связности /- 1, т - 1;

- перенося выбранное ребро Т, соединяем им найденные вершины.

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

Разработанные в главе методы калибровки ориентированных и неориентированных графов с НППС реализованы программно в системе моделирования 81МВГСЯАРН.

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

I) Графы декомпозиции включают два параметрических семейства графов: сл.г. для моделирования граф-схем алгоритмов (ГСА) и сл.г. для моделирования граф-схем надежности (ГСН).

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

связносги /, т,у, г соответственно.

новкам Дейкстры. Такой способ генерации воспроизводит механизм генезиса алгоритмов и программ, проектируемых в стиле нисходящего структурного программирования (рис. 8, 9).

Выбор вероятностей подстановок Р = {рь рг, ръ рА, р5-Рг] представляет собой задачу параметрической идентификации графов декомпозиции, решаемую на основе статистического анализа ГСА, принадлежащих определенному классу (приложению). В главе предлагается Р-ориентированный метод измерения эффективности программ, предназначенных для работы с ГСА. Программы испытываются путем обработки большого числа тестовых ГСА, генерируемых в соответствии с их вероятностной моделью Р.

На практике /'-ориентированный метод использовался для оценки эффективности метода редукции Байцера (Веггег В., 1970). Графы, моделирующие ГСА, генерировались рекурсивно из единственной вершины - оператора действия (рис. 8). В результате экспериментов установлено, что время I редукции ГСА с N вершинами методом Байцера асимптотически пропорционально №, где а е (2, 3). Так, а «2.7 для ГСА без циклов, порождаемых декомпозициями Д1, Д2, V; а « 2.72 для ГСА. получаемых применением декомпозиций Д1-Д5, V; а» 2.5 для ГСА,

содержащих в основном вложенные циклы, то есть получаемых декомпозицией Д5.

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

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

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

Рис. 10. Оценка порога Рис. 11. Максимальные контактные кластеры

перколяции в задаче ребер. (меньшие кластеры не показаны).

Для графов, выращенных с использованием равносильных центров, критическая вероятность в задаче узлов составляет рс ~ 0.491, а в задаче связей рс~ 0.759. Графы, выращенные с двумя типами центров, с долями сильных и слабых центров, соответственно, 9/10 и 1/10, и с их относительными «силами» а>\ = 8/9 и = 1/9, имеют в задаче узлов критическую вероятность рс ~ 0.495, а в задаче связей /?с= 0.633. Значимое различие для этих двух графов значений рс в задаче связей (0.759 и 0.633) объясняется следующим образом. В графе соседства, выращенном из центров разной силы, имеются редкие вершины («звезды») с высокой степенью связности, которые окружаются множеством вершин

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

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

о^ЛО-СоЛГ-'7^, где й- размерность пространства (для плоской сети й= 2), с0 - коэффициент, зависящий от семейства графов, V - одна из универсальных констант теории перколяции. Подбор V и с0 (рис. 12) по эмпирическим зависимостям полученным при исследовании методом Монте-Карло устойчивости графов соседства к случайному удалению вершин/ребер, подтверждает применимость к графам соседства универсальной константы теории перколяции V = 4/3 (установленной для всех плоских решеток). Таким образом, асимптотические зависимости сг (IV) для различных решеток и для плоских графов соседства с разными силами центров совпадают с точностью до константы с0.

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

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

Рис. 12. Теоретическая и эмпирическая зависимости а от N.

В четвертой главе рассмотрены аспекты реализации системы агент-ного моделирования SIMBIGRAPH (рис. 13).

Система SIMBIGRAPH спроектирована для решения проблемы, поднятой в отчете европейского сообщества по развитию агентных вычислений (AgentLink III, 2006) и заключающейся в необходимости интенсивного развития теоретических аспектов агентного моделирования, неотъемлемой частью которого является разработка новых моделей и методов структурной идентификации сетей взаимодействия.

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

•Ш Network-based 03ine: 2D Lattices

i Resume : Curren! modelling t¡rne:1739,0

Tima oímoaettítts

Titne of updating

LS Pseuúo Lattices

Deterministic Pft-graph [r-j stonastic PA-grapn Щ Networks I * Continuous Area '•M Network formation games Decomposition grapn £_>: Neigborhood graph DolauneY Triangulation

OríaTyfle

Console

Рис. 13. Моделирование в SIMBIGRAPH процесса сегрегации атомов на поверхности биметаллической наночастицы (пользовательский интерфейс программы).

Внутренним языком разработки агентных моделей в SIMBIGRAPH является язык программирования высокого уровня Java (обеспечивается автоматическая компиляция кода). В системе реализованы средства сохранения рабочих проектов в формате XML (проект включает данные о структуре взаимодействий между агентами и описание логики взаимодействий). Аналогами SIMBIGRAPH являются такие известные сис-

темы ИМ как ASCAPE (Бруклинский институт, США), MASON (Университет Джорджа Мейсона, США), RepastLogo (Чикагский университет, Аргонская национальная лаборатория, США), AnyLogic (XJ Technologic, Россия), SIMULAB (ОмГТУ, Россия).

В главе рассматриваются агентные модели, реализованные в SIMBIGRAPH на основе графов с НППС. Проводится расчет устойчивости Интернет к случайным отказам и к распространению вируса. Интернет моделируется на уровне маршрутизаторов (рис. 14) и на уровне автономных систем.

150 тыс. О вершин Граф БА, m = 2

100 V о _ Граф с НГШС Сеть маршрутизаторов (эталон)

50 \ж о

0.5 1 ^ а)

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

Результаты моделирования устойчивости Интернета к отказам и процессов распространения в Интернете вирусов при использовании калиброванных графов с НППС лучше согласуются с эталонными результатами, чем при использовании графов БА. В качестве эталонных результатов использовались результаты моделирования на графе, построенном непосредственно по данным о топологии сети маршрутизаторов Интернет по ее состоянию на 2006 г. (включающим данные о 124 651 узле и 207 214 связях сети маршрутизаторов).

Также в четвертой главе подробно рассматривается реализация графов соседства с использованием пакета распределенных вычислений ЛеразШРС. Приводятся результаты экспериментов по измерению скорости генерации графов в зависимости от числа задействованных процессоров вычислительного кластера ОмГТУ. Значительное ускорение, получаемое при распределении вычислений, обусловлено тем, что генерация графов соседства основана на эволюции клеточных автоматов, которые, как известно, являются одной из базовых моделей эффективно распараллеливаемых вычислений.

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

Основные результаты опубликованы в следующих работах: В журналах перечня ВАК

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

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

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

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

В материалах международных н всероссийских конференций

5. Юдин Е. Б. Концепция метаязыка как основы структурной идентификации задач распознавания образов // Научная сессия ТУСУР-2006: материалы докл. Всерос. науч.-техн. конф. студентов, аспирантов и молодых ученых. - Томск: Изд-во «В-Спектр», 2006 - С. 233-235.

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

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

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

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

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

II. Юдин Е. Б., Задорожный В. Н., Пендер Е.А. Случайные графы с нелинейным правилом предпочтительного связывания в системе агентного моделирования ЭМБЮЛАРН // Имитационное моделирование. Теория и практика / матер. 5-й Всерос. конф. - СПб.: ФГУП ЦНИИТС. -2011.-Т. 1,-С. 425-429.

12. Юдин Е. Б., Стишенко П. В. Использование среды распределенного моделирования геравШрс на вычислительном кластере ОмГТУ // Россия молодая: передовые технологии - в промышленность: матер. IV Всерос. конф. Омск: Изд-во ОмГТУ, 2011. - Кн. 1. - С. 334-337.

13. Юдин Е. Б., Васильев Е. Р. Генерация графов соседства в среде распределенного агентного моделирования НераБШРС // Имитационное моделирование. Теория и практика / матер. 5-й Всерос. конф. - СПб.: ФГУП ЦНИИТС. - 2011. - Том 1. - С. 311-314.

Свидетельства о регистрации комплекса программ

1. Система агентного моделирования 51МВГСИАРН / В. Н. Задорожный, Е. Б. Юдин // Свидетельство о регистрации электронного ресурса №16539 / Объединенный фонд электр. ресурсов «Наука и Образование» - 16.12.2010.

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

Подписано в печать 27.02.2012. Формат 60x84/16. Усл. печ. л. 1,5. Печать трафаретная. Тираж 100. Заказ П-19.

Отпечатано полиграфическим отделом Издательского центра СурГУ. г. Сургут, ул. Энергетиков, 8, тел. (3462) 76-30-67.

ГОУ ВПО «Сургутский государственный университет ХМАО - Югры» 628400, Россия, Ханты-Мансийский автономный округ, г. Сургут, пр. Ленина 1, Тел. (3462) 76-29-00, факс (3462) 76-29-29

61 12-5/1968

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

ЮДИН Евгений Борисович

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

Специальность: 05.13.01 - Системный анализ, управление и обработка

информации

ДИССЕРТАЦИЯ

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

Научный руководитель:

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

ЗАДОРОЖНЫЙ Владимир Николаевич

Омск 2012

СОДЕРЖАНИЕ

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

ВВЕДЕНИЕ 5

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

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

1.2. Решетки 16

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.2.4. Модель «хищник-жертва» на графах соседства 90 Выводы по третьей главе 94 ГЛАВА 4. ПРОГРАММНЫЕ СРЕДСТВА МОДЕЛИРОВАНИЯ СЕТЕВЫХ СТРУКТУР И ПРОЦЕССОВ 96

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

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

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

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

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

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

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

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

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

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

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

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

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

ВС - вычислительная система

граф БА - граф Барабаши-Альберт

граф с 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 страниц.

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

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

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

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

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