Scale Free Network

• A scale free network is a network whose degree distribution follows a power law. The term scale-free comes from how power laws are scale invariant
• Most models under Preferential Attachment can generate scale-free networks
• We have several Models for Scale Free Networks

Properties §

Large Hubs §

• In a large scale-free network, the biggest hubs are orders of magnitude larger than the smallest nodes in the networks.

• Let us use the natural cutoff of the continuous power law distribution of a scale-free network.

  We have the following distribution

  Let us assume that in a network of nodes, we expect at most one node that has degree bigger than .

  We, therefore, have that

  Or expanding the integral

  Which, when evaluated gives

  This implies that has a polynomial dependence on , so large scale-free networks have disproportionately large hubs.

Low Attack Tolerance §

• For scale free networks , there is a phase transition at an incredibly low value for targeted attacks. This is because hubs play an important role in keeping the network connected.

  It only takes the removal of a few hubs for the network to fragment.

• Within a network, the removal of a single node is unlikely to fragment the network However, targeted attacks can disconnect the network and cause it to break down into tiny clusters.

• The robustness of scale free networks , combined with the modifications of an attack on a scale free network give us that the breakdown thresholds for attacks on a scale-free network is the solution to this

• We can make the following observations

  • increases for small degree exponents and decreases for large degree exponents.
  • for attacks is always smaller than that for random failures.
  • For large , the scale free network behaves like a random network under attack. At large , the attack and failure thresholds converge to each other and they become indistinguishable.

Thresholds §

• The degree exponent introduces a threshold on the scale-free network. in particular on the average distance

  We have that

• We may see that the scale-free property has the following characteristics.

  • Smaller average path lengths since hubs act as bridges between many nodes.
  • Networks become ultra-small. The smaller the degree exponent , the shorter the distances between the nodes.
  • If , the scale-free network now exhibits the same properties as a small-world network.
  • If , the giant component emerges (see here).

Anomalous Region §

• By the calculations here, we find that when ,
• This region is anomalous, because the average degree diverges as . But also, the largest hub must connect to more nodes than there are links in the network.
• Thus, large scale-free networks with that lack multiple edges cannot exist.

Ultra-Small World §

• This region is characterized by being Ultra small since grows much slower than .

• This is indicative of the fact that hubs significantly reduce the distance between any two nodes.

• In this case, , where so the proportion of nodes connected to the largest hub decreases as

Critical Point §

• At , we encounter a critical point where the dependence to returns, yet this is corrected by the presence of . This means, that it is on the verge of displaying the small world property

Small World §

• Here, we find the network satisfies the small network property.
• While hubs remain, they are not sufficiently large or numerous to have a significant impact on the distance between nodes.
• For all intents and purposes, the properties of a scale-free network here are hard to distinguish from that of a small-world network. In theory, however, we can achieve this by having
  In practice, no real network is that big.

Percolation §

• The critical exponents of a scale-free network are determined as follows.

• The average cluster size near follows

  This emerges due to the Average distance thresholds.

• The order parameter critical exponent is given by

  • In a scale-free network, the giant component collapses faster around than a random network.

• The average size off the finite components is given by

v &= \begin{cases} \frac{\gamma-3}{\gamma - 2} & 3 <\gamma < 4 \ \frac{3-\gamma}{\gamma -2} & 2 < \gamma < 3 \ \end{cases} \end{split} \end{equation}