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.
Betweenness centrality: Part II
Loading...
來自 Princeton University 的課程
Networks Illustrated: Principles without Calculus
39 個評分
從本節課中
Influencing People in Social Networks
In this lesson, we will continue with our theme of influence, now paying more attention to people's social networks. We will discuss different ways of measuring importance and a popular model for influence spread in social networks like Facebook and Twitter.
與講師見面
Christopher BrintonVisiting Researcher and Lecturer
Department of Electrical Engineering
Mung ChiangProfessor
Electrical Engineering
For illustration purposes, let's find the bridge
betweenness centrality for one node at a time.
We'll start off with Cara.
To do this, we're going to have to consider each pair separately.
And we're going to have to ask two questions.
The first one is, how many shortest paths are there between the pair of people?
So, if it's the pair Anna/Frank, how many shortest paths are there?
There's two.
And then, how many of these shortest paths contain Cara?
And for that example, two of them contain Cara, so then
the result is 2 of 2, which is equal to 1.
And doing this can allow us to compute the desired fractions.
Note that in, in doing the computations, we don't have to
consider any pairs that contain Cara because that's the node in question.
Therefore, it would, wouldn't really make any sense to include her in
any of the pairs because she has to lie within those shortest paths.
Additionally, we don't have to double count pairs.
So, once we've considered Ben and Dana, we don't have to consider Dana and Ben.
And that just reduces the amount of work that we need to do.
And as a side note, we expect Cara to have a high betweenness centrality.
So expect to be high.
Intuitively because she holds the two parts of the graph together.
So any time Anna or Ben wants to go to
the other side of the graph has to pass through Cara.
Any time Dana or Evan or Frank want to go through this
other side of the graph, it has to pass through Cara as well.
So now, let's enumerate the pairs and find the
total number of times that Cara's on each of them.
Start with Anna and Ben.
So Anna and Ben, A and B.
For Anna and Ben, how many total shortest paths are there?
There's only one, which is link AB and how many of these does Cara lie on?
Well, none of them because she doesn't lie on any, the single link
AB, so zero of one, she gets for that, which is zero points.
Now let's
consider Anna and Dana.
For them, there's only one shortest path which
is ACD, so there's one shortest path, and
Cara does lie on that shortest path, so she gets one out of one, which is one.
Now
we'll consider Anna and Evan.
[SOUND] For Anna and Evan, there's one shortest path, again, A going to C going
to E, and that does include Cara, so it's one of one, which is equal to one.
And for Anna and Frank, we have two shortest paths.
Again, we have Anna, Cara, Dana, Frank, Anna, Cara, Evan, Frank.
So there's two shortest paths.
And Cara happens to lie on both of them, so she gets one point for that.
Now for Ben and Dana.
For Ben and Dana, there's only one shortest path which is BACD,
and Cara does lie in that path, so she gets one point.
For Ben and Evan, there's only one
shortest path, and again, Cara lies in that.
So she gets one point.
For Ben and Frank, there's two shortest paths.
Really, doing this is just taking the case for Anna.
It's going through all these other nodes and really
is the same computation in this case, for Cara.
So, it's two of two, because she lies on both of
those shortest paths, and I'm just going to give her one point.
And we can enumerate the rest of them as well,
but they're all not going to include Cara because anyone on
this side Dana going to Evan, Dana going to Frank, or
Evan going to Frank does not have to pass through Cara.
So for Dana and Evan, we have zero of one, which is equal to zero.
For Dana and Frank, we have zero of one, which equals zero.
And for Evan and Frank, we have zero of one, which is equal to zero.
So then, what we do is we add up all
these points that Cara got to find her betweenness centrality.
So we're going to say that the betweenness for Cara is
equal to 0 plus 1 plus 1 plus 1 so I'm adding all these.
Plus 1 plus 1 plus 1 and then plus 0 plus 0 plus 0.
Now I'm just writing this out to show the total number of pairs that we considered.
Which is one, two, three, four, five, six, seven, eight, nine, ten.
And that's six.
So Cara's betweenness centrality is six.
Let's take Dana as another example.
Note we've already found most of the
shortest paths except for those involving Cara,
because we had to do that in order to compute between the centrality for Cara.
Now we don't expect Dana to have high betweenness centrality
value, because most of the shortest paths don't include her.
Right?
So, really only the shortest paths that are, kind of going up this way are
going to include her; therefore, we don't expect her to have a very high value here.
So let's consider all the pairs starting with Anna.
So, we have to do Anna Ben, Anna Cara, Anna Dana, Anna Evan, Anna Frank.
Now for Anna to Ben and for Anna to Cara and for Anna to Evan, we see
there's only one shortest path in each of those
cases, and none of them are going to involve Dana.
Right?
So we can easily write A and B, A and C, and A and E.
There is one shortest path, and none of them are going to involve Dana,
so therefore, this gives a value of zero for each of those cases.
For Anna and Frank, it's a different story because Anna can come
up through Dana to go to Frank or go down through Evan.
So, we have two total, shortest paths, and one of them involves Dana.
So one half, which is 0.5.
So she gets half a point.
Now from Ben, for most of them, it's really the same story, right?
So from Ben to Cara and from Ben to Evan, there's going to be no value.
So Ben to Cara and Ben to Evan
there's going to be none of those there's only one path in each case.
And none of them are going to involve Dana.
So she's going to get zero points.
Zero over one.
Now for Ben and Frank, there's going to be
two possible shortest paths.
Just going up through Anna from what we showed before.
And that one of them is going to involve Dana, so
one half, she is going to get half of a point.
Now from Cara going to Evan, we know there's only one shortest path
straight from Cara to Evan, and that doesn't involve Dana, so she gets zero,
and from Cara to Frank, we know that there's two shortest paths; we can
either go through Dana or down through Evan, and one of those involves Dana.
Therefore, she gets half of a point, 1 over 2.
And lastly, from Evan to Frank, there's only one
shortest path straight from Evan to Frank, just one link.
So that's going to be zero points.
So now to find the betweenness for Dana.
Betweenness for D, we're just going to add up these values so
just considering the non-zero ones, we have three instances of 0.5.
We have 0.5 plus 0.5 plus 0.5, which is equal to 1.5.
So, betweenness for Dana is going to be 1.5, which is significantly lower
than what we computed for Cara, as expected it's four times lower.
So we can continue this process for the other nodes in the exact same way.
Let's let's look at Anna first.
So for Anna, we can intuitively see that she's
only going to lie on the shortest paths that involve Ben.
And further, she's going to lie on all
those shortest paths because for Anna to be
in the middle of a shortest path it's
going to have to come across through this way.
So from Cara, she's going to get one of one, because there's
only one shortest path to Ben that way, and she's on it.
From Dana, she's similarly going to get one of
one, because there's only one choice path to Ben.
From Evan, the same thing, one of one.
And from Frank, there's two ways, because he could go
either through Dana, or through Evan, so there's two of two.
Each of these are all equal to one, so therefore that's a total of four.
So that means the betweenness for Anna is going to be equal to four.
Now, for Ben, Ben doesn't lie on any
shortest paths because Ben is right at the end.
He's kind of a terminal point in the graph.
And therefore, the only shortest paths he's
going to lie on are ones where he's an
end point, you know, from Anna to Ben or from Cara to Ben, so forth.
But he's never going to be an intermediary point in any of the shortest paths.
Therefore, his betweenness is going to be zero.
So the betweenness for Ben, it's going to be equal to zero.
Now for Evan,
if you look at the structure of the graph, he's exactly the same as Dana, right?
So just by symmetry, you know that Evan
and Dana are going to have the same betweenness centrality.
And if you want to verify that, feel free to go through and
actually do the computation to figure out
what the betweenness centrality is for Evan.
But just note that Dan and Evan are really interchangeable here.
So the the betweenness
for Evan is going to be the same as what it
was for Dana, which is 1.5, same as Dana, we'll write.
And for Frank,
Frank doesn't lie on any shortest paths either, right?
The only way he's an intermediary is if it's
passing through him, in going from Dana to Evan.
But you would never do that, because you could go directly from Dana to Evan.
So the betweenness for him is going to be zero as well.
The betweenness of Frank is also going to be zero.
So we summarize the betweenness centrality values for each node
on the right here, which we just went through and computed.
So the new ranking is going to be Cara first, followed by Anna,
followed by a tie between Dana and Evan
in third place, followed by a tie between Ben and Frank
in last place.
Now, we can make two observations here; first is that now
Cara is by far the most important, which is what we wanted.
Her value's 50% higher than Anna's because four times 1.5 is going to give you six.
And it's four times larger than Dana and Evan.
And as we said, we wanted it to be significantly larger than theirs before.
And now, Anna is more important.
Anna is more important than Dana and Evan.
And we indicated that before, both
of these characteristics are likely desirable, so
we want Anna to be more important than both of them because of, because
of Anna's contribution, in terms of holding
the graph together, and additionally in terms
of Cara's contribution, so we really kind of would want to see this intuitively.
And we should also point out that it is possible
to compete betweenness centrality on the links rather than nodes.
So what we've done here is we've done it on
the nodes, and we've created the nodes as the values.
We can also do it to the links, right?
So you consider all the shortest paths that contain each valued link.
And it's really exactly the same procedure, and we're
not going to have time to detail it mathematically here.
And in this table here, we've just summarized what what we computed in terms
of for nodes just forgetting about links now in terms of betweenness for links.
Coming back to what we computed here, we did
for degrees of centrality, closeness centrality and betweenness centrality.
And, we we can, for each of the nodes, we have the value
of the centrality measure and also the rank they got based upon that.
And so we see all the way from degree to
betweenness how they're the permutation basically has, has gone from
what we thought wasn't really necessarily going to be to correct
to something that's seems to be correct, at least intuitively.
Now obviously closeness and betweenness centrality are
going to be more acceptable forms of measuring importance
than degree just like we saw page
rank being more the acceptable form than degree.
Between closest and betweenness you know, it's, it's sometimes going to
depend upon the situation, which one would, would be better.
Betweenness centrality is more complicated,
and it's probably more widely accepted.
But again, it's, it's not like you can say
one of them is necessarily better than the other.
That's not an that's not an unambiguous question.
[BLANK_AUDIO]
