How network math can help you make friends quanta magazine

Imagine you are one of 10 people in Randomville. How many possible friendships are there? Each of the 10 people could be connected to the other nine, so it seems like you could potentially draw 10 × 9 = 90 edges. But this actually counts each possible friendship twice: Once for each friend. So the total number of possible friendships is really 90 divided by 2, or 45.

Now let’s say we randomly choose a friendship, that is, we randomly select one of the 45 possible edges in our network. What’s the probability it connects to you? Well, there are nine possible edges extending from you to each of the other nine nodes. Since nine of the 45 edges connect to you, the probability that a randomly selected edge will connect to you is $latex \frac {9}{45}$ = $latex \frac {1}{5}$, or 20 percent.

But this same argument applies to everyone in Randomville, so every node has a 20 percent chance of being connected to the randomly selected edge. Now, as edges (and nodes) are added, these probabilities will change slightly, but in the long run they will remain roughly the same. This means that friendships will be pretty evenly distributed around Randomville. There will be some slight variation here and there, but having very few friends, or very many friends, will be unlikely. In Randomville, almost everyone is likely to end up with something close to an average number of friends.

By looking only at the degree distribution of this network, we can infer a particular kind of uniformity: When it comes to connectivity, most nodes are average and very few are extreme. This is useful information when it comes to understanding the structure of the network. (As nodes are added, say, when new people come to town, the distribution will change slightly, but the general features will persist.)

Now, neither of these two examples — the at-most-four-friends rule of Regulartown or the randomly selected friendships of Randomville — are realistic models of friendship. People can have more than four friends, and having a lot of friends isn’t as unusual as the binomial distribution suggests. So what is a more realistic model of friendship?

As you build connections with friends and friends of friends, the structure of your friendships will likely share features common to other real-world networks like food webs, protein interactions and the internet. These features characterize so-called “scale-free” networks, a model of connectivity that has come to dominate network science over the past 20 years. Researchers from mathematics, physics, economics, biology and the social sciences have all seen the telltale signs of scale-free networks in their disparate fields.

The structure of scale-free networks depends on the simple principle of “preferential attachment.” Preferential attachment is a rich-get-richer rule of network growth: A node with many existing connections is more likely to get new connections than a node with few existing connections. New connections show a preference for high-degree nodes.

Does this make sense in the context of friendship formation? Generally speaking, it seems reasonable to argue that someone with many friends will be more likely to make new ones. Since they are already connected to more people, they are more likely to meet new people through those existing connections. Having more friends creates more opportunities to make new friends. And the fact that they already have a lot of friends suggests they may have some kind of capacity or affinity for making friends. This will likely draw others to them, just as popular websites draw links from other sites and blogs, and established cities invite new rail lines and air routes.

These nodes of high degree, which act like hubs, are a critical feature of scale-free networks. They are the social butterflies of friendship networks, the banks at the center of economies, the centralized routers that regional internet lines run through, the Kevin Bacons of the acting world. Hubs can bring a small-world feel to an enormous network — for example, any two randomly selected users from the two billion people on Facebook are less than four friends apart on average. And the number and diversity of hubs also gives scale-free networks resilience against certain kinds of breakdowns: For example, even if many internet connections fail, messages can still get through, partly because there will still be many ways to get to and from the many hubs.

While there seems to be agreement on the utility of scale-free networks and their high-level features, this area of study is not without controversy. The precise mathematical characteristics of these degree distributions can be difficult to interpret. In his book Linked: The New Science of Networks, the network science pioneer and physicist Albert-László Barabási argued that networks exhibiting preferential attachment will have degree distributions that essentially follow a “power law.” Power law distributions are seen in many physical situations, like the inverse square laws of gravitation and electric fields. They can be represented as functions of the form $latex f(x)=\frac {a}{x^k}$, and their graphs typically look like this: