Аналитический обзор и постановка задачи

Постановка задачи

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

Структурные характеристики случайных графов

В математической теории графов граф — это совокупность непустого множества вершин и набор пар вершин (связей между вершинами).

Объекты представляются как вершины, или узлы графа, а связи — как дуги, или рёбра. Для разных областей применения виды графов могут различаться направленностью, ограничениями на количество связей и дополнительными данными о вершинах или рёбрах [1].

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

Сл.г. имеют ряд важных характеристик. Этими характеристиками обладают как реальные сети, так и их модели. Именно по ним можно судить насколько точной является та или иная модель сети.

Рассмотрим первую характеристику – диаметр графа. Диаметр графа определяет максимальное расстояние (измеряемое в числе ребер) между вершинами в неориентированном графе, полученное в результате анализа расстояний между всеми парами вершин. С понятием диаметра графа связан эффект «Тесного мира», также известный, как правило «шести рукопожатий». Это правило означает, что перебирая круг своих ближайших знакомых, затем людей, знающих наших ближайших знакомых и т.д. любой человек опосредовано знаком с любым другим человеком в мире. Причём, как правило, число элементов в цепи не превышает 6.

Другой, не менее важной характеристикой графа является коэффициент кластеризации. Коэффициент кластеризации C в общем случае определяется как утроенное отношение среднего числа n _D «треугольников» в графе к среднему числу n _V «вилок» (число путей длины 2).