This explorable illustrates how strong heterogeneities, cluster-like structures and high variability in node connectivities can naturally emerge in growing networks. The mechanism explored here is very simple: When a new node is added to the network it picks another target node at random. Instead of linking to it, the new node establishes a link to one of the target’s neighbors.

This model was originally introduced and analyzed by Pavel Krapivsky and Sid Redner in 2017 and is discussed in the paper “Emergent network modularity” (see References below). The effects that are at work in this model are driven by the peculiar property of networks that a node’s average degree (i.e. its number of links) is always smaller than or equal to the average of the nodes’ neighbors’ degree, also discussed in Complexity Explorable “Facebooked Flu Shots”.

Press Play and keep on reading….

This is how it works

The system is initialized with a small, fully connected network with $N=5$ nodes. When you press play, new nodes are added to the network until a maximum number $N=300$ is reached and the simulation stops. (You can always reset the system with the small button with the arrow pointing left).

The important parameter here is controlled by the slider on the bottom, the neighbor attachment probability $Q$. When a new node is added to the network, it first picks a target node. With probability $1-Q$ the incoming node links to this target node. With probability $Q$ it links to one of the target’s neighbors instead. So, when $Q=0$ incoming nodes always link to their target node. When $Q=1$ they always connect to one of the target’s neighbors. The default setting is such that attaching to a neighbor is more likely.

You can also choose with how many links a new node enters the network, i) either only $1$, ii) $1$ or $2$ with equal chance, or iii) always $2$.

Ordinary networks

Let’s first look at the boring system. Turn $Q$ to zero with the slider, select $1$ for the number of incoming links and press play. After the network is done growing to its final size, you should see a tree like structure in which the nodes have a typical degree, usually not more than 3 or 4.

The funny bubble plot that appears in the control panel when the simulation is done, illustrates the degree heterogeneity. Each bubble corresponds to a node in the network, the size is proportional to the degree. When $Q=0$ the bubbles have approximately the same size.

Seeking a friend’s friend….

Now reset the system (button with an arrow to the left) and turn the bottom slider (“neighbor attachment probability”) all the way to the right. As outlined above, when a new node comes in, it choses a node in the existing network at random (say node A), but it connects to one of A’s neighbors instead. When formulated like this, it seems the algorithm should not yield networks with different structure because, after all, why should picking a random node be different than picking a random neighbor?

When you press play, you should see that this intuition isn’t right, the emergent network looks quite different. Gradually hubs emerge, nodes with very high connectivity. When the network is finished growing, you can see how heterogeneous the network is, in the degree bubble plots on the top right.

This funky effect is driven by a general network property: The expected degree of a node’s neighbor is higher than (or equal to) the expected degree of a node, a property also discussed in Complexity Explorable “Facebooked Flu Shots”. So when a new node picks a target node A and then one of its neighbors this neighbor will be picked more likely if its degree is slightly larger than that of other nodes. If the new node comes in and links to the neighbor, the neighbor’s degree increases even further, making it more likely again to be picked as a neighbor of some other node when the next node comes in.

References

P. L. Krapivsky and S. Redner. Emergent network modularity. J. Stat. Mech. 2017 (2017)

* Acknowledgements

This explorable was inspired by a discussion with Sid Redner when I was a guest at the Santa Fe Institute in July 2019. I want to thank Jenna Marshall for hosting me and the Santa Fe Institute as a whole for providing such a great and inspiring environment.