# Scale-free networks

Complex systems can be depicted as networks. Therefore, network analysis is an important tool for the analysis of a complex system. There are different types of networks. In this article we elaborate somewhat further on so called scale-free networks. This is done in a relatively non-technical manner.

You should be aware that formal network analysis is a branch of mathematics, also using probability theory. For a general introduction to graph theory, see Chartrand and Zang (2004) and Lewinter and Buckley (2003).

If you want more detailed information about scale-free networks, you may like to look at Calderelli (2013). For a more general introduction to networks, see Easley and Kleinberg (2010).

## What does scale-free mean?

A network is called scale-free if the characteristics of the network are independent of the size of the network, i.e. the number of nodes. That means that when the network grows, the underlying structure remains the same.

^{See how the grown network still retains its underlying structure}

## The underlying structure

A scale-free network is defined by the distribution of the number of edges of the nodes following a so called power law distribution. The formula of such a distribution is as shown in the equation below:

power

Where

number of edges of a node

the probability of a node having k edges

constant positive number, often between 2 and 3.

The probability of a node having k edges decreases exponentially with increasing k.

## The normal distribution

A power law distribution is different from the so-called normal distribution. The latter is very common in real life.

The Central Limit Theorem provides an explanation for the fact that the normal distribution is found so often in many situations in practice, like for instance the distribution of body length among males or females in a given population. In a somewhat simplified way the Central Limit Theorem says that if we take any sequence of small independent random effects, then in their limit their sum or average will be approximated by the normal distribution (Easley and Kleinberg (2010), p. 480).

## Crucial difference between power-law and normal distributions

A crucial difference between the normal and power-law distribution is that the number of nodes with really high numbers of edges is much higher in the power-law distribution than in the normal distribution. But generally well connected nodes are more common in a normal distribution.

This means that in networks you will often find a small number of very highly connected nodes. They have a number of connections that would not occur if the distribution would be normal.

^{ An example of both a power-law distribution (left, yellow) and a normal distribution (middle, blue)}

## Why power-law distributions?

The normal distribution is less frequently observed in networks. This is the case because the distribution of edges in a network is mostly not the result of the sequence of independent quantities. Networks grow over time. Nodes that already have a high number of edges are more likely to see new edges to them established compared with nodes with a lower number of edges. That is the idea of so-called preferential attachment or the rich-get-richer principle (Easley and Kleinberg (2010), pp.482-486).

Preferential attachment looks like a plausible hypothesis for social networks in particular. It is attractive to be connected to people who are already highly connected. Think about celebrities, sporters and politicians in social networks.

### Small world principle

In large scale-free networks the small world principle may often hold. This principle says that any node is on average connected to any other node in a small number of steps, say around 5. The nodes with many connections act as a kind of hub between all the other nodes.

### Security

Large scale-free networks are not vulnerable to random attacks at nodes. They are vulnerable to targeted attacks at the few highly connected nodes. But the network will often not lose connectedness if one hub fails, due to the fact that other hubs remain. Connectedness means that any node is connected to any other node. You may imagine that the network structure is an important issue in thinking about cyber security.

### Stability

For the same reason you may imagine that the hubs play a crucial role in the stability of a network. For example, in the financial system supervisors try to identify and focus on so called systemically relevant financial institutions. These are the banks that are crucial for the stability of the financial system as a whole. If they fail many other financial institutions will fail too.

### Spreading information and contagion

The fact that in many real world networks a small number of highly connected hubs exist has important consequences for how, for example, information and diseases travel through the network. This is relevant to very different disciplines like epidemiology, public relations and marketing.

In next week’s activity on Agent Based Modeling you will see a marketing example where highly connected nodes have a very big impact on the acceptance of a consumer product. You can imagine that this is important to take into account as a marketeer.

© University of Groningen