Social Network Models
Veritasium Video: The Science of Six Degrees of Separation
Watts & Strogatz Study: Collective Dynamics of ‘Small-World’ Networks
Facebook Study: Three and a Half Degrees of Separation
Four years ago, I stumbled upon a video on the Six Degrees of Separation. The video discusses both Stanley Milgram’s 1960’s study and Facebook’s 2011 study (A more recent 2016 study is linked to above). I found these ideas extremely fascinating and wanted to pursue them on my own. I went on to learn a lot more while conducting a research project in high school. Here, I want to share what I learned about network models and, in particular, social network models.
We have learned about a few measures that can be computed on networks; each indicates some property the network has. One technique used to analyze networks is to compare the real-world values of these measures to the expected values in a randomly generated network. For example, in lecture, we learned about the clustering coefficient. In social networks, we find that the average clustering coefficient is much higher than the expected value in a random graph. This indicates that two people are more likely to be friends if they have a mutual friend. Alternatively, suppose we analyzed a network and found the average clustering coefficient to be lower than expected on a random graph. This would indicate two nodes sharing a common neighbor are less likely to be connected. In what types of networks would this characteristic make sense?
EDIT: The High School Dating Network on the class homepage is a good example of a network with this property!
Now, let us consider some real-world network we would like to research. We would like to develop a better understanding of this network’s underlying structure so that we can make better predictions about how this network will behave in the future. For example, consider contagion in social networks. Our understanding of social networks’ structures allows us to predict how information, disease, etc. will spread through them. One tool used to understand the structure of networks is a network model. A network model is an algorithmic way of generating a network. The expected values of measures such as the clustering coefficient can be computed mathematically based on the inputs to the model. Researchers can create network models which possess the same properties as the real-world networks they are studying. These models can then be used to make predictions about the behavior of the real-world network.
Lastly, let us consider a social network model. Cornell’s Steven Strogatz and Duncan Watts created the Watts-Strogatz Model to do just this. Their model captures the high clustering and small shortest path lengths seen in social networks. Simply stated, the model is constructed as follows. Take n nodes and put them in a ring. Connect each node to the k/2 nodes on either side so that each node has k neighbors. Lastly, each edge has a probability p in [0,1] of being rewired. If it is rewired, randomly select two nodes (preventing self-loops and duplicate edges) and connect them. Strogatz and Watts coined the term ‘small-world’ networks to describe the networks between the p=0 and p=1 extremes of their model. If p=0, the network has high clustering and if p=1, the network is completely random and has small shortest path lengths.
In conducting my research, I developed a program to create graphs and maintain a few graph measures. Below, this program shows an example of the Watts-Strogatz Model for n = 19, k = 4, and p = 0.25. Of 38 edges, 10 were rewired. You can see that the clustering in the graph was relatively unaffected by rewiring yet the average degree of separation (average geodesic) drops 26% from 2.78 to 2.06.
In my research, I attempted to create a social network model (I was unaware of the Watts-Strogatz Model at the time). Most of my research was spent developing a formula to derive the average degree of separation directly from the inputs to my model. Fortunately, I had the pleasure of sharing my research with Steven Strogatz when I arrived at Cornell. Unfortunately, I discovered the network model I developed was not a ‘small-world’ network.
My Paper: The Degrees of Separation: A Predictive Network Model Equation
This is very nice!