Betweenness centrality: Part I

Loading...

來自 Princeton University 的課程

Networks Illustrated: Principles without Calculus

43 個評分

Princeton University

Networks Illustrated: Principles without Calculus

43 個評分

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.

從本節課中

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
Electrical Engineering
Mung Chiang
Professor
Electrical Engineering

We want to somehow factor connectivity into the centrality.

How can we explicitly bring connectivity into importance?

To see this, let's start with a few simple message-passing examples, so to speak.

So, suppose for a moment that Anna in our graph wants to send a

message to Frank, and she wants to get up there as quick as possible.

Therefore, she wants to use the shortest distance possible.

So if Anna wants to go to Frank, she has two possibilities, right?

She she can go, as we said through this shortest path to

Cara, Dana, and Frank, or she can go Cara to Evan to Frank.

So Anna, let's send her a message right here to Cara.

She has to tell Cara though, because without Cara,

she would not be able to get to Frank, but

once Cara gets the message, she's gotta send it

on Cara can either send it to Dana or Evan.

So Cara can send it up this way, send the message

up there, or she can send the message down this way.

And either of them could then directly forward that message over to Frank.

So the question is, what does this tell us?

Anna really has two ways to get her

message to Frank, and both of them involve Cara.

So if we want to assign points, so to speak,

to the intermediate messengers, Cara should get the most points.

Say, she gets one point, right?

So just say Cara gets one point for that because

without her, Anna wouldn't be able to get to Frank.

And

since only one of the two paths involved Dana or Evan, you

can consider them to be maybe half as important on this path, right?

Because they're interchangeable in a sense, so maybe Dana

and Evan will each get half a point for that.

So, let's take another case.

Suppose Ben wants to send a message to Dana.

So, Ben wants to go to Dana.

Now there's only one shortest path.

Ben can go to Anna, in turn to Cara, then up to Dana.

So for rewarding points again based on messages, Anna and Cara

should get the same amount because they're both on the intermediaries.

So, Anna should get one point, and Cara should

get one point additional to what she had before.

And the question is, how should these be related to what we had previously?

For the other messages, I mean, should they

be different or should they be weighted the same?

Is there anything different?

Do the difference is that between Anna and Frank, we had two

shortest paths, and between Ben and Dana, we only had one shortest path.

So, intuitively, since Cara lied on both the shortest paths before and she was

vital to that connection, Anna and Cara are still 100% vital to this connection.

So, Anna and Cara on this path should get the

same amount intuitively as Cara got in the previous case.

So, from Anna to Frank, we would say, again, we'll reward Cara with one

point and Dana and Evan with one half of a point.

And from Ben to Dana, we said we'd reward

Anna with one point, and Cara again with one point.

So, in this case, again Dana and Evan have

half of what everyone else gets in each case.

And this is the idea behind betweenness centrality.

So, in order to find the betweenness centrality for node, we want to consider

each pair of nodes, and find the shortest paths between each pair of nodes.

And then we want to award the other nodes points for being on the shortest path.

So remember, there could be one or multiple shortest paths.

In the case of Ben to Dana, there's one shortest path.

From Anna to Frank, there's two.

So, we want to find all the different shortest paths and then we want to

award the other nodes points for being on one or more of those shortest paths.

So, the points awarded to a node for a given pair is the

fraction of the shortest paths chain the pair that the node is on, right?

So, if there is three different shortest paths and one node lies on two of

the three shortest paths, then we would award that node two out of three points.

So, there's three total well, there's actually one total point but

there's three total shortest paths and two out of the three would be two thirds.

And so in this case, referring back to

our example again for Cara between Anna and Frank.

Remember there was two total shortest paths, and she's on

two of them, so we award her two of two.

And, on the other hand, for Dana and Evan, we award them

one of two because they're on one of the two shortest paths.

And, in the case from Ben to Dana, there's

only one shortest path, means the denominator's one there.

And either both Ana and Cara are on both of

them, so they get one of one point in each case.

And, once we do this for all the pairs, we add up a

number of points that each node has, and that it sits between the centrality.

探索我們的目錄

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

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

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

通過 App Store 下載

通過 Google Play 獲取