Watts and Strogatz developed an influential network model that balances two of the properties seen in social networks. This model has high clustering: pairs of my friends are more likely to be friends themselves. It also has small diameter: the average distance between pairs of vertices is logarithmic in the size of the network.
This video analyzes a simplified version of the Watts-Strogatz model. We prove that average path length in this network is at most the square of the logarithm of the size of the network. We opt for this simplified result, which captures the spirit of the Watts-Strogatz model, rather than trying to prove the best possible bound.
![](https://i.ytimg.com/vi/Pnh6Kg4nYbE/mqdefault.jpg)