Механизм оптимизации

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

Общие свойства

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

Описание

Затраты и выгоды в моделях оптимизации обычно можно упростить до двух атрибутов: расстояние между новым узлом и существующим; и расстояние существующего узла от центрального узла. Таким образом, целевую функцию можно записать в следующем виде:

$C_{i}=min_{j}[\delta *d_{ij}+h_{j}]$

• где $C_{i}$ означает минимальную стоимость присоединения узла «i» к существующему узлу.
• $d_{ij}$ обозначает расстояние между узлами «i» и «j»
• $h_{j}$ представляет расстояние узла 'j' от центрального узла
• $\delta$ — это параметр, который определяет вес отдельного расстояния по сравнению с расстоянием до центрального узла, и поэтому он варьируется в зависимости от настроек.

В сети автомагистралей, где города являются узлами, а соединения — автомагистралями, $d_{ij}$ будет физическое расстояние между городами, и $h_{j}$ будет расстояние от столицы (или от центрального города региона). Стоимость $\delta$ определяет тип сети, построенной механизмом оптимизации.

Звездная сеть

Механизм оптимизации приводит к созданию звездообразной сети всякий раз, когда $\delta <(1/2)^{1/2}$. Уникальной особенностью звездообразной сети является то, что большинство вновь добавленных узлов будут подключаться к центральному узлу независимо от расстояния. Звездообразную сеть можно рассматривать как сеть, в которой затраты на установление нового канала пренебрежимо малы по сравнению с выгодой от прямого подключения к центральному узлу. Звездные сети редко наблюдаются в реальности.

Случайная сеть

Случайная сеть строится методом оптимизации, когда $\delta >N^{1/2}$. В случае достаточно высокого $\delta$, затраты на создание нового канала чрезвычайно высоки по сравнению с выгодой от тесного подключения к центральному узлу. В результате большинство новых узлов будут подключаться к ближайшему доступному узлу. Реальным примером является электросетевая сеть, где стоимость строительства линии электропередачи высока, а выгода от прямого подключения к источнику питания незначительна.

Безмасштабная сеть

$4<\delta <N^{1/2}$. Если $\delta$ не является ни слишком высоким, ни слишком низким, механизм приводит к созданию безмасштабной сети, характеризующейся преимущественным присоединением. Вновь добавленные узлы, как правило, подключаются к более крупным узлам, но иногда они могут подключаться к узлам среднего размера или даже к небольшим, в зависимости от их расстояния. Большинство реальных сетей, характеризующихся базовым механизмом оптимизации, являются безмасштабными сетями, такими как сеть маршрутизаторов и сеть автомагистралей.