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]
