How do you meet your friends? It turns out that if we know the answer, we may know a great deal about the structure of the entire friendship network and perhaps understand how other real-world networks evolve.
From friendship networks to the Internet, from electricity grids to biological networks, networks or graphs are common in the real-world. They are usually enormous, random and dynamic, making the study of their structure difficult.
However, it is still possible to examine certain features of those graphs and attempt to explain the features with random graph models. Quite a few random networks models were discovered to model those networks. We will explain the idea behind some of the most popular models within the context of friendship networks.
Erdős-Rényi models. Everyone is given a chance to meet everyone else and people become friends with each other in the process with some fixed probability. We also assume making a friend with someone does not affect the chance you become friends with someone else at all. Clearly the Erdős-Rényi model is quite naïve since making a friend with someone means we are more likely to be friends with their friends due to certain common interest.
Configuration models. Everyone is given a “friendship quota” that they must adhere to. They are paired up randomly until everyone’s quota is met. This model does not sound so intuitive yet it makes sense. The “friendship quota” mirrors the fact that some people are more social than the others and this quota can be fine-tuned to fit the real-world situation.
Preferential Attachment models. People joins the universe one at a time, connecting themselves into the existing friendship network. Here newcomers are more likely to make friends with the popular people (lots of existing friends) than the less popular ones. The intuition of the selection bias is that the popular people are more social and perhaps more charming, so it would be more likely that newcomers will become friends with them.
However, all of the above models are flawed. It turns out that as the number of people in the models grows, a random individual’s friends are rarely friends with each other. That is not the case in the real-world since a considerable proportion of our friends are friends with each other. Our research proposed a solution to this issue. Starting with any random network model, we add an additional round to let individuals meet with their friends-of-friends and make friends with them. It turns out this indeed fixes the issue and allows people’s friends to be friends with each other.
David Chen
The University of Melbourne
