EXPLORABLES

Knitworks

by Dirk Brockmann

This explorable illustrates network growth based on preferential attachment, a variant of the Barabasi-Albert model that was introduced to capture strong heterogeneities observed in many natural and technological networks. It has become a popular model for scale-free networks in nature.

Preferential attachment means that nodes that enter the network during a growth process preferentially connect to nodes with specific properties. In the original system, they preferentially connect to existing nodes that are already well connected, increasing their connectivity even further. This rich get richer effect generates networks in which a few nodes are very strongly connected and very many nodes poorly.

Press play and keep on reading...

This is how it works

Initially the system starts with a small network of only three nodes that are all connected to one another.

During the growth process, a new node comes in at every time step. The new node enters with \(q\) open links. \(q\) is a random integer between 1 and a maximum value that you can set with the corresponding slider. These open links are attached to randomly chosen target nodes in the existing network.

How are target nodes picked?

Initially, target nodes are picked completely at random, irrespective of their properties, corresponding to the neutral choice in the radio box.

Preferential attachment to high degree nodes

When instead of neutral you select degree, target nodes are picked preferentially according to their connectivity. To understand this we need to compute the nodes' degree \(k\), the number of links it has in the network. In the simulation the symbol-size of the nodes is proportional to the degree.

When degree is selected in the radio box, an incoming link attaches to a node \(n\) with a probability \(p _n\) that increases with the target node's degree like so:

\[ p _n \propto (1+k_n)^\xi \]

where \(\xi\geq 1\) is an exponent, that is also a slider parameter of the system. The larger this exponent, the more pronounced is the preferential choice towards high degree nodes.

Preferential attachment to low degree nodes

The third choice (inverse-degree) is somewhat the reverse. Incoming links are preferentially attached to nodes that only have a few links, whereas high-degree nodes are avoided.

Death

The network will not grow indefinitely. Once a specific size (slider) is reached, for every node that comes in, the oldest node in the network along with all its links is removed. The age of the nodes is encoded in grayscale from white (youngest) to black (oldest).

Observe this:

Reset the system and choose neutral attachment, increase the maximum incoming degree to its upper bound and press Play. After a transient an stringy network should emerge with a few isolated nodes and a large connected component.

Now switch to degree preferential attachment and increase the exponent to an intermediate or large value. Eventually the network should exhibit a few strongly connected nodes. The effect is more visible if you increase the maximum size of the network. The hubs will eventually die and release all their connected nodes and the process starts again.

References