EXPLORABLES

The Blob

by Dirk Brockmann

This explorable illustrates an important feature of complex networks: the emergence of the giant component. Networks often have multiple components. A component is a part of the network where we can find a path between any two nodes by traversing links. Two different components, however, are disconnected. When the number of links in the network is too small, the network will consist of many little components. Only when the number of links is sufficiently large, the network will have a single component. The transition from one scenario to the other can be explored here and the emergence of a giant component at the transition point can be witnessed.

This is how it works

First, we need a bit of network vocabulary. We have a network with \(N\) nodes and \(L\) links, the overall connectivity can be quantified by the link density \(\rho\): the number of links devided by the maximum number of links (\(L_\text{max}=N(N-1)/2\)):

\[\rho=2L/(N(N-1)).\]

The degree \(k\) of a node is the number of its links to neighbors. The mean degree is related to the density by

\[\left < k \right > = \rho(N-1) = 2L/N.\]

The main slider controls the mean degree of the displayed network, proportional to its overall connectivity.

The size of the component is just the number of nodes in it. The largest component is illustrated in orange, the second largest component in red. As a guide for the component structure the plot in the control panel depicts the components as circles with sizes proportional to the corrensponding component sizes.

You have two choices of networks, the Erdős–Rényi (ER) and Barabási–Albert (BA) network. Both networks are random networks, generated by a random process. You can generate different realization pressing the new network button.

The ER-network is characterized by a fairly homogeneous connectivity structure in which nodes have more or less the same number of neighbors. In contrast, the BA-network is characterized by a strong node heterogeneity, i.e. few nodes with many connections and many nodes with few connections.

Observe this

If you turn the slider all the way to the left, the network is completely disconnected. As you increase the mean degree slowly, more and more components will form and around \(\left < k \right >\approx 1\) for the ER-network you will see that one component starts dominating and form the giant component.

Do this again and observe what happens to the second largest component. Initially, its size will increase, like all other components. But at the critical point the size of the second largest component will decrease again, because the largest component starts swallowing whatever component is the second largest repetitively.

ER vs. BA

If you compare the nature of the transition for both network types you will see that for identical mean degree, a giant component emerges earlier in the BA network and the transition point is more difficult to identify. In fact, one can show that the BA-network, in the limit of large network size (\(N\rightarrow \infty\)) will not have a transition point at all but exhibit a giant component even for very low connectivity.