So this model sounds quite intuitive. But we still have to show the path discovered by greedy social search is going to exhibit small world. And what exactly does this mean? Well, without going into mathematical detail, suffice to say that the discoverable path length must grow very slowly as the number of nodes in the graph increases. So, as we have more of those leaf nodes in this case. that, the, the discoverable path length is, by the search process is going to have to grow very slowly. So as we increase the leaf nodes from eight to 16, to 32, to 1024 2048 so we're going from eight to 16, 32, you know 1024. Again, always in powers of two. And you know up to millions and millions of nodes. We're going to have to not see a very large increase in the shortest path link. So, we need to specify, or not the shortest, We're going to have to not see a very large increase in the, in the path links that can be discovered. Not necessarily the shortest path links, which is those that can be discovered. So we need to specify how the probability of nodes knowing each other decays with increasing levels of ancestry. And that's basically, you can show this mathematically, that the, the discoveral path length is going to be directly related to how that probability of notes knowing each other is going to decay with increasing ancestry. That should make intuitive sense, though. Because if you, you know, you're going to want to look, if you're given someone who's very far away, you're going to look at your levels of ancestry. And you're going to see, who the person, who, who the person you know in a level of ancestry is that could be close enough to that person that you would actually want to forward the letter to them, given that they're far away from you. So, it turns out that the probability must decrease by exactly one-half for this to happen. And so the optimal probability, it's a very crisp and concise result. That probability is going to have to decay by one-half as you go from one level to the next. So what does that mean? Well if we draw one of the structures here for the Watts-Dodds-Newman model suppose we have three levels of ancestry in the binary tree. Look something like this. And, in these, we have these leaf nodes down here. This case we have eight of them. Three, four, five, six, seven, eight. What we basically have to specify is how as we go up, the tree. So basically, how likely is it for a person in here to know a person in here. Okay. That's one. Then how likely is it for a person in here to know a person in here. That's second level of ancestry. Then how likely is it for a person in here to know someone on the totally other side of the tree, someone over here. So if we say that at the first level of ancestry that the probability of two nodes knowing each other who meet first at that level is x. Then we say that at the second level of ancestry, if the probability is declined by exactly one-half, it's going to be 'x' over '2'. Then at the third level, it would be 'x' over '2' divided by '2', which is 'x' over '4'. That has the sum actually to be one because probabilities have to add up to one and if you solve this out you get 'x' to be about .571 which means that the first level of ancestry has to have 57.1%. And in the second level's going to be about half of that, which is about 28.5% and at the third level you'd have about 14.3%. So what it's saying is that in order for us to have this property of the small world's property. And the probabilities, in order for us to have the small world property in the WDN model, probabilities have to decay by exactly 1/2. So if we had a three level structure. So we have three levels of ancestry here, the probabilities at the first level is going to have to be 57.1%. The probability of someone at, here, knowing someone in here is going to be 57.1%. Then, at the second level of ancestry, 25%, at the third level, 14.3%. And that's just an example to illustrate this. You can also do it for the case where you have 4 levels of ancestry. And in that case, he would have to be X plus X over two plus x over four plus X over eight, it has to be equal to one. Then you solve out for X again and you're going to get something a little different. And additionally you could see how the probabilities what they would have to be if we change the decay rate, but we always want the decay rate to be exactly one-half. And if it's not one-half, so if it's, for instance, if it's 60% saying it goes down by 60% as we go up from the level to the next. A much higher decay. Then the shortest path is going to grow very quickly. And we show that here in the example. And for this graph right here, we're, we're simulating the case of the WDN model where we have that every person, they're basically this 50 people per leaf. So in each of these boxes down here, there's 50 people. And additionally, every person is connected to 100 people on average. So, the degree, the degree on average [SOUND] is equal to 100. So what this implies is that every person knows 50 people in their leaf directly. So within a given leaf every person's going to, there's 50 people per leaf and everybody in the leaf is connected therefore that's where half of these people come from. The other half come from the longer range connection saying every person's also connected to 50 people outside of their leaf, right? So in different levels of ancestry. And those are two parameters we would need to specify in order to have this simulation, to get this graph. And we're plotting how it, how it changes as the number of people goes to 10 million, basically. This is time ten to the sixth. So, as the number of people goes to 10 million, how does this search path length change. Right, so. In the case of 50% we see it goes up very, very slowly. Right, so, it only goes up to about 1.5 here. This is 1.5. At 10 million people the search path length has only gone up to 1.5. The other hand, with 60%, it's gone up much har, higher to about 9.7, and even to 65%, so even a 5% increase above 60%, we're already going up to 41.6, which is way too large, right, because we need this to be, to remain relatively small as we increase the size of the network. So if this condition is met, we have both existence and discoverability of small world, right? Because as we saw here we can discover them with a search path length of about 1.5 even if they are not necessarily the optimal search paths in each case. Still, it suffices using greedy social search mechanism to do this. So in this numerical example as long as we keep the decrease at 50% we can guarantee that the greedy search length will exemplify small worlds for the Watts-Dodds-Newman model. And therefore we can conclude that Milgrim's observed six degrees of separation is indeed both discoverable and exists in realistic social networks. All right. So, this Watts-Dodds-Newman model is one way that people have shown both the existence and the discoverability, aspects of it. And there's other models as well and people propose different models also for different social scenarios too. This is just one example and again the key takeaway is just that it, under certain circumstances, if we have the conditions just right. In this case, being the probability being one half, then we can generate such a network and have such, a greedy social search mechanism, that can both explain and discover the small worlds using only local information. [SOUND]
