Deterministic scale-free network

A scale-free network is a type of networks that is of particular interest of network science. It is characterized by its degree distribution following a power law. While the most widely known generative models for scale-free networks are stochastic, such as the Barabási–Albert model or the Fitness model can reproduce many properties of real-life networks by assuming preferential attachment and incremental growth, the understanding of deterministic scale-free networks leads to valuable, analytical results.

Concept

Although there are multiple deterministic models to generate scale-free networks, it is common, that they define a simple algorithm of adding nodes, which is then iteratively repeated and thus leads to a complex network. As these models are deterministic, it is possible to get analytic results about the degree distribution, clustering coefficient, average shortest path length, random walk centrality and other relevant network metrics.

Deterministic models are especially useful to explain empirically observed phenomena and demonstrate the existence of networks with certain properties. For example, the Barabási-Albert model predicts a decreasing average clustering coefficient as the number of nodes increases, whereas empirical evidence suggests otherwise. Hierarchical network models can explain this phenomenon while also retaining the scale-free property. Another notable example is that it is possible to generate networks deterministically, which are scale-free and linear world at the same time, showing that small-world property is not a necessary consequence of the scale-free property.

Properties

The exact properties of the generated networks depend on the particular algorithm with which they are constructed, therefore there are not many common properties. The single unifying property is scale-freeness, that is, the degree distribution of the nodes always follows a power law at least asymptotically, which means that a randomly selected node has k edges with probability

$P(k)=ck^{-\lambda }$

where the degree coefficient (λ) depends on the model parameters.

Also, because of the iterative construction, many of the models produce hierarchical networks with fractal-like properties. Other properties, such as network diameter, average path length, clustering coefficient vary across models depending on the construction.

Examples

Barabási-Ravasz-Vicsek model

One of the first deterministic scale-free network models was proposed by Barabási, Ravasz and Vicsek. It involved the generation of a hierarchical, scale-free network by following a set of simple steps:

Step 0: We start from a single node, that we designate as the root of the graph.

Step 1: We add two more nodes, and connect each of them to the root.

Step 2: We add two units of three nodes, each unit identical to the network created in the previous iteration (step 1), and we connect each of the bottom nodes [...] of these two units to the root. That is, the root will gain four more new links.

Step 3: We add two units of nine nodes each, identical to the units generated in the previous iteration, and connect all eight bottom nodes of the two new units to the root.

[...]

Step n: Add two units of 3n−1 nodes each, identical to the network created in the previous iteration (step n−1), and connect each of the 2n bottom nodes of these two units to the root of the network.

It has been analytically shown, that the degree distribution of this network asymptotically follows a power law with a degree exponent of ln(3)/ln(2). Iguchi and Yamada has shown that most of the important network statistics can be derived analytically in this model.

Lu-Su-Guo model

This model based on a binary tree exhibits both the scale-free property and the ultra small-world property (the average shorthest path increases more slowly than the logarithm of the number of nodes) for an arbitrary number of nodes.

Zhu-Yin-Zhao-Chai model

The authors propose two models which exhibit the power law in the degree distribution while the average shortest path grows linearly with the number of nodes. This proves that not every scale-free network has the small-world property. One of their models shows that this can also be true in the absence of degree correlation.