Now we have answered the first question about a structural small world. And answering this question as we just saw, leads to a deeper question and indeed a more surprising observation out of the Milgram experiment in the late sixties, and that is the algorithmic. Small world. One model by Kleinberg, two years after the Watts Strogatz model, can be described briefly as follows and then we have homer problem to go into further detail about that. So now we would like to find out the quantity little l, which is the length of the greedy search path in a social network and we want this number to be small and also grow slowly as a function of number of lengths. Just like a big L. In Kleinberg's model he says that, true we will have longer path but the longer the path is, the less likely it will be established. That is the starting point of Plan Berth model to explain how these small little hours. Well how less likely, let's say, if the distance is denoted by R which could be the physical distance or some composite matric of social and physical distance. Then the probability that such a long length exists is R to the minus alpha. So alpha is some parameter. That controls the rate of decay of the likelihood of the longer path. And then it turns out that Kleinberg showed if this rate of decay, alpha, is exactly equal to the dimension of the space, for example, inth, our word, 3-dimension. Hm. In a word of say, a grid, a two dimension, in a word of a line, or a circle, one dimension. Then if alpha is three, or two, or one, in these three different cases, on in general as long as alpha is exactly, you go to the dimension of the space in which the network re size, then algorithmic small world will hold, and this little L will be small and grows slowly as a function again. So why is that? Again the proofs are in the homework and we'll go through a similar model in just a minute. But intuitively what's going on is the following. That if you look at say 2-dimensional space, or in general r, k dimensional space. U2018kay? Then you look at ball or radius r, then you look at another ball of radius 2r. And then you look at how many more people will live in this space, okay. The probability of having the linked one of these nodes will drop as R to the minus K and yet the number of node living in the space, assuming some evenly distributed node location, will be proportional to R to the positive K. So, as you go farther out, there are more people that you might know, even though the chance that you know any one of them is smaller. And it turns out, if these two growth and decay rates cancel each other out. Then, you pretty much have a constant chance of number of people you will know as the space, space grows. And that turns out to be the key idea. The number of people going up compensates for the smaller chance of knowing any, any individual as the social circle expands. And that's what's underlying this resout. Now, you may say this resout is a little too brittle. Because we need alpha to be exactly = to the space number of dimensions, K. It can be a little bigger than that. To say, K + 0.001. You cannot be K- 00.1. And part of this brittle nature of the result is due to the fact, how we define algorithmics more world. We want L to grow as, Log or, and most a polynomial of a log function. Okay. And part of the reason is because the way we construct the likelihood of longer path. In advanced material part of the lecture video we will talk about yet another alternative model to explain algorithmic's will work without this brittle nature. But before then, we will first talk about a variant of Kleinberg model, called Watts Dodds Newman model, Actually. This is an extension of the Kleinberg model. And this is a model that trying to explain how rhythmic small world whereas Watts-Strogatz. Model try to explain the structure of small worlds. In the Watts Dodds Newman Model, you have the following character of human society of the social network. You've got people living in groups of G people per group, so each leaf node here is a group of people on this rectangle, and each individual is represented by a node, some of them labeled here. Okay. And then you have a total of N people in the whole world. So you've got N over G leave nodes, these villages or communities. Okay? Let's assume for simplicity's sake, that this is an integer. And then, we can therefore say, take the base two log. Because this is, going to be a branching, binary branching of a tree structure. So, base two. Of the log of N over G, that would be the number of. Levels. And each level will be indexed by little m. So in this case, suppose we have, say, 80 people in the world. And that each society can host ten people then we'll have all together three levels. Okay, m equals one, two or three. Okay, this is one level, two level, three level. And these level denotes the chance that you know somebody. For everyone within the same community, there is a direct link. You can directly talk to each other. And if you want to reach, say send a mail to somebody else outside of your own circle, then you have to find the first common ancestry. Okay, we use, and sister node the tree structure here. These are the children nodes of this, a parent node. So you want to say, if I, A want to talk to B, I can directly talk to him. If they want to talk to C, C is not in the same community so I have to find out, what is the lowest and common sister node, well it's one level above, is n equals to one, okay. What if I want to talk to sa, D? Then I actually need to find the lowest, the first common, sister and of this level M equal to two. And A want to talk to E. Turns out I need to go all the way to level N equal to three. 'Kay? And the idea is that the probability that two people know each other decays exponentially in m, the level of the first common ancestry node. So probability p that two people separated by m level of first common ancestry, a piece of m. Is proportional to exponential decay two to the minus alpha M. Okay, so bigger the M, smaller chance that you know each other, and the rate of decay is alpha. As you can smell, this is very similar to the triumvirate model. And indeed you can view this kind of tree as a one-dimensional world, and we will see that we want alpha to be one. All right. So this is proportional and therefore to be precise we have to write down the normalization constant and therefore is P's of M equals to some normalization constant K times two the minus N. K is such that the summation of all the P's across all the M's equals to one. Okay. All right. So now, we can do the following. First, let's find out expected number of people reachable, okay, within the mth ancestor. Denote that by big N sub little m. Well, that's really a product of three things. First, the probability of knowing someone across M and sister level. Second. Is the number of communities that you can reach, which is two to the power M by traversing M community, M levels of ancestors. And the third factor in the product is G, is the number of people within each community, which we assume to be the same across all communities. So it's a factor, three factors multiplied together, the chance you know someone there and the probab, the number of communities times the number of people per community. Now, we are going to write this as two to the power one times m, the highlight. We're really raising two to the power one times m. And we'll later come back to this one, cuz it'll be playing a critical role to show that alpha needs to be exactly one for algorithmic small-world. Now can substitute the, this expression for piece of n and have the following expression then, g times k times two to the power one minus alpha m. Okay. There is a n here and then for piece of n there is minus alpha there. So this is a constant, this is normalization constant, therefore this decays with one minus alpha as the exponential decay rate. Now, what we want to do is to say, we want to compute the average... The expected length of the social search. So that's little l. Well, let's see, if I want to reach someone. I want to find out basically some, someone within my same community that can hop over. Knows somebody out there. Right. If I know that then I'll go straight. Otherwise, I have to find someone else to go to that community. Okay. And the expected number. Of people you need to pass on internally before you can reach to someone in m's community is one over nm. And the passing through all the m communities is summing over little m. And since we know the expression of nm, can write out this expression. Which is one over KG becomes importing out of the summation, summing over from N equal to zero to log of N over G-1 okay. From the zeroest level to the highest level times two to the power alpha minus 1M. Which turns out to be one over K G times, following expression, N over G, to the power alpha minus one minus one, two to the power alpha minus one minus one. And say this is the answer. Alright. Except, we know NG and alpha, but we don't know what K is. K is just a normalization constant. We need to express it as a function of parameters that to have physical meaning. Well, one way to express that is to say if we look at the average degree of a node in this graph in the tree is simply summation of NM's over N. Which turns out to be k g, n over g to the power of 1- alpha -one to the 1-alpha - one. So now, we can express k as a function of average degree, and the constant d, g, n, and alpha. You can substitute this over here. And then you get the following expression, L equals one over d bar, which is some constant n over g. The power alpha minus one minus one to the alpha minus one minus one. Times n over g to the power 1- alpha-1 two to the power 1-alpha-1. So now it depends on whether alpha is bigger than one or smaller than one or equal to one. If alpha equals to one, this relation doesn't hold, okay. We have to re-look at this expression again. And we will come back to that later. The moment we write this, in this expression we have assumed that alpha is not exactly equal to one. It could be past, bigger than one or smaller than one strictly. As you can see from these two mirror image expressions, see the way, you see L grows like what, like L over G times the power. Alpha minus one, absolute value. If alpha is bigger than one, this term will dominate. This will go away. If alpha is smaller than one, this term will dominate, and this will go away. Either way, we can say error. The interest quantity grows as a novergy to the power alpha minus one. Which is not a logarithmic growth in n. L is a function of n is not algorithmic, and therefore not us small world. And he's not algorithmic small world according to the greedy search method. So our hope is that what if, alpha exactly equals one. Well, if alpha exactly equals one, what would happen? Let's go back to this expression. Then n, m, in that case. Becomes nothing but g, k and this is the key part. It is independent of m. And that's exactly the intuition behind Kleinnberg resound we just mentioned. For the propriated decay rate of formula relationships over longer distance, you say that as the distance becomes longer, in this case n becomes bigger, I have a smaller chance of knowing people. But then there are more people for me to know. And if the two terms cancel each other, and therefore the number of people I may reach is independent of the distance. In this case it's just g times normalization constant k. Then something interesting happens. What would that be? Well let's look at what l is. Okay. In that case. We can find the following. Power is just one over, summation of one over MM, which is, simply. One over GK, times the summation of 1s. How many times? Well, log N over G times. Okay, and now we can use the same trick to express K as a function of the average degree, and then we see the following. One over B, borrow the average degree, times log of N over G, squared. This expression, as you can see, function of error is a function of N is logarithmic, well not exactly, it's square of logarithmic, but the polynomial of logarithmic is still good enough. In particular, this is an upper band, so we have a small world. A logarithmic, algorithmic, small world because the social search, followed by greedy routing distance is a function. Like a log of N. Or square, upper bounded by the square of log of N. And what really happened is the following. Behind the mathematics, is that if the rate of decay of probability of knowing someone over distance M goes down at just the right rate, then it cancels out by the effect of no having more people over longer distance out there. And if the two exactly cancel each other, then you get a constant term for Ns of M. And that leads to error becoming a logarithmic function as opposed to. A polynomial function. So here's a simple example. As I plot L as a function of N over this large range, you see that when alpha is. Very close to one, you see a very slow growth. Okay? When alpha deviates from one a lot, then the growth is much, much faster. A better way to look at that is think of L, okay, as a function of fixed N now very over alpha. You see, when alpha is exactly one, that's where it hits the isotopic growth rate of log and a square of that. For a numeric example with a fixed N, we cannot the effect of that but we can see that is small. In absolute terms, error is very small, less than five. And as alpha deviates from one. Then you can see L becomes much bigger. So either we look at it as a function of N, look at the growth rate asyntopically, or fix and look at a function of alpha and look at absolute value. Either way we validate what we just demonstrated through this numerical example. So now, we come to the summary part. We looked at a structural small world first. We want small short path to exist, and yet, large clustering coefficient to be maintained. Turns out that a regular ring with a little randomization to induce long range links suffices. When p is a small, then we get a large clustering coefficient C, and a small Big L, for the shortest the distance. And the reason of that is because this is an average quantity. It is not destroyed a whole lot by smore randomization. And yet this is an extremo quanity. A little randomization can help create short path. And the reason that assumptions is okay in this different weight of defining metrics is because of the bigger surprise out of the six degree separation experiment. The algorithmic small world. That short path not only exists, but also can be found with local information through, say, greedy routing methods. And we look at the source of search. Little l's behavior in Kleinberg, and also, the Watts Dodd Newman models. These models might be brittle. Advanced material will look at a less brittle model. All these, all these models, are so-called generative models. Because they can provide a mechanism to generate a network with a desired behavior. In this case, Small World. They are explanatory models because they explain what we observe. And they are useful but they're also dangerous as we will see in the next lecture. When we try to reverse engineer to explain or generate another famous phenomena in network topology. Not small word but scale free network or the long tail of no degrees. Then we'll see that if we do not add enough. Domain-specific functionality model, then these generated models can lead to a misleading conclusion. So see you.