Low-degree saturation

In a scale-free network the degree distribution follows a power law function. In some empirical examples this power-law fits the degree distribution well only in the high degree region, however for small degree nodes the empirical degree-distribution deviates from it. See for example the network of scientific citations. This deviation of the observed degree-distribution from the theoretical prediction at the low-degree region is often referred as low-degree saturation.

Typically the empirical degree-distribution deviates downwards from the power-law function fitted on higher order nodes, which means low-degree nodes are less frequent in real data than what is predicted by the Barabási–Albert model.

Theoretical foundation

One of the key assumptions of the BA model is preferential attachment. It states, the probability of acquiring a new link from a new entrant node is proportional to the degree of each node. In other words, every new entrant favors to connect to higher-degree nodes. Formally:

[math]\displaystyle{ \Pi\left(k_i\right)=\frac{k_i}{\sum_j k_j} }[/math]

Where [math]\displaystyle{ \Pi\left(k_i\right) }[/math] is the probability of acquiring a link by a node with degree [math]\displaystyle{ k }[/math].

With a slight modification of this rule low-degree saturation can be predicted easily, by adding a term called initial attractiveness ([math]\displaystyle{ A }[/math]). This was first introduced by Dorogovtsev, Mendes and Samukhin in 2000.

[math]\displaystyle{ \Pi\left(k_i\right)=\frac{A + k_i}{A +\sum\limits_{j} k_j} }[/math]

With this modified attachment rule a low-degree node (with low [math]\displaystyle{ k }[/math]) has a higher probability to acquire new links compared to the original set-up. Thus it is more attractive. Therefore, this handicap makes less likely the existence of small degree-nodes as it is observed in real data. More formally this modifies the degree distribution as:

[math]\displaystyle{ p_k = C\left(k + A \right)^{-\gamma} }[/math]

As a side effect it also increases the exponent relative to the original BA model.

It is called initial attractiveness because in the BA framework every node grows in degree by time. And as [math]\displaystyle{ k }[/math] goes large the significance of this fixed additive term [math]\displaystyle{ (A) }[/math] diminishes.

Significance

All the distinctive features of scale-free networks are due to the existence of extremely high degree nodes, often referred as hubs. The existence of these hubs are predicted by the power-law distribution of the degrees. However low-degree saturation is a deviation from this theoretical degree distribution, since it characterize the low end of the degree distribution, it does not deny the existence of hubs. Therefore, a scale-free network with low-degree saturation can produce all the following characteristics: small-world characteristic, robustness, low attack tolerance, spreading behavior.

If it is modeled via the BA model augmented by the initial attractiveness, then this solution reduces the size of hubs because it affects the exponent of the degree distribution positively relative to the original BA model.

See also

Initial attractiveness