Explore
For Enterprise
Join for Free
Log In

艺术与人文
商务
计算机科学
数据科学
信息技术
健康
数学和逻辑
个人发展
物理科学与工程
社会科学
语言学习
學位
證書

瀏覽 Coursera 的全部課程

瀏覽
搜索
企業版
登錄
免費加入

Betweenness centrality: Part II

Loading...

网络运作：无需微积分的原理简介

普林斯顿大学

4.4（47 個評分） | 11K 名學生已註冊

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.

查看授課大綱

審閱

4.4（47 個評分）

5 stars
27 ratings
4 stars
13 ratings
3 stars
6 ratings
2 stars
1 ratings

從本節課中

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.

Facebook & Twitter9:55

Who is "important?"6:35

Social graph2:34

Degree centrality4:18

Closeness centrality: Part I5:00

Closeness centrality: Part II10:28

Betweenness centrality: Part I4:59

Betweenness centrality: Part II13:57

Contagion: Part I6:17

Contagion: Part II7:01

Cluster density2:43

Marketing strategies10:50

教學方

Christopher Brinton
Lecturer
Mung Chiang
Professor

腳本

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]

探索我們的目錄

免費加入並獲得個性化推薦、更新和優惠。

Coursera 致力於普及全世界最好的教育，它與全球一流大學和機構合作提供在線課程。

© 2019 Coursera Inc. 保留所有權利。

通過 App Store 下載

通過 Google Play 獲取

Coursera
關於
管理團隊
工作機會
目錄
證書
MasterTrack™ 證書
學位
企業版
政府版

社區
Learners
Partners
Developers
Beta Testers
Translators

連接
博客
Facebook
領英
Twitter
Instagram
YouTube
技術博客

更多
條款
隱私
幫助
內容訪問
媒體
聯繫我們
目錄
附屬公司