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.
