Are you already "socially networked" with everyone you know?

Facebook and LinkedIn Network Connections

Both my Facebook and LinkedIn social networks have gone through periods of rapid grown in the past year. Although I have been a member of LinkedIn for many years, my network expanded rapidly last year, approximately doubling in a couple of months.  I have had a similar experience in the last few months with my Facebook network.

This is likely a convergence of factors.  My contemporaries are reconnecting with high-school and college acquaintances on Facebook.  More of the people I have worked with in the past have joined LinkedIn and started added colleagues from past employers.  This has led to a critical mass of people both connecting and inviting others to connect.

In each case, it seems that when enough people in my circle of acquaintances are connected, new connections form rapidly because it isn’t far (in terms of network hops) to other people I know.

So am I already "socially networked" with everyone I know? I think the answer is yes.  Because I am not very active at inviting new friends, it might be more accurate to say that I could be completely socially networked with an evening’s work.  In terms of network dynamics, this is because the network of my local group of friends has undergone the phase transition network mathematicians refer to as "percolation."

A simple model of network percolation

Where are without a model? Not very far on this blog. Instead of modeling a complete social network, let’s start with a simplified model and see if the behavior I want to describe pops out.

Here is a model that is easy to visualize. Imagine I am about to tile my kitchen floor. I draw a grid on the floor showing where each tile will be placed.  Looking at the kitchen floor as I prepare to lay the tile, you see a simple grid of lines, like graph paper. Now, start adding tiles. But instead of working from one side of the kitchen to the other in rows (like a normal person), I add tiles randomly.

I lay one tile by the sink, then two by the fridge, then another by the stairwell, a couple in the center.  The floor is getting cover red with tiles, but in a hodgepodge sprinkling.  Not too many of them are sitting right next to each other at first.  As I put down more and more tiles, however, there start to be little clusters of adjacent tiles. After a little while, the floor might look like this:

But then, along comes my nephew Hayden, wanting to go to the sink for a drink of water. I don’t want him to walk where there are no tiles, because he will track glue everywhere. But he is small, and can’t take steps bigger than one tile. So I need to hurry to put down enough tiles so he can walk to the sink.  But I don’t want to ruin my beautiful experiment with the random tiles.  How many tiles do I have to put down (still placing them at random locations) before Hayden can walk on adjacent tiles from the living room to the sink to get a drink?

When he can do this, the edges of the network of tiles are connected.  The network of tiles is said to have a percolating group of tiles.

A slightly more complex simple network percolation model

A mathematical description of the tile model goes like this.  Each tile (graph nodes or vertices) can have at most 4 edges connecting it to other tiles (graph edges or links).  The connections are created by placing adjacent tiles.

Let’s add a small generalization to the model to make it slightly more realistic. The tiles are connected by the fact that they are placed next to each other.  But in a social network, you can be "near" someone, but choose not to connect.  So let’s add the condition that each connection between adjacent people can be a friendship or not. And let’s allow this independently for each near neighbor. In the social network analogy, this means everyone person (node) can have at most 4 friendships (relationships, links to other nodes) but they don’t have to have be connected to someone they are "near."  Now people and friendships might look like this:

The analogous percolation question for a social network: how many friendships have to be created before you can get anywhere in the network by traversing friendships?  In other words, at what point is it possible to find everyone you know on a social network?

Further, regarding a period of rapid network growth: Is there some point in the evolution of the network when connections are created more rapidly?

To model this simple network, I created a simulation. You can download the Python script and run it yourself.  I created a grid 6 x 6, giving 36 nodes.  Central nodes can have at most 4 friends.  Edge nodes can have 3 and corner nodes only 2. For the entire network, the number of possible edges is 2 x 6 x 5 = 60.

One reason to use a computer model, is that since I am placing the friendships randomly, each time we run the model on a 6 x 6 network, the details will come out slightly different. So we want to understand what happens on average.  Using a computer model lets us run many (50 in this case) copies of the network experiment (without tiling a kitchen floor, and ripping it up over and over).

Instead of asking just about the path from the living room to the sink,  or one side of our generalized network to another, let’s look at the overall connectivity of the nodes. How close are we to being able to traverse the graph from any point to any other point? For this, we measure the size of the largest group of connected nodes (people) as we add more edges (friendships).

The size of the largest group of connected people looks like this as we add friendships between the people:

From the plot above, you can see that the size of the largest group gets large very fast after about 30 friendships form.  The network is fully connected after 40 friendships form–even though there are 60 friendships possible.

Okay, let’s close the loop on the analogy. If I had 36 high school friends on Facebook 3 months ago, they would have been difficult to find through each other.  But over time, a few of them talked on the phone, met on the street etc. and invited each other to friend them on Facebook.  This process was slow at first, but after about 30 friendships were formed, the process took off. One I was connected to a couple of sub-groups, I could find anyone I knew of my 36 high-school friends. Once the network percolates, I am socially networked with everyone I know.