1 Аналитический обзор и постановка задачи
1.1 Постановка задачи
Задача данной работы состоит в исследовании уже существующих алгоритмов калибровки БС и разработки ускоренного алгоритма по коэффициенту кластеризации. Полученный алгоритм необходимо реализовать, протестировать и сделать вывод о его практической значимости.
1.2 Структурные характеристики случайных графов
В математической теории графов граф — это совокупность непустого множества вершин и набор пар вершин (связей между вершинами).
Объекты представляются как вершины, или узлы графа, а связи — как дуги, или рёбра. Для разных областей применения виды графов могут различаться направленностью, ограничениями на количество связей и дополнительными данными о вершинах или рёбрах [1].
Степень связности одной вершины равна количеству рёбер присоединённых к этой вершине. Также часто используется понятие средней степени связности графа. Данное значение можно получить, если поделить число рёбер в графе на число вершин это же графа.
Сл.г. имеют ряд важных характеристик. Этими характеристиками обладают как реальные сети, так и их модели. Именно по ним можно судить насколько точной является та или иная модель сети.
Рассмотрим первую характеристику – диаметр графа. Диаметр графа определяет максимальное расстояние (измеряемое в числе ребер) между вершинами в неориентированном графе, полученное в результате анализа расстояний между всеми парами вершин. С понятием диаметра графа связан эффект «Тесного мира», также известный, как правило «шести рукопожатий». Это правило означает, что перебирая круг своих ближайших знакомых, затем людей, знающих наших ближайших знакомых и т.д. любой человек опосредовано знаком с любым другим человеком в мире. Причём, как правило, число элементов в цепи не превышает 6.
Другой, не менее важной характеристикой графа является коэффициент кластеризации. Коэффициент кластеризации C в общем случае определяется как утроенное отношение среднего числа n «треугольников» в графе к среднему числу nV «вилок» (число путей длины 2).
1.3 Модель графа с нппс
Случайные графы с НППС были впервые предложены В.Н. Задорожным в 2010 году в статье [2]. Данные графы генерируются на основе правила «предпочтительного связывания» (богатый становится богаче). Граф с НППС выращивается из графа-затравки итерационно, путём добавления вершин со случайным числом рёбер r, с заданной функцией предпочтения f ≥0, зависящей от степени связности ki вершины. Вероятность присоединения свободным концом нового ребра к уже существующей вершине графа зависит от функции предпочтения и вычисляется по формуле (1):
, (1)
Эта модель обеспечивает абсолютно точное совпадение средней степени связности графа.
Модели графов с НППС в последнее время получили широкое развитие. В работе [3] были найдены эффективные способы генерации графа. В [2, 4] представлены такие способы калибровки графов, которые позволяют при заданном распределении вероятностей r, путём подбора функции предпочтения f(k) генерировать граф с требуемым распределением степени связности вершин.
Но, не смотря на точное совпадение средней степени связности графа, данная модель не может обеспечить абсолютно точное совпадение всех остальных структурных характеристик.