Optimization mechanism

In network science, the optimization mechanism is a network growth algorithm, which randomly places new nodes in the system, and connects them to the existing nodes based on a cost-benefit analysis. Depending on the parameters used in the optimization mechanism, the algorithm can build three types of networks: a star network, a random network, and a scale-free network. Optimization mechanism is thought to be the underlying mechanism in several real networks, such as transportation networks, power grid, router networks, the network of highways, etc.

General Properties

The optimization mechanism is a model with growth, in which preferential attachment is valid under certain assumptions. As opposed to the copying model, the optimization model uses global information about the network, to connect the newly entering nodes to the existing ones, thus reducing the amount of randomness in the process. The model's mechanism is based on a cost-benefit comparison, that is for each entering node 'i', the algorithm calculates the net benefit (benefits minus costs) of connecting 'i' to each existing node, and connects node 'i' to the node which gives the highest net benefit.

Description

The costs and benefits in the optimization models can generally be simplified into two attributes: the distance between the new node, and the existing one; and the distance of the existing node from the central node. Thus the goal function can be written in the following form:

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

where C_i stands for the minimal cost of attaching node 'i' to an existing node, d_{ij} denotes the distance between node 'i' and 'j', and h_j represents the distance of node 'j' from the central node. Delta is a parameter, that determines the weight of the individual distance compared to the distance to the central node, and thus it varies across different settings. In a highway network setting - where cities are nodes and links are highways - d_ij would be the phisical distance between cities, and h_j would be the distance from the capital (or from the central city of the region). The value of \delta determines the type of the network bulit by the optimization mechanism.

Star Network

The optimization mechanism results in a star network, whenever \delta<(1/2)^{1/2}