So we just discussed why we can't rely on increasing the number of links per node on the regular graph, to reduce the average shortest path length. So let's think practically here. We need a large clustering coefficient, and the regular graph provides that pretty nicely. At the same time, we need to have some wrong, long range links, that are going to be able to. Reduce stat distance between nodes on average. So, what if we add a few long range links between nodes on opposite ends of the graph? What would that do for us? Would that give us the properties that we need? So, this was the basic idea behind the Watts-Strogatz Model, which was first published in 1998. In the very reputable journal Nature. And you can definitely check out that original paper, if you'd like. So there's three parameters in the Watts-Strogatz Model. First is the number of nodes, just like we had with the regular graph. Second is the number of links per node, which is the same exact thing again as we had in regular graph. Which is the number of nearest neighbors each node has. And the third is prob, which is the probability. Which is the chance of connecting, a random pair of nodes in the graph. So, rather than connecting just to your, the neighbors that are nearest to you, it's the chance of connecting to a random pair of nodes for each link in the graph. So we repeat this process for each link in the graph, this whole coin flipping process that we said before of random notice establishment. And in this process that coin that we're flipping. I was going to have a probability equal to "prob", which could be like 10% of being heads and the rest of the times it's going to be tails. So 90% of the time tails and each time we flip it if it gets heads, then we connect to a random pair of nodes and if, if it's tails then we don't. So this is the basic idea here. We have the just the regular graph structure again. And then we're adding a few long range lengths. So, for instance if maybe we were going through this process for each link and maybe when we were considering this link here we did that coin flip and it turned out to be heads. So then we established some random long range link. And so we just took this node and then we chose some other random node in the network and we just connected. This node to that other node. So, that's the idea behind the Watts-Strogatz Model. So, now, suppose we have 32 links which is the case in this graph structure that you see here without the randomization. So, for each long range link, as we said, we may or may not establish a long range connection between two random notes. And higher probability the higher this value prob is, that means the more successes we're going to have. And therefore, the more of these long range random links we're going to be establishing. Note also that we're technically rewiring the links and what rewiring means, is that technically in the Watts-Strogatz Model, when we consider this node here, so we go through for each node and we do this whole coin flipping process if it turned out to be heads and we did establish a long range length, this one in this case, we would actually remove this node. And we or this link and rewire so we would say, okay, for this node rather than be connected here you're actually going to get connected up to this first node here. But that doesn't change the intuition behind how these long range links are established, it's really just a difference between saying that. This person would stay connected with this person in addition to having a long range friend. Where as, to say in the actual case, the Watts-Strogatz Model we would say that actually this person actually is not going to be connected to this close neighbor. Actually, going to have a long range connection to someone not in his near cluster vicinity.
