Six Degrees of Separation: Modeled
A quick script to explore the idea of Six Degrees of Separation.
Small-World: In the network that describes individuals (nodes) and their relationships (edges) to other individuals, there exists a path between any two nodes which is less than 6 edges long.
We simulate the problem by generating a random Barabasi-Albert graph for a varying number of nodes, and computing the average shortest path between any two nodes.
The Barabási–Albert (BA) model is an algorithm for generating random scale-free networks using a preferential attachment mechanism. Several natural and human-made systems, including the Internet, the world wide web, citation networks, and some social networks are thought to be approximately scale-free and certainly contain few nodes (called hubs) with unusually high degree as compared to the other nodes of the network.
We first choose a number of friends (edges) for each node and construct a random BA-graph with a particular number of nodes. We then find the average shortest path between any two nodes and repeat for a different number of nodes. The following is a chart obtained with 10 friends per node, for a population of 50 to 500 Nodes.
A logarithmic fit works best, and trial and error revealed that for our purposes 600 nodes was a reasonable sample size to extrapolate to 10⁹ nodes (we fit the curve from 100 nodes onward to bypass behavior around 0 nodes). An extrapolation of such a fit looks like:
We repeat the analysis above for a varying number of friends per node. For each run we fit a logarithmic function, extrapolate to 7 Billion, and record the DOS (degree of separation — previously referred to as: average shortest path) at that point. The following relationship was obtained:
It is clear that around 44 we are below the 6 DOS claim. The peak is around 50 friends where DOS is 5.5. So granted our (several) assumptions, the degree of separation should not exceed 5.5. However, there is something curious about the above chart, let’s examine it closer:
As one would expect, as the number of friends for each node goes to 0, the DOS blows up. Similarly as the number of friends increases beyond 50 the DOS decreases. But why does the DOS increase from 30 to 50? I have a hunch it has an intimate connection to the BA-model we used to construct the network.
More on this anomaly, and exploration of cases here the N (Number of people) >> F (number of Friends each individual has) assumption is not valid.
Note: This is a work in progress, any comments and insights are appreciated.
