Deterministic scale-free network

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

${\displaystyle 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.

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.

^[4]

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.^[5]

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

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.^[3]