This post is a studying notes of paper “A Set of Measures of Centrality Based on Betweenness”, the paper [pdf], wrote by Freeman in 1977, is an introductory and the most classic paper of betweenness centrality. Based on the betweenness centrality concept first introduced by Bavelas in 1948, the paper introduces a set of measures of centrality, including point centrality, scale free (relative) point centrality, and graph centrality.

Betweenness and Point Centrality

The classical centrality measures of Bavelas (1950) etc. can not be used by unconnected networks, since they define the centrality of a point as the sum of the minimum distance between that point and all others, thus all distance sums are infinite in unconnected networks.

In order to obtain a more satisfactory solution per centrality measurements, Freeman adopts the betweenness concept first introduced by Bavelas, betweenness of a point is “the degree to which a point falls on the shortest path between others”, and therefore has a potential per control of communication, persons in such central positions could influence the group by “ withholding information (or) coloring, or distorting it in transmission”.

Measurement of Point Centrality

Consider a unordered pair of points {} . Either are unreachable from each other or there are one or more paths between them. In the later case, each path has a length equals to the number of edges contained in it. Among the paths connecting pi and pj, one or more have the shortest length: the geodesics.

If $p_i$ and $p_j$ are unreachable from each other, then , denotes betweenness centrality of point with respect to and , is zero;

If and are adjacent, means that there is only one edge connecting them, since does not reside on the shortest paths of and , also equals to zero;

If is on one or more shortest paths of and , in which situations, has a proportional control of communication between and , and intuitively the proportion is the percentage/extent to which is on the shortest paths, given the total shortest paths of and is and the number of falls in the shortest paths is , then we get . As the equation shows below:

To determine the overall centrality of in the graph, we need merely to sum the partial betweenness value of all unordered pair of points {} in the graph:

Scale-free Point Centrality

One problem with the above point centrality is it not point independent/scale-free, it is related to how many points in the graph, thus comparing point centrality defined above with different graphs which may contain different amount of point is meaningless. A concreted example is pointed out that 6 betweenness value in 5 points graph compared with 6 betweenness value in 25 points graph, although they have the same betweenness centrality value but the influence of them is different.

In the later section Freeman introduced a relative point centrality, which is scale free to how many points in the graph, where point centrality is divided by the maximum centrality of their graph.

where is the number of points in the graph, and is only determined by n, which is , therefore we obtain:

To get more information of how is computed, please refer to the paper for details, you can imagine such a point that stands on the shortest path of all other pairs of {}, where and have merely one shortest path, such a graph looks like a star graph, that one point in the central and all others surround it.

Graph Centrality

Freeman defines the graph centrality as the average difference between the most central point and all others, which sounds like a little bit of information entropy, I think.

where is the relative point centrality value of the most central point in the graph.

From the equation, we can see if all the points have the same centrality value then the graph centrality is 0; and if the graph is a star or wheel graph, then graph centrality is 1.