Введение. 
Разработка и исследование ускоренного алгоритма калибровки моделей больших сетей по коэффициенту кластеризации

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

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

В двадцатом веке в область интересов ученых вошли так называемые случайные графы, т. е. графы, которые генерируются в результате некоторого случайного процесса. Теория случайных графов была представлена Полом Эрдешом и Альфредом Реньи, после того, как Эрдеш открыл, что вероятностные методы часто оказываются полезными в проблемах теории графов. Генерация графа Эрдеша-Реньи очень проста: нужно с некоторой вероятностью p распределить рёбра между всеми вершинами. Тем не менее, эта модель активно использовалась в теории перколяции и теории критических явлений, поскольку обладает критическими свойствами, например, существует такая критическая вероятность pc связывания вершин, ниже которой сеть распадается на множество несвязных компонент, а выше — образуется так называемый стягивающий кластер. Граф Эрдеша-Реньи, по существу, являлся самым популярным и единственным случайным графом с 50-х годов прошлого века.

Ситуация поменялась за последние десятилетия. Причиной этому стал тот факт, что большое значение приобрели сеть интернет и «всемирная паутина», сеть ссылок веб-страниц, имеющая английскую аббревиатуру WWW — World Wide Web. В то же время возможности вычислительной техники значительно возросли, позволив обрабатывать большие массивы данных, и тем самым строить модели таких сетей как сеть белковых взаимодействий, сеть генных последовательностей, социальные сети и т. д. А поскольку стало возможным получить мгновенный снимок сети, например, подсети WWW и представить его в виде графа (каждый отдельный сайт будет вершинной графа, а ссылки между ними будут являться его рёбрами Аналогично, на основе анализа BGP таблиц можно получить граф, представляющий собой мгновенный снимок сети автономных систем Интернет), то встал вопрос анализа этих графов. Однако интернет и WWW являются постоянно изменяющейся структурой, появилось желание исследовать их с помощью случайных графов. Но детальное исследование перечисленных сетей показало, что, вопреки ожиданиям, эти сети очень сильно отличаются от графа Эрдеша-Реньи.

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

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