Генерирование графа с заданным распределением в условиях распределения топологии

Универсальная система моделирования сетевых структур, разрабатываемая нами в рамках НИР, представляет собой параллельный симулятор сетей с расширяемой (за счет унифицированных модулей) функциональностью.

Важной задачей при моделировании сетей является генерирование топологии с заданным распределением степеней вершин (например, равномерным или степенным).

Каждый вычислитель (процесс параллельной программы) владеет только фрагментом будущей сети в виде набора узлов с пустыми списками смежности. Программист модуля расширения, генерирующего топологию, должен заполнить списки смежности узлов. Чтобы не генерировать глобальную топологию, предложен алгоритм, по которому 1)каждый вычислитель генерирует собственный фрагмент топологии с некоторым распределением, 2)все фрагменты «склеиваются» в одну сеть. Распределение для пункта 1 генерируется вероятностным алгоритмом на основании заданного глобального распределения.

Алгоритм склеивания пункта 2 использует операцию «разрыв-соединение», суть которой в том, что связи A-B и С-D (принадлежащие разным фрагментам) разрываются и устанавливаются новые: А-С и B-D (соединяющие фрагменты). Данная операция, очевидно, не изменяет степень вершин.

В каждом сгенерированном фрагменте сети отыскивается множество связей, которые будут участвовать в операциях «разрыва-соединения», затем вычислители обмениваются данными множествами и на их основании корректируют списки смежности своих узлов.

Вычислительные эксперименты на кластере подтверждают корректность и эффективность предложенного метода. Так, временные затраты на генерирование топологии из 1.000.000 узлов и степенным распределением с показателем ? = 2.0 падают с 3480 секунд (при использовании одного вычислителя) до 28 секунд (при использовании десяти вычислителей), что объясняется большой временной сложностью выбранного алгоритма генерирования топологии сети из N узлов (порядка O(N2)). Полученная сеть имеет 5.514.196 связей, число связей между узлами, принадлежащими разным вычислителям - 419.548 (8%). Мерой качества работы алгоритма можно считать норму вектора разности векторов исходного V и получившегося V* распределений по метрике пространства l1, которая не превосходит 100 (0.0001% от нормы вектора V), что свидетельствует о высокой точности алгоритма.