The Social Network (Part 1)

If you make sure you're connected, the writing's on the wall

With the ongoing turmoil around Twitter, I’ve been thinking more about how (social) networks form — and how they fall apart. This will be a two-part piece, with the second instalment to come on Thursday. Today I will explain what an amphetamine-addicted Hungarian (and his equally brilliant co-author) taught us about networks.

Representing the network

As usual, we need some kind of mathematical language and model to represent the real-world things that we care about. The key object here is what mathematicians call a graph. This terminology can be a bit confusing because most of us use the word “graph” for a plot with two axes and some points scattered on it, so I’m going to call it a network instead (I do exactly the same in Numbercrunch).

You can think of a network based on a collection of dots, which we will call vertices. These correspond to individuals - for example you could think about a school class of 30 children, and draw a dot to represent each child.

Now, we might want to capture the fact that some children are friends with one another, and others aren’t. We can consider each pair of children, and if they are friends with one another, we can draw a line (which we call an edge) between their vertices. So if Annie and Bill are friends there will be a edge linking them in our network, but if Bill and Clare aren’t friends there will be no edge. With six children, labelled 1 to 6, you might see something like this:

(Picture taken from Wikipedia: User:Chmod007 Public domain, via Wikimedia Commons)

Understanding the network

It may look like a bit of a mess for a big class, but in theory we could draw the network and use the resulting picture to understand the friendship structure. For example, you might find small cliques of say four or five children, all of whom are friends with one another. It might be that boys tend to be friends with other boys but not so much with girls. Perhaps there is a sporty group, a nerdy group and a fashionable group, all of whom like to hang out with people like themselves but are less keen on people from outside their community.

There are mathematical tricks and ideas which allow us to discover these kinds of structures within a complicated network. The network records the relationships within the class, and by studying it (and perhaps even observing how it changes over time) we can start to understand the class’s social interactions.

One thing we might care about is the size of the biggest connected component of the network: that is, the largest group of vertices that are joined together by edges in some way. They aren’t all necessarily directly connected to one another, but there should be a chain of friendships. If Amy is friends with Bella, Bella is friends with Chris, and Chris is friends with Dave, then they would all be in the same component.

Having a large connected component is a sign of health for a social media network: it means that ideas and memes can percolate within it, and people shouldn’t be isolated or in echo chambers. Indeed many of Twitter’s algorithmic tricks are designed to break people out of silos: by recommending people to follow or new posts in the For You view, Twitter tries to create new connections to build more links within its network to ensure a persistent spread of ideas.

Building the network

Now we know how to draw a network, we can start to try to understand whether what we see is unusual or not. One way to do that is to think about forming a network at random, and what we might expect to see if we did.

It’s not necessarily very obvious what it means to create a network at random, and indeed there are many ways to do it. I’ll describe a more interesting way in Part 2, but for now I’ll describe what is called the Erdős–Rényi model, named after the two Hungarian mathematicians who developed it in the late 1950s.

(As an aside, Paul Erdős has been the focus of a huge amount of popular attention, not least because of his extreme and somewhat unhealthy lifestyle. He travelled the world with few possessions, working obsessively on mathematical problems before moving on to his next destination, fuelled by a prodigious caffeine and amphetamine habit, and never settling down with a partner or children. This clearly worked for him personally, and made him the most prolific mathematician of all-time, but I’d hate it if people thought this was typical or necessary behaviour. Most mathematicians aren’t like that, and you don’t have to lead a life of monkish devotion to the subject in order to succeed. Indeed, before his untimely death Erdős’s co-author Alfréd Rényi made huge contributions in many areas of maths, while also leading a life full of culture and physical activity with his family.)

Anyway, the Erdős–Rényi model is very simple, and can be described in terms of two numbers, n and p. The n represents the number of vertices in the network - so in our school example, n would be 30. The p is a probability (a number between 0 and 1), and tells us how well-connected our network will be.

The rule to create the network is very simple. We consider each pair of vertices, and draw an edge between them with probability p. Whether or not there is an edge for any pair is completely independent of all the other edges (so if p was 1/6 for example, you could think of rolling a standard die for each pair of vertices, and drawing in an edge if you roll a six).

Flip the switch

It should be clear that the bigger p is, the more edges there will tend to be, and so the network will be better connected. But what is surprising is the way that this happens: essentially as you increase p, the network suddenly flips from being not very connected at all to being extremely highly connected.

Mathematicians and physicists call this as a phase transition. Think about varying the temperature of water: at -1°C it will be solid ice, at 1°C it will be liquid water. If you can control the temperature precisely enough, even at -0.1°C or -0.01°C you will have ice, and at 0.1°C or 0.01°C you will have liquid. While you can argue what you might see at exactly 0°C, it’s clear that tiny changes in temperature that move you to the opposite side of this critical freezing point will cause big changes in behaviour.

We see something similar for the random Erdős–Rényi network. It turns out that the quantity which acts like the temperature is “n times p” (or np for short), and the equivalent of the freezing point is the number 1. This kind of makes sense, because np is roughly the number of other vertices that each vertex will be linked to - if you buy (n-1) lottery tickets each with a chance p of winning, you expect to win about “(n-1) times p” prizes.

But at a network level, Erdős and Rényi together proved that the change in behaviour is very dramatic:

1. If np is less than 1 (even a little bit less, say 0.99), then the network will tend to be formed of a collection of clumps that don’t mix well together. To be precise, the size of the largest connected component will be about the logarithm of n, which is a tiny fraction of the whole collection of vertices.

2. If np is bigger than 1 (even a little bit bigger, say 1.01), then the network will tend to have what’s called a giant component, meaning that a fixed fraction of the network will be joined together.

The social network

What all this means is that there is a critical level of interaction, above and below which social networks will tend to significantly gain or lose functionality.

This phase transition, and others like it which crop up in similar models, means that when building a network there can be a particular level of connectivity at which good things start to happen. All of a sudden, the network stops being a group of silos and becomes well-connected. Retweets can allow messages and ideas to flow across it, permitting rich and interesting interactions. We’ve moved to the good side of the phase transition and the ice has melted.

If you are running a social network, this is exactly what you want to happen, to see high connectivity allowing the free flow of ideas. However, there’s a cautionary message here as well, in that the same thing can happen in reverse.

Given a once-healthy network, if enough edges are removed then its utility can fall apart in an equally dramatic way. It may not be obvious at what point this happens, but in theory it can be a very drastic change - there can suddenly no longer be enough edges for ideas to flow properly, and the network can decompose into disconnected groups of people only talking at each other. A small change has taken us to the bad side of the phase transition, and things have frozen up again.

This may or may not be a useful model for what might happen with Twitter, not least because the Erdős–Rényi model is not a particularly realistic way to describe real social interactions. I’ll come back to this in Part 2, and describe more interesting models which might tell us more about the real world. But for now, understanding this language of networks, vertices, edges and phase transitions starts to give us a mathematical feel for the mechanics of social networks, and how they form and fall apart.

Note: because of the kind of network effects I have described, there is great power in you passing on this article. So if you found it interesting, please share it and if you aren’t already subscribing then please do - this will make sure that you receive Part 2 later in the week.