Importance Equations

Loading...

En provenance du cours de Princeton University

Networks Illustrated: Principles without Calculus

39 notes

Princeton University

Networks Illustrated: Principles without Calculus

39 notes

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.

À partir de la leçon

PageRank by Google

In this lesson, we will take a look at PageRank, Google's famous algorithm for ordering the results on its search page. PageRank is a prime example of how coming up with the right "ranking" of a set of items is a difficult yet important question in networking.

New Word in the Dictionary5:01

Search Engines7:03

The "Random Surfer"7:38

Importance Equations5:31

PageRank Example Calculation10:40

PageRank Example Summary5:14

Dangling Nodes & Disconnected Graph6:22

Robust Ranking3:24

Rencontrer les enseignants

Christopher Brinton
Lecturer
Electrical Engineering
Mung Chiang
Professor
Electrical Engineering

So let's see if we can take what we just did and apply it to actually computing

some of these important scores. Or coming up with a way to equate the

important scores to one another. So if we consider our graph again, let's

just write down what we had before in terms of spreading the scores.

We saw before this link would have been W over 2.

This one also W over 2, Z, since there's three links, each one's Z over 3, Z over

3 and Z over 3. X gets X over 2, because there's two

links, the outgoing, out degrees two. And Y gets just one, because there's only

one outgoing link, just Y. And this is a really good way to

visualize it by the way, because then you can see how each of them have to sum to

one. Our [LAUGH], [INAUDIBLE] have to sum up

to the importance of the nodes, so this is W, again, this is X , this is Y and

this is Z. So, these, each of the outgoing degrees

sum to the incoming one. And so now, what you have to also realize

is that, we just said how each of these nodes spreads their importance scores.

But now we can write each node's score in terms of the scores on its incoming

links. So the idea behind page rank is that we

should be able to write each of these important scores at node x in terms of

what's coming into it. So that's going to define how important

it is. Something coming from W, something coming

from Z and the exact values that we use are the W over 2 value here.

Because that's the importance that W spreads on to its link, and Z over 3,

because that's the importance that Z spreads onto this link.

So we just write an equation at each node in terms of the incoming lengths.

So, for X, we can get that X equals W over 2, plus Z over 3, right?

Because when you, if you start at W, the only way you can, because the only way

you can get to X is by either being on W or Z if we're neglecting the idea of

surfing randomly right now. And if you're on w, there's a w over two

chance then that you're going to come to x because it splits half and half.

And if you're on z, there's a Z over 3 chance you're going to come to X, because

it splits in, into thirds. Now let's try to write the equation for

node W, and w's important score. W can only get, you can only get to w in

one step, at least, if you come from z, right?

So, W then has to be equal to Z over 3, because when you're on Z, there's a

third, only a third of a chance of getting over to W.

So, we say that, W is equal to Z over 3. Now we did w and X, let's do Y.

Now Y has three incoming lengths. Okay, because we said before it has an n

degree of 3 and that's why before at least we thought it was the most

important node with the N degree. So you can get to y if you're on W, X or

Z. So coming from W there's half of a chance

so we say that Y equals W over 2 plus then coming from X there's also half a

chance plus X over 2. Then coming from Z there's a third of a

chance, so we say plus Z over 3. And then now if we look at from Z's

perspective, Z being the last node over here.

From Z we can only get to it from either Y or X.

So, from Y it's actually guaranteed, if you're following hyperlink.

It's the only, Y is only out degree is only to Z.

So, Y only points to Z. So Z is equal to Y plus, and then from X

it's half, so plus X over 2. So these equations right here, you can

say that they are all dependent on each other, right?

X is dependent upon W, W is dependent upon Z, Z is dependent upon X in turn, Y

is dependent upon w, x, and z and so on. And so this whole idea of X being

dependent upon w, which is then dependent upon Z, which then dependent X, and so on

as a circle. That's the idea of recursion.

It's seemingly circular logic, but it turns out that we can actually solve if

we take all these equations together. We can actually solve for one solution of

the equations. guaranteed to provide that we make some

assumptions about how the equations are built, we'll look at that too, a little

bit. But if we can come up with a solution to

these equation, that's going to give us the page rank solution.

And each page's page rank importance. So we have to come up with values of W,

X, Y and Z. That will satisfy each of these equations

at the same time. Now when you solve a system of equations,

there's two, there's three possibilities. The first possibilities are there's no

solution. So there may not be values of X, W, Y,

and Z that can solve each of these four, say one, two, three, four.

There may not be values that can do it. The second is that there's a unique

solution [SOUND]. And unique means that there's only one.

There's one unique way of doing it. We could pick, we could find one value of

W, X, Y and Z at the same time that will work for all these.

And the third one is at, there's multiple solutions, so we'll write this, multiple.

So we want to make it so that we have a unique solution.

And as we'll see there is a unique solution to this set of equations it

turns out. But we're going to have to make a few

modifications in the end of this, as you'll see, in order to guarantee that

there's not either multiple solutions or no solution.

Explorer notre catalogue

Rejoignez-nous gratuitement et obtenez des recommendations, des mises à jour et des offres personnalisées.

Coursera propose un accès universel à la meilleure formation au monde, en partenariat avec des universités et des organisations du plus haut niveau, pour proposer des cours en ligne.

© 2018 Coursera Inc. Tous droits réservés.

Télécharger dans l'App Store

Disponible sur Google Play