Ускоренный метод генерации графа БА и графа с НППС

Данный алгоритм был представлен в [5].

Граф БА генерируется из небольшого графа-затравки путём добавления новых вершин с фиксированным числом рёбер m ≥ 1. Свободный конец нового ребра присоединяется в соответствии с формулой (2):

, j = 1,…, N, (2)

где N – текущее число вершин в графе.

Из формулы видно, что чем больше степень связности у вершины, тем выше вероятность её выбора.

На рисунке 1 представлена блок схема этого алгоритма.

Рисунок 1 – Блок схема алгоритма генерации графа БА

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

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

Блок схема данного алгоритма представлена на рисунке 2 [5].

Рисунок 2 – Блок схема алгоритма ускоренного метода генерации графа БА и графа с НППС

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