Robust Ranking

Loading...

En provenance du cours de Princeton University

Networks Illustrated: Principles without Calculus

40 notes

Princeton University

Networks Illustrated: Principles without Calculus

40 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. All the features of this course are available for free. It does not offer a certificate upon completion.

À 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 you can ask yourselves the same question again.

Is that enough?

Is that going to always give us one unique consensus or

one unique ranking of web pages?

And the answer now is yes, we do have enough and that will always

guarantee that we will have a unique solution with that page rank algorithm.

And taking those two things into consideration does give us

the page rank scheme.

And so as the process we presented before, which accounts for dangling nodes and

disconnected graphs that forms the basis for our page ranking.

As with any company, you can assume that they are using a slightly different

approach and they optimize it a lot over time.

But that's the basic idea of how they go about ranking the web pages.

Notice how difficult their problem is though because there's billions and

billions of those web pages.

So they have to be able to do the computation very quickly.

And they have to, basically, deal with lots of large data sets and

large data objects like matrices.

And they have to be able to do computations on them very quickly, and

update those computations quick.

So if we take this graph again, just for a second.

And just to illustrate exactly how that calculation would go with page rank.

The first thing we notice again, is that V is a dangling node down here.

So what we would do is we would assume there's a link coming up here.

That there's a link here.

There's a link to this guy, and there's a link to x.

And that there's also a soft node to V.

And initially then, this node disconnected components here but

if there was one disconnecting component, maybe would could assume

that there's nodes over here like A and B, for instance.

And if they're connected to each other, going back and

forth, then that other randomization aspect would basically connect them and

have a pseudo connection to each of the other guys, by that randomization.

Say that there is a way to get there.

But it's just you have to go through your browser or

the random server has to go through this browser to get there in our analogy.

And we could do this for every leg.

So then every node has, in a sense, a connection to every other node,

as we said.

So as long as we account for dangling nodes and disconnected graphs,

then we can be guaranteed that that procedure will have a unique solution.

So now the question is, how much randomization should we have?

So in that random serving philosophy, how many times should we be just following

the web graph itself versus how many times should we be jumping to random pages?

Including that we'll have an affect on the algorithm itself and

how quickly it can approach its solution.

PageRank itself assumes a 15% randomization.

And so that's basically what that's saying is that 15% of the time we're going to

rely on the randomness,

or just random URL's that we searched through when we used page track process.

And the other 85% of the time,

we're going to rely on the connectivity in the web graph.

And there's a trade off there

computationally in terms of how quickly the algorithm will converge.

Much like what we looked at, this is a good review of the stuff with distributed

power control back in the first chapter.

So this is a trade off of how quickly the algorithm will converge with

how much randomization we're putting in the solution.

And so again,

what this means is that we're following the web graph 85% of the time and

we're entering a random URL 15% of the time in our random surfing analogy.

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.

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

Télécharger dans l'App Store

Disponible sur Google Play