Closeness centrality: Part I

Loading...

來自 Princeton University 的課程

Networks Illustrated: Principles without Calculus

39 個評分

Princeton University

Networks Illustrated: Principles without Calculus

39 個評分

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.

從本節課中

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
Visiting Researcher and Lecturer
Department of Electrical Engineering
Mung Chiang
Professor
Electrical Engineering

So one factor we did not take into account with

degree centrality was the distance between nodes in the graph.

And here what we mean by distance is the number

of links that are on the path between two nodes.

And a path is simply a set of links that are connecting two nodes.

So we'll refer to a path by the nodes

that we visit in traversing it from start to end.

And since we have names here for nodes, we're

going to abbreviate them by the first letters for convenience.

So the link from Ben to Anna, for

instance, we're going to denote as B, A here.

And that's, of course, a path too; it's just a path with only one link.

On the other hand the, path from Ben to

Frank that goes through Anna, Cara, Evan and then Dana.

So we're going to go from Ben to Anna then to Cara to Evan to Dana and then to Frank.

Would be B, A, C, E, D, F and alternatively, we could go

to Dana before we go Evan because Dana and Evan are both connected,

and they're in turn both connected to Cara, so we could of

gone from Ben to Anna to Cara to Dana, to Even to Frank,

which would be B, A, C, D, E, F.

But we could have also gotten there using fewer lengths because

there's no need to go through both Dana and Evan, right?

Because both Dana and Evan are connected to Frank.

So why would we bother going through both of them?

And for instance, we could have taken B, A, C, D, F; so we can write that down.

B, A, C, D, F which you'd be going from Ben to Anna

to Cara to Dana to Frank, and therefore bypassing

Evan or B, A, C, E, F, which is another one.

This is an illustration of the shortest path between two nodes.

And this is the path between two nodes that has the shortest distance.

Again there's two shortest paths here between Ben and Frank.

Both of these are shortest paths.

And all four of these are paths.

So all shortest paths or paths, not the other way around.

Obviously, because not all paths are shortest paths that we showed here.

Paths are not going to be unique, because in general we

could traverse multiple different ways to get from one node to another.

Path lengths are also not going to be unique because on different paths

between given set of nodes could have different lengths, as shown here.

Shortest paths are also not unique.

So we should write this down.

They're not unique either.

because there could be multiple shortest paths between each nodes.

But the shortest path length, meaning the length of the shortest

path or the shortest paths, is always going to be the same.

Therefore, the shortest path length is itself unique.

Now if we find the lengths of the shortest paths between each

pair of notes, so, we find the shortest path between Ben and Anna.

Between Ben and Cara.

Ben and Evan.

Ben and Dana.

Ben and Frank.

Anna, Cara.

Anna, Dana.

And so forth between all the different pairs.

And find the longest of all those shortest paths.

Consider all the pairs.

That's the diameter of the network.

It's the longest of the shortest paths, considering all the different node pairs.

In this case, the diameter in this network is actually four.

And that should make sense because Ben and Frank

are the farthest away, no matter how you cut it.

There's no other pair of nodes you can find that's going to be of

distance four away from one another on the shortest paths between the pairs.

So the diameter is four in this case.

Now this is going to bring us to our second interpretation of importance,

which is to look at how far a node is from its neighbors.

And this is the closest centrality for a node.

So specifically, what we do is, we first

find the shortest path lengths to all other nodes.

So we take a given node, say Ben, and we want to find Ben's closeness centrality.

So we find the shortest path length from Ben to Anna, from Ben to

Cara, from Ben to Dana, from Ben to Evan, and from Ben to Frank.

We get all the shortest path lengths, and we write them down.

And we find the average of those.

So rather than finding the longest of those as

we would do if we were looking for diameter, in

one step to get to the diameter, we're going to take

the average of these in the case of closeness centrality.

And then the closeness centrality is simply

one over that average shortest path length.

So when we take this average, it becomes the averages shortest path length.

And the reason that we take the reciprocal is because they're, they're inverse ideas.

Right?

We want to he closest to go up as the average shortest path length goes down.

So a, as a notice closer to all other nodes,

the average shortest path lengths is going to go down.

Therefore, we wanted to have more of

a higher closeness centrality and vice versa.

So as the average shortest path length goes up, that means the node is

farther away, and therefore should be less

central and have less of a closeness centrality.

探索我們的目錄

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

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

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

通過 App Store 下載

通過 Google Play 獲取