Watts-Dodds-Newman Model: Part B

Loading...

Из курса от партнера Princeton University

Networks Illustrated: Principles without Calculus

40 оценки

Princeton University

Networks Illustrated: Principles without Calculus

40 оценки

What makes WiFi faster at home than at a coffee shop? How does Google order its search results from the trillions of webpages on the Internet? Why does Verizon charge $15 for every GB of data we use? Is it really true that we are connected in six social steps or less? These are just a few of the many intriguing questions we can ask about the social and technical networks that form integral parts of our daily lives. This course is about exploring the answers, using a language that anyone can understand. We will focus on fundamental principles like “sharing is hard”, “crowds are wise”, and “network of networks” that have guided the design and sustainability of today’s networks, and summarize the theories behind everything from the social connections we make on platforms like Facebook to the technology upon which these websites run. Unlike other networking courses, the mathematics included here are no more complicated than adding and multiplying numbers. While mathematical details are necessary to fully specify the algorithms and systems we investigate, they are not required to understand the main ideas. We use illustrations, analogies, and anecdotes about networks as pedagogical tools in lieu of detailed equations. All the features of this course are available for free. It does not offer a certificate upon completion.

Из урока

It's a Small World

Six degrees of separation is a widely told story in popular science. How can it still be a "small world" with the enormity of the Internet today? It depends on how the social networks are structured, and on how we search for short paths, as we will see in this lesson.

Introduction2:22

Milgram's Experiment8:28

"Small world" in Culture5:16

Structural vs. Algorithmic Small Worlds3:51

Triad Closures and Homophily6:25

Average Shortest Path7:31

Random Graphs5:03

Clustering Coefficient: Part A8:32

Clustering Coefficient: Part B4:34

Regular Graph: Part A8:03

Regular Graph: Part B5:29

Watts-Strogatz Model: Part A3:31

Watts-Strogatz Model: Part B4:03

Discovering Short Paths6:38

Watts-Dodds-Newman Model: Part A5:21

Watts-Dodds-Newman Model: Part B8:11

Познакомьтесь с преподавателями

Christopher Brinton
Lecturer
Electrical Engineering
Mung Chiang
Professor
Electrical Engineering

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]

Ознакомьтесь с нашим каталогом

Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.

Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.

© Coursera Inc., 2018 Все права защищены.

Загрузить из App Store

Загрузить в Google Play