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

В данном разделе производится обзор существующих методов и по итогам ставится задача исследования.

В первом параграфе этого раздела описаны основные понятия теории сетей. Приводятся их необходимые описания и определения.

Во втором параграфе производится обзор существующих графовых моделей, вводятся понятия случайных графов Барабаши-Альберт, Эрдеша-Реньи, Уаттса-Строгатца, описаны правила их генерации.

В третьем параграфе вводится понятие случайного графа с нелинейным правилом предпочтительного связывания (НППС), который был предложена Задорожным В.Н. в 2010 году.

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

В конце раздела, исходя из представленной информации, ставится задача данного исследования.

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

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

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

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

Большие сети – это сети, содержащие тысячи вершин и связей между ними.

Случайный граф (сл.г.) – граф, в которых ребра распределены случайным образом.

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

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

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

Калибровка графа позволяет построить модель графа так, чтобы сохранить распределение степени связности (РСС) вершин, путём подбора других параметров, в зависимости от поставленных целей.