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.