Определения, обозначения, сокращения
АС – автономная сеть
БС – большие сети
БСВ – большая случайная величина
БСС – большая стохастическая сеть
граф БА – граф Барабаши-Альберт
граф с НППС – граф с нелинейным правилом предпочтительного связывания
ДСВ – дискретная случайная величина
ПС – предпочтительное связывание
РСС – распределение степени связности
сл.г. – случайный граф
Содержание
Введение 6
1 Аналитический обзор и постановка задачи 8
1.1 Структурные характеристики случайных графов 8
1.2 Некоторые модели случайных графов 9
1.2.1 Модель графа Барабаши ‑ Альберт 9
1.2.2 Модель графа Уаттса – Строгатца 10
1.3 Модель графа с НППС 12
1.4 Обзор аналогов 13
1.4.1 Ускоренный метод генерации графа БА и графа с НППС 13
1.4.2 Метод сепарабельной реконфигурации по коэффициенту кластеризации 21
1.5 Выводы из аналитического обзора и постановка задачи ВКР 22
2 Разработка алгоритма генератора графа с НППС с возможностью калибровки по коэффициенту кластеризации 24
2.1 Алгоритм генерации графа с НППС с возможностью калибровки по коэффициенту кластеризации 24
3 Аспекты программной реализации в системе имитационного моделирования Simbigraph 31
Заключение 33
Список использованных источников 35
Приложение А 37
Введение
В современном мире можно обнаружить множество различных сетей. Это и биологические сети, сети дорог, телефонные сети, нейронные сети и в том числе сети интернет.
С геометрической точки зрения сеть представляет собой множество одинаковых компонентов – вершин, связанных друг с другом рёбрами, поэтому исследование сетей неразрывно связано с теорией графов. Теория графов возникла в восемнадцатом веке в работе Леонарда Эйлера, чья ранняя работа в основном касалась маленьких графов с высокой степенью регулярности. В двадцатом веке особенно большое внимание уделялось изучению случайных графов. Теория случайных графов широко используется в изучении сложных сетей. Теория случайных графов была представлена Полом Эрдешом и Альфредом Реньи, после того, как Эрдеш открыл, что вероятностные методы часто оказываются полезными в проблемах теории графов.
С развитием технологий, одной из самых больших сетей стала сеть интернет («всемирная паутина», имеющая английскую аббревиатуру WWW – World Wide Web), и значительное внимание стало уделяться её исследованию. К тому же, к этому времени возможности вычислительной техники значительно возросли, позволив обрабатывать большие массивы данных, позволив тем самым строить модели больших сетей и исследовать их.
И действительно, имея мгновенный снимок сети интернет сейчас не сложно представить её в виде графа: каждый отдельный сайт будет вершинной графа, а ссылки между ними будут являться его рёбрами. Однако интернет является постоянно изменяющейся структурой и без исследований нельзя предугадать, как будет выглядеть данная сеть в следующий момент времени. Поэтому последнее время большое внимание стало уделяться моделям графов больших сетей (БС). А в исследовании сети интернет большую роль играют модели сетей на основе случайных графов.
Ранее большие сети рассматривались на основе классического случайного графа, получаемого случайным равномерным распределением. Однако при анализе реальной сети интернет исследователи столкнулись с иным характером распределения степени связности графа. Было выяснено, что распределение вероятностей узлов степени связности обычно подчиняется степенному закону. Случайный граф, удовлетворяющий данному условию, предложили А.Барабаши и Р.Альберт (1999), который строится на основе правила «предпочтительного связывания». Также действующие модели предложили Д. Уаттс и С. Строгатц (1998), М. Ньюман (2000), С. Н. Дороговцев, Дж. Мендес и А. Н. Самухин (2001), К. Купер и А. Фрези (2002), B. Боллобас (2001), Ф. Чанг и Л. Лу (2006), Ю. Лесковец (2006), В. Н. Задорожный (2010). Но, не смотря на большое разнообразие моделей, ни одна из сетей не даёт полного соответствия с реальной сетью. Так было выяснено, что почти все модели отличаются от моделируемых сетей по коэффициенту кластеризации и диаметру графа.
Следует также отметить, что программы для анализа графов и их генерации оказываются весьма медлительными, поскольку приходится генерировать большие графы, состоящие из сотен тысяч вершин и ребер. Поэтому в данной работе используются различные способы ускорения разработанных алгоритмов.