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.
Dangling Nodes & Disconnected Graph
Loading...
From the course by Princeton University
Networks Illustrated: Principles without Calculus
39 ratings
From the lesson
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.
Meet the Instructors
Christopher BrintonLecturer
Electrical Engineering
Mung ChiangProfessor
Electrical Engineering
So, now we've illustrated a page rank calculation.
But here's the next question. Does the method we just presented always
lead to a unique solution? And the answer is, not quite yet.
There are some modifications that we have to make in order to be guaranteed that we
don't either have no solutions or multiple solutions.
Each of which case isn't good because then there's no single consensus that we
can come up with. So, let's consider again, this our
example over here and we've augmented it now with one link point to this node V
over here. Okay.
So now, let's look at V for a second. V isn't pointing to anyone.
It has no outgoing links. If you notice.
So, what does that imply? Well, remember as we said that a node has
to spread its important score to other nodes, right?
So, if there was one link over here then this would be V.
if there were two, then this would be V over two, and so on.
Right. But that's not the case here.
There's no spreading of any important score at all.
So, the only logical conclusion then is that v has an importance score of 0,
because it's not spreading to anyone. So, he has no importance score at all.
Because that's the only way it'll stay consistent with what we just did.
And now, V importance score of 0, we say that V was aggregating its importance
score from Z. So, this is Z over 4 because there's four
links 1, 2, 3, 4. So now, remember V has to be equal to Z
over 4 by our equations because V is aggregating all of this importance from
this link. So, if V is 0, then that means that Z has
to be 0, so then now Z is 0. Okay.
Well, if Z is 0, then that means that all these outgoing links have to be 0 because
he is spreading all of his importance equally to everyone.
And so, 0 divided by 4 is still 0. And well, then what's going to happen?
Look at Y. Y is spreading all of its important score
to Z, right? So, since Z is 0, Z has to be equal to Y
plus X over 2, right? And we can't have any of them be less
than 0. So, since Z is equal to 0, then the only
conclusion is that both of these have to be equal to 0.
So, now it's saying that Y has to be equal to 0 and X has to be equal to 0,
which means that this length is 0, this length is 0.
As you can see, it's going to cascade through and everyone is going to end up
having an important score of 0. So, we call, the, the problem all started
with this node V over here. And the problem was that V didn't spread
it's important score to anyone. And we call V a dangling node because
it's, it's just a node that doesn't point to any others.
And once you get to that node you're kind of sunk cause you can't go anywhere
else. Right?
If you're following the web graph, you can't possibly get out.
So, the only thing that happens is that it leads to no solution.
So, here we have basically the only solution working is that all the
important scores are 0 which is the trivial solution.
And so, we have no, and we should say no meaningful.
Because technically, 0 is a solution. Having them always 0, but there's no
meaningful solution here. There's no way to rank from our solution
that we've gotten. So, the way that we solve the problem of
dangling nodes, is that we assume that the dangling node points to every other
node in the graph. So, basically what we say is that we
assume V has a link to W. We assume V has a link to Z.
We assume V has a link to X. We assume V has a link to Y.
And we also assume that V has a link to itself.
So, it has a hyperlink, and that points back to it's own page.
And by doing that, then we don't have this problem anymore because as I ran the
surfer idea, once we get to V, then we can actually get out of V again.
And continue with that random surfing process.
So now, we fixed the dangling node problem, but there's a, there's a second
issue, in the idea of a disconnected graph.
So, we call a connected component a group of nodes which can reach each other, but
can't reach anyone outside of their group.
And, so basically in this graph right over here, we have two different
connected components, right. So, if our web graph looked like this and
obviously a lot of the internet might be something like this because the internet
is very sparse, as we said. So, there's going to be groups of nodes
that aren't connected so each other. So that we have A, B and C which are all
connected on one hand and we have D and E who are connected on this side over here.
So, the problem is that if we start in A go to B and then go to C, and then go to
B. And then, we go to C B, C B and so on.
Even if we're choosing within this group over here, we can't ever leave this sub
graph. because there's, there's no, way to get
out of this sub graph over here. And the same thing in here, is if we're D
and E, there's no way that we can get out of this.
We can't get over to this side because there's no link going over there and
there's no link going this way either. This is going to lead us to actually
infinitely many solution. So, there's an infinite number of values
of important scores that could satisfy this because we don't have any
relationship between these two over here. So, we, we have no relationship, then
basically we can establish any relationship we want and it will still
work. And this is going to be a problem
whenever we have more than one connected component because the entire graph isn't
one connected component. We have two or three sub graphs.
And so, we're stuck in one of these sub graphs forever, as we said, by a random
surfing philosophy. The solution to this is we add that thing
that we neglected initially where we said maybe they random surfer will eventually
get tired, right? So, if he's, if he's starting at A, and
he comes over to B, and then he goes to C, then back to B again.
Then maybe eventually he'll get bored and decide to just enter a random URL and
then he'll end up on D. And then, he can go to D, to E.
And he'll be stuck in that sub graph until he enters a random URL again and
comes back to C. So, we're basically establishing an
artificial link between each node. So, we're saying in a sense, each node is
connected to every other node because there's a way to reach them just through
our web browser rather than through the actual hyperlink connectivity on the
pages. So we add that purely random surfing that
we neglected initially into the mix.
Explore our Catalog
Join for free and get personalized recommendations, updates and offers.
Coursera provides universal access to the world’s best education,
partnering with top universities and organizations to offer courses online.
© 2018 Coursera Inc. All rights reserved.
