The world is full of networks. We form social networks and infrastructure networks such as the electricity grid and transport networks. The internet is a network. There are also networks inside our bodies formed, for example, by the neurons in our brains.
These complex networks are not random, but a degree of randomness is involved in their formation. Some of your social contacts, for example, will be people you met by chance. The mathematical notion of a random network can help us understand them.
In maths, a network is simply a connection of nodes with links between some of them. In a random network these links are placed randomly. One way to generate such a random network is to start with a collection of unconnected nodes and think of some number p between 0 and 1. Take a pair of nodes and get a random number generator to give you a number between 0 and 1. If it's smaller than p, connect your pair of nodes by a link. Otherwise leave them unconnected. Repeat for every pair of nodes. If the number of nodes is large, then you will end up with a proportion of around p of pairs of nodes being connected. For example, if p=0.5 then around half the pairs are connected. If p=0 no pairs are connected. And if p=1 all pairs are connected.
You can generate your own random network using the interactivity below, created by Oscar Gillespie using the Cytoscape.js library. Enter your preferred value for p in the box in the top left and click create. The left-hand figure shows you what your network looks like when the nodes are arranged in a circle. The right-hand figure uses force-directed drawing to find a lay-out that's aesthetically pleasing.
Every random network you generate in this way for a fixed p is likely to look different, but you can use probability theory to make all sorts of general statements about random networks. For example, you can work out the expected number $L$ of links in the network. It's
$$L=p\frac{N(N-1)}{2},$$ where $N$ is the number of nodes.
Understanding the general properties of random networks is an interesting mathematical question in its own right. A lot of important work on them was done by the mathematicians Paul Erdős and Alfréd Rényi. You can find out more in this interesting chapter of the book Network science by Albert-László Barabási himself an expert in the field.
Although real-life networks are rarely totally random, random networks are still useful. One property random networks share with many real-life networks is what is popularly known as six degrees of separation — the idea that the average number of links you need to traverse to get from one node to another is surprisingly small. This means that you're probably only a few steps away, in terms of acquaintance links, from Taylor Swift.
More generally, comparing a real-life network with a random one and spotting the differences can give you a good idea of the processes that lead to the formation of the real-life network that are not random.
Most importantly, though, random networks are fun to play with and think about and they can be pretty!
This content forms part of our collaboration with the Isaac Newton Institute for Mathematical Sciences (INI) – you can find all the content from the collaboration here.
The INI is an international research centre and our neighbour here on the University of Cambridge's maths campus. It attracts leading mathematical scientists from all over the world, and is open to all. Visit www.newton.ac.uk to find out more.
