Обоснование необходимости разрабатываемого алгоритма

На IV региональной научно-практической конференции был представлен доклад [7], в котором особое внимание уделялось исследованию диаметра сл.г. В данной работе был проведён следующий эксперимент. Было выбрано 7 реальных сетей с уже известными параметрами. Для каждой из этих сетей было построено несколько различных модели сл.г. и подсчитан диаметр, как реальной сети, так и моделей. Длина выборки равнялась 10. Результаты этого эксперимента представлены в таблице 1.

Таблица 1 – Сравнение диаметра у реальных сетей и их моделей

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

Описание алгоритма

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

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

Рассмотрим модифицированный алгоритм генерации графа ПС [8]. Ниже представлено словесное описание разработанного алгоритма калибровки моделей БС по коэффициенту кластеризации.

Начало

G – генерируемый граф, изначально является небольшим графом-затравкой.

Цикл по добавляемым вершинам n = 1, …, N

Разыгрывается случайное число ребер r_k

Цикл по добавляемым вершинам c новой вершиной ребер k = 1, r_k

1. Вначале каждое из r_k новых ребер в соответствии с ускоренным алгоритмом генерации графа ПС [3] выбирает вершину для присоединения своего свободного конца с вершиной из множества вершин с заданной степенью связности i (слоя) по правилу ,

j = 1, K, где K – число слоев в G

2. Затем, если (r_k > 1) выполняется процедура случайного (равновероятного) выбора ребра e в графе G, связывающего вершины из выбранных слоев. К смежным к ребру е вершинам присоединяется 2 из r новых ребер, образуя гарантированный треугольник из вершин

3. Остальные (r_k – 2) ребра выбирают вершины из соответствующих слоев равновероятно.

4. Добавляется вершин и r_k ребер

Конец цикла по r_k

Конец цикла по n