Degree centrality

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

So we just said, centrality is a measure of node importance.

The first obvious choice is degree centrality in which we simply

count the number of nodes that are connected to a node.

And in these types of graphs there's going to be

no need to distinguish between in and out degree anymore.

Because they are bi-directional.

In the case of web graphs we had to do so because we saw

that, one node could point to another while not vice versa was necessarily true.

But here the in and outs are going to be exactly the same.

So our job is even easier.

Let's apply the concept of degree centrality

to the graph shown here, this example graph.

So what does this imply?

Let's start with Anna.

So for Anna, Anna has two links.

Therefore, Anna's degree centrality is two.

For Ben, Ben has only one link.

So Ben's degree centrality is one.

Cara has three links.

So Cara's degree centrality is three.

Dana has three links as well.

So her degree centrality is also 3.

Same thing for Evan, he's got 3.

And Frank has a degree of centrality

of 2.

If we rank according to this we have Kara, Dana and Evan at the top, all with three.

Then, in second place would be Anna and Frank.

And, in last place would be Ben, the lowest.

So that's the ranking.

Cara, Dana, Evan at the top, then Anna Frank, and then Ben.

So is this, question is though, is this reasonable?

I mean, we can probably agree that Ben should be the

least important because he's only connected to Anna in the graph.

We can also probably agree that Dana and Evan should be equally as important.

Wherever they happen to lie in the graph they, or

in the importance ranking, they should be equally as important.

Because they're really connected to those same nodes.

Dana's connected to Cara, Evan, and Frank, whereas

Evan is connect to Cara, Dana, and Frank.

It's, it's kind of symmetrical in this case around the center point.

But consider Cara.

There's something special about her.

She provides the only connection that Anna and Ben have with the rest of the graph.

So Anna and Ben rely on Cara to be

able to be connected to the remainder of the graph.

Just like Dana, Frank, and Evan rely on Cara

to be able to be connected with Anna and Ben.

So if we removed Cara from the graph, we would cause a partition to happen.

So we have to, one thing we have to consider

is who's going to cause a network partition to occur?

Additionally, Ben would not be connected to the graph without Anna.

So if we removed Anna from the graph, Ben would be isolated by himself.

And on the other hand, removing any of other nodes besides them.

Would not isolate anyone from the rest of the graph.

Of course, the node that we're moving is going to be isolated,

but it doesn't have any affect on the remainder of the graph.

So if we're discussing centrality, [SOUND] shouldn't we reward Ben and Cara?

Since their connections are more vital to the graph's connectivity.

So as we saw when we were looking at page rank this

many issues with, you've seen the degree of the notices centrality measure.

So, degree centrality probably isn't a good measure.

And, we just pointed out a specific example of that, with network partition.

And, another asset.

If you're connected to many important nodes, you should be

rewarded, just as we talked about, in the page rank algorithm.

Because each web page is going to have the problem

to being able to spread its importance to its neighbors.

So, indeed we could also use the page rank algorithm here.

Would be possible to take the page rank algorithm

and just assume that the links go both ways again.

So Anna connected to Ben, Ben's connected to Anna, we

can definitely run page rank on any of these examples.

But, we're going to rather than looking at that algorithm, we're

going to to take more, other

more conventional approaches to define centrality.

[BLANK_AUDIO]

探索我們的目錄

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

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

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

通過 App Store 下載

通過 Google Play 獲取