Discovering Short Paths

Loading...

Do curso por Princeton University

Networks Illustrated: Principles without Calculus

39 ratings

Princeton University

Networks Illustrated: Principles without Calculus

39 ratings

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. Please note that per Princeton University policy, no certificates, credentials or reports are awarded in connection with this course.

Na lição

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

Conheça os instrutores

Christopher Brinton
Lecturer
Electrical Engineering
Mung Chiang
Professor
Electrical Engineering

So we just saw the magic of small worlds with a large clustering coefficient.

We have triad closures with most of our friends, so

in a regular graph the people that are close, next to us.

And small fraction of our friends though are going to be outside of our typical,

quote en quote, social circle, our normal circle, social, social circle.

So, all Milgram needed to observe six degrees of separation,

was this very small fraction of long range links.

So, these, this small fraction is a very important part

of establishing small world, six degrees separation.

So, as we said, the shortest path is an extremal quantity.

And we only care that there exists a shortest path, not that their all short.

And that should make sense right because you know if you were driving somewhere

for instance.

Why would you want to tak ea longer route,

you just want to take the shortest route none of the other ones necessarily matter.

Unless of course there's a detour or

something but don't have to get into that here, because that's not relevant.

You only really care about the shortest path.

You just know that if I can get some, to someone in two hops then I'm

going to say that I have a distance of two from them.

But there's is actually a catch to this, right.

These is an issue with the shortest path existence.

We just said that, this is an extremal quantity,

because we're just concerned with the fact that there exists a short path.

Not that all the paths are short.

But if there's only one shortest path, people need to find these shortest paths.

So how is someone going to be able to tell if one is shortest or not.

Sort of like if you're driving somewhere, right, and

if someone tells you well there is a way to get to your destination in 15 minutes.

All right, that's not really going to do much for you,

because you have to be able to actually find how to get there in 15 minutes.

So you can use roadsigns, and other things that you'd see along the way,

but other than that, you're not really going to have much help.

You're not going to be able to find these short paths.

But Milgram, saw in his experiment that people with very limited,

local information were able to find these short paths.

And now we can illustrate that here in this Watts Strogatz type graph, right so.

For A, A can get to C in just 2 hops, right?

You could, A can go right to B, and then to C.

But, how is A going to know to get to C that way?

So why wouldn't A,

for instance, go to this node, who would then in turn go to this node.

Who maybe then knows that he should go this way, and then up here.

But that's already now having hopped length of one,

two, three, four, rather than a hop length of two.

So, people need to be able to find short paths, and it's not always easy.

Because we don't know the network structure,

we don't know who you're friends, or friends with necessarily.

So how can six steps be locally discoverable?

And this is the algorithmic portion, portion of the problem.

How can people find these short paths with very limited local information?

And that's what we're going to focus on now for the rest of the lecture.

So, if you were one of those people participating in Milgroom's experiment,

how would you decide the next hop?

Probably would have been some combination of geographic proximity which is

relatively easy to see.

Just to see how close,

a person is to the destination they need to get in terms of where they live.

And, also occupational proximity, which could be harder to determine cause its not

clear necessarily which occupations would tend to know each other.

Certain occupations that could seem completely opposite may actually work

together in certain types of jobs.

And, you would do this you would combine thee two to

come up with some hybrid social distance metric.

In order to determine how far you think a person is away from the destination then

choose the best one.

Or at least that's the case in Greedy social, social search.

In Greedy social search what we do is you choose the best, next hop,

based upon this social distance metric.

So everybody does what they know based upon their own local information.

You make the best possible decision.

For the next step and that's why it's actually called greedy.

Because you're only doing what you know, and

what's best base upon your current information.

Of course it may not turn out to be the optimal overall.

Because who you go to next may not be necessarily what's going to get

you to the destination in the quickest number of pops.

Now we can illustrate that in a example here.

So suppose X, this person X, is an engineer located in Princeton, New Jersey.

All right, so this engineer wants to get to destination Y,

which is, who is a lawyer in Pala Alto, California.

So, the engineer takes a look at who he knows, and,

he knows an actuary who's in Summit also in New Jersey.

And he knows someone else.

He also knows a politician who's in Seattle, Washington.

And he says to himself, okay well politicians kind of close to a lawyer.

You know, they probably run into some similar cir, circles and so forth.

So, Andy is in Seattle and Seattle Washington's a lot closer to

Palawatha California than New Jersey is so I'm going to forward it over to A.

And once a politician gets it,

he also runs the next, that same greed social search process.

And chooses the next best hop based upon his local information.

And says, okay, well I don't know the lawyer directly, from, to California.

But I know a politician in Los Angeles, California,

who is closer than I am cause he's in California and he forwards it to B.

And then it turns out that politician happens to know the lawyer at

the destination.

So this took a total of one, two, three hops to get there.

But it turns out that in reality this actuary in Summit,

actually knew the lawyer directly.

So, but how would the person know if this actuary in summit,

New Jersey is going to know the lawyer in Palo Alto California?

So if, if X knew the entire network he would have said,

all right, well I need to forward it to C, and then forward it to Y.

But we could see here that he couldn't choose his shortest path, the,

the shortest path between him and Y.

Because he doesn't have total view of the network,

he only has his own local information.

And, as we said, this process continues.

So X does it, passes it to A, A does it, passes it to B, B, C is the destination.

So this is not going to result in the optimal route because nobody

has a global view of the network.

But we wonder why there's, the average length discovered by such a previous

search could be close to the average shortest path length.

And if so, if we can come up with such a network where this type of

greedy search would result in something close to the average shortest path length?

Then in addition to being plausible,

we could say that shortest paths are actually discoverable.

So we're looking for that discoverability, Still.

So we want to be able to show that this can lead to that under a certain network.

Explore nosso catálogo

Registre-se gratuitamente e obtenha recomendações, atualizações e ofertas personalizadas.

O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.

© 2018 Coursera Inc. Todos os direitos reservados.

Baixar na App Store

Baixar no Google Play