Watts-Strogatz Model: Part A

Loading...

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

Networks Illustrated: Principles without Calculus

43 оценки

Princeton University

Networks Illustrated: Principles without Calculus

43 оценки

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 we just discussed why we can't rely on increasing the number of links per node on

the regular graph, to reduce the average shortest path length.

So let's think practically here.

We need a large clustering coefficient, and

the regular graph provides that pretty nicely.

At the same time, we need to have some wrong, long range links,

that are going to be able to.

Reduce stat distance between nodes on average.

So, what if we add a few long range links between nodes on

opposite ends of the graph?

What would that do for us?

Would that give us the properties that we need?

So, this was the basic idea behind the Watts-Strogatz Model,

which was first published in 1998.

In the very reputable journal Nature.

And you can definitely check out that original paper, if you'd like.

So there's three parameters in the Watts-Strogatz Model.

First is the number of nodes, just like we had with the regular graph.

Second is the number of links per node,

which is the same exact thing again as we had in regular graph.

Which is the number of nearest neighbors each node has.

And the third is prob, which is the probability.

Which is the chance of connecting, a random pair of nodes in the graph.

So, rather than connecting just to your, the neighbors that are nearest to you,

it's the chance of connecting to a random pair of nodes for each link in the graph.

So we repeat this process for each link in the graph, this whole

coin flipping process that we said before of random notice establishment.

And in this process that coin that we're flipping.

I was going to have a probability equal to "prob", which could be like 10% of

being heads and the rest of the times it's going to be tails.

So 90% of the time tails and each time we flip it if it gets heads,

then we connect to a random pair of nodes and if, if it's tails then we don't.

So this is the basic idea here.

We have the just the regular graph structure again.

And then we're adding a few long range lengths.

So, for instance if maybe we were going through this process for each link and

maybe when we were considering this link here we did that coin flip and

it turned out to be heads.

So then we established some random long range link.

And so we just took this node and

then we chose some other random node in the network and we just connected.

This node to that other node.

So, that's the idea behind the Watts-Strogatz Model.

So, now, suppose we have 32 links which is the case in this graph structure that you

see here without the randomization.

So, for each long range link, as we said,

we may or may not establish a long range connection between two random notes.

And higher probability the higher this value prob is,

that means the more successes we're going to have.

And therefore, the more of these long range random links we're

going to be establishing.

Note also that we're technically rewiring the links and what rewiring means,

is that technically in the Watts-Strogatz Model, when we consider this node here, so

we go through for each node and we do this whole coin flipping process if it

turned out to be heads and we did establish a long range length,

this one in this case, we would actually remove this node.

And we or this link and rewire so we would say, okay, for this node rather than be

connected here you're actually going to get connected up to this first node here.

But that doesn't change the intuition behind how these long range links

are established, it's really just a difference between saying that.

This person would stay connected with this person in

addition to having a long range friend.

Where as, to say in the actual case,

the Watts-Strogatz Model we would say that actually this person actually is

not going to be connected to this close neighbor.

Actually, going to have a long range connection to someone not in

his near cluster vicinity.

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

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

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

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

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

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