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]
