In my last blog, I investigated the time taken for a giant component to develop in a social network.In that experiment, when the largest component contained the majority of people in the population, I stopped the simulation and recorded the time taken. If I were to continue the simulation, we’ll observe that the giant component eventually expands to include almost all nodes (persons) in the network. The size of the giant component thus converges to a constant over time as shown on the graph below for a virtual world of 1000 people:

In future experiments, I would like to extract statistics from the virtual world after this giant component has achieved equilibrium. I thus need a way to automatically detect when equilibrium is achieved in my virtual world. In this blog, I’ll explore how I implemented this, and I’ll also investigate the factors that affect the time taken to achieve equilibrium.

First, I need to clarify exactly what I mean by the term “equilibrium”. A social network is in equilibrium if the probability that the giant component grows is equal to the probability that the giant component shrinks. At the start of my simulation, due to the sparse nature of the network, the probability that the giant component grows is very high. As the simulation runs, the network gets saturated with friend connections and the probability decreases. At some point, the probability will decrease to 0.5, upon which we have reached the equilibrium point.

Now that I know exactly what I mean by equilibrium, I need to determine how I can detect it. Consider the graph above that shows the growth of the giant component. It is obvious that equilibrium has not been achieved in the first 300 days as the size of the giant component almost monotonically increases every day. The approximate plateau from day 400 onwards also indicates that the size of the giant component is stable, and thus the system is in equilibrium. We can thus estimate that the system is at equilibrium at day 400. Unfortunately, its is a bit harder to teach this visual recognition to a computer simulation. For the purpose of simplicity, I’ll assume that when the giant component is at equilibrium when it contains at least 90% of the population. I ran a few simulations to confirm the validity of my 90% heuristic.

After adding equilibrium detection to my simulation, I examined the relationship between the time taken to achieve equilibrium, and the average time taken to make a friend in the social network. The result of this simulation is shown in the graph below:

The relationship was linear. The time taken to achieve equilibrium is directly proportional to the average time taken to form friends. The constant of proportionality was 5.0.

Conclusions :

If E = time taken to achieve equilibrium, and T = the average time taken for a person to make a friend :

E = 5.0 T

Using the result used from my previous blog , we can also establish the relation between E and L (the length of time taken for the giant component to form) :

E = 2 L

This surprisingly simple relation says that the time taken for a system to achieve equilibrium is exactly twice as long as the time it takes to for the giant component to form. This result has some interesting implications. For example, consider a new instant messaging service. If this service measures the time it takes for a giant component to form within the network, it can accurately predict when the network will fully develop. This type of information can be exploited for strategic commercial planning.

My simulation source code can be found here (Visual C++ 2005).