0:17

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,

Â 5:11

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.

Â 7:16

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.

Â 8:15

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.

Â 11:33

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.

Â 13:21

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.

Â 15:15

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.

Â 16:29

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.

Â 19:18

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.

Â