Введение к работе
Актуальность работы. Современное «сетевое» общество все чаще сталкивается с острыми проблемами, порождаемыми недостаточным знанием свойств больших сетей, состоящих из сотен тысяч узлов и связей. Особенно сложны для исследования большие стохастические сети (БСС), формируемые и относительно быстро изменяемые в результате взаимодействия множества случайных и детерминированных факторов, такие, как Интернет или социальные сети. В сети Интернет вследствие целенаправленного вывода или случайного выхода из строя оборудования, вследствие распространения сетевых вирусов или вследствие атак на веб-службы нередко возникают нештатные ситуации, наносящие значительный ущерб сети и ее пользователям.
Важным этапом исследования БСС является их структурная идентификация, то есть построение адекватной графовой модели топологии БСС. В связи с этим, поскольку простые графовые модели типа периодических решеток или классического случайного графа (сл.г.) Эрдеша-Реньи оказались малопригодны для описания топологии Интернета и многих других подобных ему БСС (Barabsi A., Albert R., 1999), назрела необходимость разработки новых классов сл.г. и соответствующего существенного развития теории случайных графов в целом.
В вышеупомянутой работе Альберта Барабаши и Реки Альберт предложены так называемые безмасштабные сл.г., позднее названные графами Барабаши-Альберт (графами БА). Структурные свойства графов БА позволяют успешно моделировать такие БСС как Интернет, сеть ссылок веб-страниц, сеть участия белков в обменных процессах организма, сети сотовой связи и многие другие. Установлено (Pastor-Satorras R., Vespignani A., 2001), что графам БА свойствен нулевой порог сопротивляемости распространению вируса, что объясняет необычайную выживаемость вирусов в биологических и компьютерных сетях. Другое важное свойство графов БА заключается в том, что их «целостность» надежно сохраняется при случайных удалениях вершин/ребер, но легко нарушается при целенаправленных атаках на концентраторы (вершины с большой локальной степенью связности), что объясняет аналогичные свойства сети Интернет (Albert, Jeong, and Barabsi, 2000). На основе графов БА для моделируемых ими сетей предложены и теоретически обоснованы стратегии борьбы с распространением вирусов и способы повышения устойчивости к отказам узлов и связей.
Аналитический обзор большого числа публикаций, посвященных исследованию БСС, позволяет выделить в проблеме структурной идентификации БСС следующие типичные задачи (приводятся в порядке их актуальности и приоритетности):
– выявление и формализованное описание механизма генезиса сети, который определяет ее основные, качественные характеристики;
– анализ распределения степени связности (РСС) узлов сети;
– определение коэффициентов кластеризации сетей и графов;
– анализ более тонких структурных характеристик, таких как диаметр сл.г., совместное распределение вероятностей концевых степеней ребер и т.д.;
– разработка методов генерации больших сл.г. с заданными характеристиками, соответствующими характеристикам моделируемых БСС.
Различные классы случайных графов в разное время предложили Ю. Лесковец (2006), М. Ньюмен (2001), Д. Уотс и С. Строгатц (1998). Среди российских ученых, работающих в области теории сл.г., следует отметить А. В. Коганова, Ю. Л. Павлова, А. Н. Сазонова, В. Н. Задорожного. В области исследования устойчивости и надежности широко известны работы Б. В. Гнеденко, И. Н. Коваленко, А. С. Можаева, В. А. Острейковского, И. А. Рябинина. Модели распространения эпидемий исследуют О. В. Бароян, Л. А. Рвачев, теорию сетевых игр развивают Д. А. Губанов, Д. А. Новиков, А. Г. Чхартишвили. Имитационное моделирование (ИМ) как универсальный численный метод исследования сложных систем широко используется и развивается в работах О. И. Кутузова, Ю. Г. Полляка, Ю. И. Рыжикова, Р. М. Юсупова.
Цель работы заключается в разработке методов структурной идентификации БСС для исследования сетевых процессов.
Объектом исследования являются БСС, включающие: сети типа Интернет, большие граф-схемы алгоритмов (ГСА), граф-схемы надежности (ГСН), распределенные в пространстве статистически однородные структуры (РС).
Предметом исследования являются случайные графы, методы структурной идентификации БСС, методы и алгоритмы генерации сл.г. и аналитико-имитационные модели сетевых процессов.
Методы исследования. Решение поставленных в работе задач осуществляется методами теории графов, теории клеточных автоматов, теории вероятностей, теории перколяции, теории критических явлений, методами асимптотического анализа, дифференциального и интегрального исчислений, а также методами ИМ.
Задачи работы заключаются в разработке, математическом обосновании и исследовании методов структурной идентификации БСС, включая методы генерации и калибровки:
1) графов предпочтительного связывания для сетей типа Интернет;
2) графов декомпозиции для моделирования ГСА и ГСН;
3) графов соседства для моделирования РС.
Основные положения и результаты, выносимые на защиту
1. В части моделирования сетей типа Интернет разработаны:
– ускоренный метод генерации случайных графов с нелинейным правилом предпочтительного связывания (НППС), включающих в качестве частного случая графы БА;
– методы калибровки ориентированных и неориентированных графов с НППС по эмпирическим РСС узлов моделируемых сетей;
– метод калибровки графов с НППС по коэффициенту кластеризации (метод сепарабельной реконфигурации графа).
2. В части моделирования ГСА и ГСН предложены и исследованы:
– новый класс сл.г. – графы декомпозиции;
– метод структурно-параметрической идентификации ГСА и ГСН;
– метод P-ориентированного измерения эффективности алгоритмов, предназначенных для работы с ГСА и ГСН.
3. В части моделирования РС:
– предложены и исследованы сл.г. соседства в качестве математической модели структур, расширяющей класс моделей теории перколяции (периодических решеток);
– сформулирована, исследована и подтверждена гипотеза о возможности распространения на графы соседства законов теории перколяции, установленных для решеток в части формирования контактных кластеров («задача узлов» и «задача ребер»);
– продемонстрирована возможность эффективного использования графов соседства в задачах исследования популяционной динамики и в задачах борьбы с распространением вирусов.
Научная новизна
1. Ускоренный метод генерации графов с НППС отличается от известных методов разбиением множества вершин графа на слои (подмножества вершин с одинаковыми степенями). Методы калибровки графов по РСС, основанные на известной методике калибровки графов с НППС (Задорожный В.Н., 2010), отличаются математической формализацией всех шагов процесса калибровки и возможностью калибровки ориентированных графов. Метод сепарабельной реконфигурации для калибровки сл.г. по коэффициенту кластеризации отличается от метода сепарабельной калибровки графов БА (Задорожный В.Н., Юдин Е.Б., 2009) применимостью к любым сл.г.
2. Графы декомпозиции и метод P-ориентированного измерения эффективности алгоритмов, предназначенных для работы с ГСА и ГСН, отличаются учетом вероятностной структуры связей в ГСА и ГСН. Известные методы оценки эффективности алгоритмов, обрабатывающих графы по разреженным матрицам смежности, учитывают лишь среднюю степень связности вершин.
3. Плоский и трехмерный графы соседства отличаются от традиционных моделей теории перколяции – решеток – возможностью адекватного учета стохастической структуры связей между частицами исследуемых физических сред при высокой дисперсности их размеров.
Практическая значимость
1. Ускоренный генератор графов с НППС позволяет генерировать графы сетей, содержащие сотни тысяч узлов и связей, и выполнять их многовариантный анализ, обеспечивающий возможность решения прикладных задач прогнозирования сложных сетевых процессов, а также синтеза и оптимизации принимаемых решений. Методы калибровки случайных графов с НППС по эмпирическим РСС решают задачу структурной идентификации сетей с ненаправленными и направленными связями на более высоком уровне точности, чем графы БА. Метод сепарабельной реконфигурации графов решает задачу структурной идентификации БСС в части калибровки их графовых моделей по коэффициенту кластеризации.
2. Графы декомпозиции и метод P-ориентированного измерения эффективности алгоритмов, предназначенных для работы с ГСА и ГСН, обеспечивают объективную оценку и улучшение таких алгоритмов благодаря учету вероятностной структуры их приложений.
3. Графы соседства обеспечивают более высокий по сравнению с решетками уровень точности при решении практических задач теории перколяции. Это задачи анализа процессов просачивания и фильтрации, расчета критических вероятностей отказа элементов в сложных системах сетевой структуры и т.д.
Разработанные в диссертации методы реализованы программно в системе агентного моделирования SIMBIGRAPH.
Достоверность и обоснованность результатов подтверждается строгостью математических выкладок, статистическими и численными экспериментами, примерами решения задач калибровки сл.г., согласованностью результатов аналитического и ИМ сетевых процессов, положительными внедрениями результатов диссертации в СПИИРАН (г. Санкт-Петербург), в ОмГТУ (г. Омск), в ОАО «АйПро» (г. Омск).
Апробация работы, публикации
Результаты диссертационной работы апробированы на региональной конференции «Информационные технологии и автоматизация управления» (Омск, 2009, 2010, 2011), всероссийской научно-практической конференции «Имитационное моделирование. Теория и практика» (Санкт-Петербург, 2007, 2009, 2011), всероссийской научно-технической конференции «Россия молодая: передовые технологии – в промышленность!» (Омск, 2008, 2010, 2011), международной конференции «Динамика систем, механизмов и машин» (Омск, 2009).
По теме диссертации опубликовано 13 статей, в том числе 4 статьи во включенном в перечень ВАК журнале «Омский научный вестник».
Личное участие. Задачи диссертационного исследования поставлены совместно с научным руководителем В. Н. Задорожным. В совместных публикациях в разделах, посвященных графам БА, научному руководителю принадлежат постановки задач и аналитические результаты; численные эксперименты и моделирование сетевых процессов выполнены автором диссертации. Ускоренный генератор графов БА и графов с НППС, методы калибровки этих графов по эмпирическим РСС и по коэффициенту кластеризации, графы декомпозиции, метод P-ориенти-рованного измерения эффективности алгоритмов, графы соседства и результаты их исследования принадлежат автору диссертации.
Структура и объем работы. Основная часть диссертации объемом 135 страниц машинописного текста включает введение, четыре главы, заключение, список использованных источников из 120 наименований и содержит 92 рисунка и 14 таблиц. Объем приложений – 12 страниц.
