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

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

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

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

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

Случайный граф, удовлетворяющий данному условию, предложили А.Барабаши и Р.Альберт (1999), который строится на основе правила «предпочтительного связывания». Также действующие модели предложили Д. Уотс и С. Строгатц (1998), М. Ньюман (2000), С. Н. Дороговцев, Дж. Мендес и А. Н. Самухин (2001), К. Купер и А. Фрези (2002), B. Боллобас (2001), Ф. Чанг и Л. Лу (2006), Ю. Лесковец (2006), В. Н. Задорожный (2010). Но, не смотря на большое разнообразие моделей, ни одна из сетей не даёт полного соответствия с реальной сетью.

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

Пояснительная записка содержит 3 главы.

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

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

В третьей главе описаны некоторые аспекты программной реализации алгоритма.

Также пояснительная записка содержит список сокращений, список использованных источников и приложение, где можно найти код данного алгоритма.