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.
Regular Graph: Part A
Loading...
Из курса от партнера Princeton University
Networks Illustrated: Principles without Calculus
39 оценки
Из урока
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.
Познакомьтесь с преподавателями
Christopher BrintonLecturer
Electrical Engineering
Mung ChiangProfessor
Electrical Engineering
Now, in continuing our quest for a graph Explain to us what
the small world phenomenon is and explain explain to us how it comes about.
We're going to consider a graph that's at start contrast to the random graph that
we just looked at.
And so, the regular graph, in this case,
is a set of nodes that are living on a ring.
All right.
So, basically we typically represent a regular graph as just a,
a set of nodes that are living on some ring here.
So it means that they're all connected in like a circular manner.
So everyone is friends with everyone next to them.
And two numbers are going to determine the structure.
The first one is the number of nodes that are living on the ring.
Which in this case, one, two,
three, four, five, six, actually has to be an even number as we'll see in a minute.
So I'll just make it eight.
In this case there would be eight nodes on the ring.
And then the number of links that each node has,
which is a parameter called links per node.
Here each node has exactly two links in this case.
But we can, really we can increase the number of link that each node has and
the way that we do that is then by connecting a node to,
more of its neighbors right?
So as the number of links per nodes increases nodes are going to connect to
more of their closest neighbors.
So, both of these numbers have to be even numbers.
All of these are even so.
Here the number of links per node is two.
What if we increase it to four?
That means that each node has to have four neighbors.
So two of the neighbors are going to be on the left side, and
two of the neighbors are going to be on the right side of the node.
So for this node here, that means then, we're going to take the next
closest neighbor and make a direct connection that way.
For this node here we're going to take the next closest neighbor.
And then we repeat that for each of the nodes just like this.
And this will get a little messy here now.
But this is exactly how we would do that and how we create the graph searcher.
And so we continue that process so forth and
we're going to come up with something that looks like we'll show in a minute.
And we as we've said, we're going to choose an equal number of nodes on
each side and both these parameters have to be even numbers for this to work out.
So, when you have two links per node, the graph is just a simple ring, right?
Just a simple circular ring, that is illustrated in this case right here,
where each node, as we said is going to have two neighbors, one each side.
But now as we go to four links per node, we have a little more complicated of
a structure so each node has four links, two on each side.
And as we go to six links per node, each node is going to have six links,
three on each side.
So half of them are going to be on the left side,
half of them are going to be on the right side.
And the way that you can envision this really happening in reality is like by
having, if you told the number of people basically standing in a room
to arrange themselves in such a way that their closest neighbors were going to be.
On the left and the right sides.
So here we have six people so basically if you said.
Everyone okay arrange yourselves so
that your two closest neighbors are going to be right next to you.
That would be how we would arrange each other,
or arrange the graph in this sort of a ring structure.
And then if we said arrange yourself so
that the, your closest four neighbors are going to be right next to you,
then they would say, this person also is friends with that person.
This person's also close fiends with that person, and so forth around the ring.
So, this is two links per node, this is four links per node, and these are the two
parameters that are going to determine the structure of a regular graph.
So how do we evaluate the clustering coefficient for a regular graph?
Well, we're not going to derive the general formula for
the clustering coefficient as a function of the number of links per node.
But let's look at an example before I present the general formula.
Let's look at an example of two different cases.
The first one is when we have just two links per node.
So, when we have two links per node, as we said we just have
a simple ring where each, all the nodes are just living on one ring.
And, there's no triangles so we have no triangles.
Because, there's no set of nodes that are,
there's no set of three nodes that are connected in a triangular structure we
would need something like that to it, if happened.
So, since there's no triangles,
the number of triclosures is going to be equal to zero.
That means that the, clustering coefficient, clustering coefficient,
is going to be equal to zero.
Very simple.
Now let's look what happens when we increase, up to four links per node.
So, let's just focus first on the case of one node.
All right.
And like in this graph right here.
So we're going to focus on this one center node right here.
And let's just look at the number of triangles and
the number of connected triples that there are just centered at this one node.
So when we look at the number of triangles,
there's actually, only one triangle.
Right? So, the one triangle centered at this node
is just, exactly what we drew up in this case over here.
Just right here.
So between this blue node and this black node.
So there's one triangle.
Now the number of triples that we have gets a little more complicated.
So as we said, for each triangle there's going to be three triples.
So we already have three from that one pair.
But we're also going to have three other connected triples,
which are also highlighted in this diagram right here.
But basically when we have the six nodes, I'm just going to draw each of
the separate cases out so that it'll be easier to see.
Again, we're just considering everything centered at this one node for
the time being.
But if you can see, as you see here, one sot of connect,
one connected triple is going to be from this node to this node.
There, that's one connected triple.
That's one additional one.
Another connected triple is going to be from, if we reach,
draw this again one more time.
We have two, three, four, six,
here, our five nodes here and another connected triple would
be, connecting this node to this node and then connecting over to that point there.
That's going to be another one and then we have just one more,
which I won't draw in this case,
but, from this node connecting to this node and then off the top like that.
So it's going to be another one,
so there's going to be six total connected triples.
So we have three of them coming from the triangle.
We've got this outer triple here and then we have two
triples involving the inner nodes and again we're only considering the case or
of the triples and the triangles here that are centered at this nodes.
All right. So, this,
this node is the center point of this triple.
This is the center point of this triple and
this is also the center point of this triple.
So, now the question is, do we have to look at the rest of the nodes and
redo this computation?
And the answer is, actually, no.
Because the next property that regular graphs is that all the notes have
the exact same number of links.
And, the structures are all the same.
So, each node is going to have the exact same number of triangles,
in this case, one.
And, the exact same number of triples, in this case, six, centered.
So, we only need to consider one center node, because if we do everything else,
it'll all just cancel out in the end since we're taking the ratio of the tri,
of the triangles to triples.
Because the number of nodes,
the full number of nodes in this graph is going to have no effect.
The only thing that's going to affect the clustering coefficient is the number of
the number of links that each node has.
So the clustering coefficient in this case right here,
just considering this one node right here, is going to be one triangle, and
we have six triples over three, which is going to be one half.
And to see why that wouldn't matter.
Note that if we consider all of the nodes to three, four, five, six,
seven, eight here.
We would just be multiplying the one by eight, and we also be multiplying the six
in the denominator by eight which would be the equivalent of just one half again.
So, there's no need to consider all the different nodes.
Ознакомьтесь с нашим каталогом
Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.
Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.
© Coursera Inc., 2018 Все права защищены.
