Random Graphs

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 let's continue through our search for an explanatory model.

Consider the following situation.

Suppose we are given ten nodes.

And we want to connect them in what's called a random graph.

So I'll explain the process now of random graph formation.

So with the random graph we take each pair of these nodes, so

each of these ten nodes for instance.

We can line them up in a circle maybe one, two, three, four, five, six,

seven, eight, nine, ten.

And we consider each pair of nodes.

So, let's say, we'll consider this node and this node first, for instance.

And, we're going to establish a link this a certain probability between the two.

So we'll take some fix probability, whatever it is.

And then we'll establish the length of a certain probability and

the way to think about this, if the probability was say,

10%, so say there's a 10% chance we'll establish a link.

You think of a, a biased coin, right?

Which has a 10% chance of lading on heads and a 90% chance of landing on tails.

And if it lands on heads, every time it lands on heads we establish a link.

So, suppose in the first trial, we'll say, okay there was no.

Nothing.

So, it land on the tails, so we don't establish a link.

Now we consider this pair.

And again, we, it doesn't establish a link.

Okay? Maybe then when we consider this pair,

it does establish a link.

And when we consider this pair, it doesn't.

This pair, it doesn't, and so forth.

And you just continue that, and

you'll end up with a certain amount of the nodes connected.

Right?

So, I'm just randomly, connecting nodes here.

So, with a higher probability, we're going to expect to have more links.

And the reason we say, expect is because whenever we're dealing with probabilities,

we always have to think of what's the expected outcome of that situation.

So, the higher the probability is,

the more likely that each of these trials that are running of success-failure,

link establishment, or link non-establishment are going to succeed.

And therefore, we can say that we expect to have more links with

a higher probability, because link establishment is a random process.

So, this could be an example, for instance of 10% link establishment.

Okay. So now as we increase it to 25%,

we could regenerate that and do the process again with 25% probability and

we see generally, we have more people connected and here's 50%.

So we see there's even more and as we went more and more obviously,

in the extreme cases of zero percent we'd have no one connected and

a 100% everyone would be connected to everyone else.

But you can see that increasing this probability.

It just makes us have we, as we increase the probability we

expect to see more links and a higher density in the resultant graph.

Now this doesn't sound like the way most networks form, right?

So, this would be somewhat equivalent to saying, okay,

we have ten people in a room randomly, and they don't know each other.

Now, we put them in a room and we tell to decide randomly, whether or

not to be friends.

Right? That's probably not going to happen.

Now, the question is, what small-world properties are needed?

So, even though it doesn't sound like most networks,

would it be able to satisfy the properties of small worlds?

Well, for small worlds, we need small average shortest distance on the one hand.

And random graphs do actually satisfy this,

because there's no change in the probability between a very,

between two different links depending on how far they are.

It's some fixed probability, we said p, here.

So whether the link [COUGH] is here to here, or

the link is all the way over here, the pair.

This pair and this pair are going to have the same exact probability of

being connected by a random graph.

So therefore, we are going to get or

we're going to expect to get long range links, as well as short range links.

So, it does satisfy this property, of having a small average shortest distance.

But the other thing we need, is we need homophily in the graph.

But, it doesn't satisfy that property.

So it does satisfy small average shortest distance, but

it doesn't satisfy homophily.

And the reason it doesn't have this property is that, to precisely for

the reason we said here.

For homophily, we need to have some triangles or

some triad closures in social relationships.

Right? But, just because this person's connected

to this person, and

this person's connected to this person, suppose they are.

Then it has, there's no increased chance of having these two people and

be connected to make that trial closure happen.

So in general, it's not going to have the homophily property that we need of

friends of friends more likely to be friends.

So therefore, the random graph is not going to satisfy the small-world property.

So, it does not satisfy, small world.

And so, what we really need to do is figure out a way to be able to

quantify this homophily, which is what we're going to look at next.

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