# Betweenness Centrality in Some Classes of Graphs

Authors: Sunil Kumar Raghavan Unnithan; Balakrishnan Kannan; Madambi Jathavedan
Journal: International Journal of Combinatorics
 (2014)

---

## Abstract

There are several centrality measures that have been introduced and studied for real-world networks. They account for the different vertex characteristics that permit them to be ranked in order of importance in the network. Betweenness centrality is a measure of the influence of a vertex over the flow of information between every pair of vertices under the assumption that information primarily flows over the shortest paths between them. In this paper we present betweenness centrality of some important classes of graphs.


---

## Body

## 1. Introduction

Betweenness centrality plays an important role in analysis of social networks [1, 2], computer networks [3], and many other types of network data models [4–9].In the case of communication networks the distance from other units is not the only important property of a unit. What is more important is which units lie on the shortest paths (geodesics) among pairs of other units. Such units have control over the flow of information in the network. Betweenness centrality is useful as a measure of the potential of a vertex for control of communication. Betweenness centrality [10–14] indicates the betweenness of a vertex in a network and it measures the extent to which a vertex lies on the shortest paths between pairs of other vertices. In many real-world situations it has quite a significant role.Determining betweenness is simple and straightforward when only one geodesic connects each pair of vertices, where the intermediate vertices can completely control communication between pairs of others. But when there are several geodesics connecting a pair of vertices, the situation becomes more complicated and the control of the intermediate vertices gets fractionated.


## 2. Background

The concept of betweenness centrality was first introduced by Bavelas in 1948 [15]. The importance of the concept of vertex centrality is in the potential of a vertex for control of information flow in the network. Positions are viewed as structurally central to the degree to which they stand between others and can therefore facilitate, impede, or bias the transmission of messages. Freeman in his papers [5, 16] classified betweenness centrality into three measures. The three measures include two indexes of vertex centrality—one based on counts and one on proportions—and one index of overall network or graph centralization.


### 2.1. Betweenness Centrality of a Vertex

Betweenness centralityCB(v) for a vertex v is defined as
(1)CBv=∑s≠v≠t‍σstvσst,
where σst is the number of shortest paths with vertices s and t as their end vertices, while σst(v) is the number of those shortest paths that include vertex v [16]. High centrality scores indicate that a vertex lies on a considerable fraction of shortest paths connecting pairs of vertices.(i)
Every pair of vertices in a connected graph provides a value lying in[0,1] to the betweenness centrality of all other vertices.(ii)
If there is only one geodesic joining a particular pair of vertices, then that pair provides a betweenness centrality 1 to each of its intermediate vertices and zero to all other vertices. For example, in a path graph, a pair of vertices provides a betweenness centrality 1 to each of its interior vertices and zero to the exterior vertices. A pair of adjacent vertices always provides zero to all others.(iii)
If there arek geodesics of length 2 joining a pair of vertices, then that pair of vertices provides a betweenness centrality 1/k to each of the intermediate vertices.Freeman [16] proved that the maximum value taken by CB(v) is achieved only by the central vertex in a star as the central vertex lies on the geodesic (which is unique) joining every pair of other vertices. In a star Sn with n vertices, the betweenness centrality of the central vertex is therefore the number of such geodesics which is n-12. The betweenness centrality of each pendant vertex is zero since no pendant vertex lies in between any geodesic. Again it can be seen that the betweenness centrality of any vertex in a complete graph Kn is zero since no vertex lies in between any geodesic as every geodesic is of length 1.


### 2.2. Relative Betweenness Centrality

The betweenness centrality increases with the number of vertices in the network, so a normalized version is often considered with the centrality values scaled to between 0 and 1. Betweenness centrality can be normalized by dividingCB(v) by its maximum value. Among all graphs of n vertices the central vertex of a star graph Sn has the maximum value which is n-12. The relative betweenness centrality is therefore defined as
(2)CB′v=CBvMax⁡CBv=2CBvn-1n-20≤CB′v≤1.


### 2.3. Betweenness Centrality of a Graph

The betweenness centrality of a graph measures the tendency of a single vertex to be more central than all other vertices in the graph. It is based on differences between the centrality of the most central vertex and that of all others. Freeman [16] defined the betweenness centrality of a graph as the average difference between the measures of centrality of the most central vertex and that of all other vertices.The betweenness centrality of a graphG is defined as
(3)CBG=∑i=1n‍CBv*-CBviMax⁡∑i=1n‍CBv*-CBvi,
where CB(v*) is the largest value of CB(vi) for any vertex vi in the given graph G and Max⁡∑i=1n‍[CB(v*)-CB(vi)] is the maximum possible sum of differences in centrality for any graph of n vertices which occur in star with the value n-1 times CB(v) of the central vertex, that is, (n-1)n-12.Therefore the betweenness centrality ofG is defined as
(4)CBG=2∑i=1n‍CBv*-CBvin-12n-2orCBG=∑i=1n‍CB′v*-CB′vin-1.
The index, CB(G), determines the degree to which CB(v*) exceeds the centrality of all other vertices in G. Since CB(G) is the ratio of an observed sum of differences to its maximum value, it will vary between 0 and 1. CB(G)=0 if and only if all CB(vi) are equal, and CB(G)=1 if and only if one vertex v* completely dominates the network with respect to centrality. Freeman showed that all of these measures agree in assigning the highest centrality index to the star graph and the lowest to the complete graph (see Table 1).Table 1
Graphs showing extreme betweenness.
G
C
B
(
v
)
C
B
′
(
v
)
C
B
(
G
)
S
n
{
(
n
-
1
2
)
for  central  vertex
0
for  other  vertices
{
1
for  central  vertex
0
for  other  vertices
1
K
n
0
0
0In this paper we present the betweenness centrality measures in some important classes of graphs which are the basic components of larger complex networks.


## 2.1. Betweenness Centrality of a Vertex

Betweenness centralityCB(v) for a vertex v is defined as
(1)CBv=∑s≠v≠t‍σstvσst,
where σst is the number of shortest paths with vertices s and t as their end vertices, while σst(v) is the number of those shortest paths that include vertex v [16]. High centrality scores indicate that a vertex lies on a considerable fraction of shortest paths connecting pairs of vertices.(i)
Every pair of vertices in a connected graph provides a value lying in[0,1] to the betweenness centrality of all other vertices.(ii)
If there is only one geodesic joining a particular pair of vertices, then that pair provides a betweenness centrality 1 to each of its intermediate vertices and zero to all other vertices. For example, in a path graph, a pair of vertices provides a betweenness centrality 1 to each of its interior vertices and zero to the exterior vertices. A pair of adjacent vertices always provides zero to all others.(iii)
If there arek geodesics of length 2 joining a pair of vertices, then that pair of vertices provides a betweenness centrality 1/k to each of the intermediate vertices.Freeman [16] proved that the maximum value taken by CB(v) is achieved only by the central vertex in a star as the central vertex lies on the geodesic (which is unique) joining every pair of other vertices. In a star Sn with n vertices, the betweenness centrality of the central vertex is therefore the number of such geodesics which is n-12. The betweenness centrality of each pendant vertex is zero since no pendant vertex lies in between any geodesic. Again it can be seen that the betweenness centrality of any vertex in a complete graph Kn is zero since no vertex lies in between any geodesic as every geodesic is of length 1.


## 2.2. Relative Betweenness Centrality

The betweenness centrality increases with the number of vertices in the network, so a normalized version is often considered with the centrality values scaled to between 0 and 1. Betweenness centrality can be normalized by dividingCB(v) by its maximum value. Among all graphs of n vertices the central vertex of a star graph Sn has the maximum value which is n-12. The relative betweenness centrality is therefore defined as
(2)CB′v=CBvMax⁡CBv=2CBvn-1n-20≤CB′v≤1.


## 2.3. Betweenness Centrality of a Graph

The betweenness centrality of a graph measures the tendency of a single vertex to be more central than all other vertices in the graph. It is based on differences between the centrality of the most central vertex and that of all others. Freeman [16] defined the betweenness centrality of a graph as the average difference between the measures of centrality of the most central vertex and that of all other vertices.The betweenness centrality of a graphG is defined as
(3)CBG=∑i=1n‍CBv*-CBviMax⁡∑i=1n‍CBv*-CBvi,
where CB(v*) is the largest value of CB(vi) for any vertex vi in the given graph G and Max⁡∑i=1n‍[CB(v*)-CB(vi)] is the maximum possible sum of differences in centrality for any graph of n vertices which occur in star with the value n-1 times CB(v) of the central vertex, that is, (n-1)n-12.Therefore the betweenness centrality ofG is defined as
(4)CBG=2∑i=1n‍CBv*-CBvin-12n-2orCBG=∑i=1n‍CB′v*-CB′vin-1.
The index, CB(G), determines the degree to which CB(v*) exceeds the centrality of all other vertices in G. Since CB(G) is the ratio of an observed sum of differences to its maximum value, it will vary between 0 and 1. CB(G)=0 if and only if all CB(vi) are equal, and CB(G)=1 if and only if one vertex v* completely dominates the network with respect to centrality. Freeman showed that all of these measures agree in assigning the highest centrality index to the star graph and the lowest to the complete graph (see Table 1).Table 1
Graphs showing extreme betweenness.
G
C
B
(
v
)
C
B
′
(
v
)
C
B
(
G
)
S
n
{
(
n
-
1
2
)
for  central  vertex
0
for  other  vertices
{
1
for  central  vertex
0
for  other  vertices
1
K
n
0
0
0In this paper we present the betweenness centrality measures in some important classes of graphs which are the basic components of larger complex networks.


## 3. Betweenness Centrality of Some Classes of Graphs

### 3.1. Betweenness Centrality of Vertices in Wheels

Wheel Graph  Wn. A Wheel graph Wn is obtained by joining a new vertex to every vertex in a cycle Cn-1. It was invented by the eminent graph theorist W. T. Tutte. A wheel graph on 7 vertices is shown in Figure 1.Figure 1
Wheel graphW7.Theorem 1.
The betweenness centrality of a vertexv in a wheel graph Wn, n>5, is given by
(5)CBv=n-1n-52,ifvisthecentralvertex,12,otherwise.Proof.
In the wheel graphWn the central vertex is adjacent to each vertex of the cycle Cn-1. Consider the central vertex of Wn for n>5. On Cn-1 each pair of adjacent vertices contributes centrality 0, each pair of alternate vertices contributes centrality 1/2, and all other pairs contribute centrality 1 to the central vertex. Since there are n-1 vertices on Cn-1, there exist n-1 adjacent pairs, n-1 alternate pairs, and n-12-2(n-1)=(n-1)(n-6)/2 other pairs. Therefore the betweenness centrality of the central vertex is given by 1/2(n-1)+1(n-1)(n-6)/2=(n-1)(n-5)/2. Now for any vertex on Cn-1, there are two geodesics joining its adjacent vertices on Cn-1, one of which passing through it. Therefore the betweenness centrality of any vertex on Cn-1 is 1/2.Note. It can be seen easily that CB(v)=0 for every vertex v in W4 and
(6)CBv=23,ifvisthecentralvertex,13,otherwise
in W5.The relative centrality and graph centrality are as follows:(7)CB′v=2CBvn-1n-2=n-5n-2,ifvisthecentralvertex,1n-1n-2,otherwise,CBWn=∑i=1n‍CB′v*-CB′vin-1=n2-6n+4n-1n-2.


### 3.2. Betweenness Centrality of Vertices in the GraphKn-e

A complete graph on 6 vertices with one edge deleted is shown in Figure2.Figure 2
Complete graphK6-(v1,v4).Theorem 2.
LetKn be a complete graph on n vertices and e=(vi,vj) an edge of it. Then the betweenness centrality of vertices in Kn-e is given by
(8)CB(v)=1n-2,ifv≠vi,vj,0,otherwise.Proof.
Suppose the edge(vi,vj) is removed from Kn. Now vi and vj can be joined by means of any of the remaining n-2 vertices. Thus there are n-2 geodesics joining vi and vj each containing exactly one vertex as intermediary. This provides a betweenness centrality 1/n-2 to each of the n-2 vertices. Again vi and vj do not lie in between any geodesics and therefore their betweenness centralities are zero.The relative centrality and graph centrality are as follows:(9)CB′v=2CBvn-1n-2=2n-1n-22,v≠vi,vj,0,otherwise,CBG=∑i=1n‍CB′v*-CB′vin-1=4n-12n-22.


### 3.3. Betweenness Centrality of Vertices in Complete Bipartite Graphs

Complete Bipartite Graphs  Km,n. A graph is complete bipartite if its vertices can be partitioned into two disjoint nonempty sets V1 and V2 such that two vertices x and y are adjacent if and only if x∈V1 and y∈V2. If V1=m and V2=n, such a graph is denoted Km,n. For example, see K3,4 in Figure 3.Figure 3
Complete bipartite graphK3,4.Theorem 3.
The betweenness centrality of a vertex in a complete bipartite graphKm,n is given by
(10)CBv=1mn2,ifdeg⁡v=n,1nm2,ifdeg⁡v=m.Proof.
Consider a complete bipartite graphKm,n with a bipartition {U,W} where U={u1,u2,…,um} and W={w1,w2,…,wn}. The distance between any two vertices in U (or in W) is 2. Consider a vertex u∈U. Now any pair of vertices in W contributes a betweenness centrality 1/m to u. Since there are n2 pairs of vertices in W,  CB(u)=1/mn2. In a similar way it can be shown that, for any vertex w in W, CB(w)=1/nm2.The relative centrality and graph centrality are as follows:(11)CB′v=2CBvm+n-1m+n-2=2m+n-1m+n-2×1mn2,ifdeg⁡v=n,2m+n-1m+n-2×1nm2,ifdeg⁡v=m,CBKm,n=∑i=1n‍CB′v*-CB′vim+n-1=m3-n3-m2-n2nm+n-12m+n-2,ifm>n,n2n-1-m2m-1mm+n-12m+n-2,ifn>m.


### 3.4. Betweenness Centrality of Vertices in Cocktail Party Graphs

The cocktail party graphCP(n) [17] is a unique regular graph of degree 2n-2 on 2n vertices. It is obtained from K2n by deleting a perfect matching (see Figure 4). The cocktail party graph of order n is a complete n-partite graph with 2 vertices in each partition set. It is the graph complement of the ladder rung graph Ln′ which is the graph union of n copies of the path graph P2 and the dual graph of the hypercube Qn [18].Figure 4
Cocktail party graphCP(3).Theorem 4.
The betweenness centrality of each vertex of a cocktail party graph of order2n is 1/2.Proof.
Let the cocktail party graphCP(n) be obtained from the complete graph K2n with vertices {v1,…,vn,vn+1,…,v2n} by deleting a perfect matching {(v1,vn+1),(v2,vn+2),…,(vn,v2n)}. Now for each pair (vi,vn+i) there is a geodesic of length 2 passing through each of the other 2n-2 vertices. Thus for any particular vertex, there are n-1 pairs of vertices of the above matching not containing that vertex giving a betweenness centrality 1/2n-2 to that vertex. Therefore the betweenness centrality of any vertex is given by n-1/2n-2=1/2.The relative centrality and graph centrality are as follows:(12)CB′v=2CBv2n-12n-2=12n-12n-2,CBG=0.


### 3.5. Betweenness Centrality of Vertices in Crown Graphs

The crown graph [18] is the unique n-1 regular graph with 2n vertices obtained from a complete bipartite graph Kn,n by deleting a perfect matching (see Figure 5). A crown graph on 2n vertices can be viewed as an undirected graph with two sets of vertices ui and vi and with an edge from ui to vj whenever i≠j. It is the graph complement of the ladder graph L2n. The crown graph is a distance-transitive graph.Figure 5
Crown graph with 8 vertices.Theorem 5.
The betweenness centrality of each vertex of a crown graph of order2n is n+1/2.Proof.
Let the crown graph be the complete bipartite graphKn,n with vertices {u1,…,un,v1,…,vn} minus a perfect matching {(u1,v1),(u2,v2),…,(un,vn)}. Consider any vertex; say u1. Now for each pair (ui,vi) other than (u1,v1) there are n-2 paths of length 3 passing through u1 out of (n-1)(n-2) paths joining ui and vi. Since there are n-1 such pairs, they give v1 the betweenness centrality (n-1)×n-2/(n-1)(n-2)=1. Again for each pair from {v2,v3,v4,…,vn} there exists exactly one path passing through v1 out of n-2 paths. Since there are n-12 such pairs, they give v1 the betweenness centrality n-121/n-2=n-1/2. Therefore the betweenness centrality of v1 is given by 1+n-1/2=n+1/2. Since the graph is vertex transitive, the betweenness centrality of any vertex is given by n+1/2.The relative centrality and graph centrality are as follows:(13)CB′v=2CBv2n-12n-2=n+12n-12n-2,CBG=0.


### 3.6. Betweenness Centrality of Vertices in Paths

Theorem 6.
The betweenness centrality of any vertex in a path graph is the product of the number of vertices on either side of that vertex in the path.Proof.
Consider a path graphPn of n vertices {v1,v2,…,vn} (see Figure 6). Take a vertex vk in Pn. Then there are k-1 vertices on one side and n-k vertices on the other side of vk. Consequently there are (k-1)×(n-k) number of geodesics containing vk. Hence CB(vk)=(k-1)(n-k).Figure 6
Path graphPn.Note that, by symmetry, vertices at equal distance away from both ends ofPn have the same centrality and it is maximum at the central vertex (vertices) and minimum at the end vertices. Consider
(14)Max⁡CBvk=nn-24,whenniseven,n-124,whennisodd.Relative centrality of any vertexvk is given by
(15)CB′vk=2CBvkn-1n-2=2k-1n-kn-1n-2.Corollary 7.
Graph centrality ofPn is given by
(16)CBPn=nn+16n-1n-2,ifnisodd,nn+26n-12,ifniseven.Proof.
Whenn is even, by definition
(17)CBPn=2n-12n-2∑i=1n‍CBv*-CBvi=4n-12n-2×nn-24-0+nn-24-1·n-2+⋯+nn-24-n-42n-n-22=4n-12n-2×nn-24×n-22-1(n-2)+2n-3+⋯+n-42n-n-22+⋯+n-42n-n-22=4n-12n-2×nn-228-n∑k=1n-4/2‍k+∑k=1n-4/2‍kk+1=4n-12n-2×nn-228-nn-2n-48nn-228-nn-2n-48+n-2n-48+n-2n-3n-424=1n-12×nn-22-nn-42+n-42+n-3n-46=nn+26n-12.
When n is odd, by definition
(18)CBPn=2n-12n-2∑i=1n‍CBv*-CBvi=4n-12n-2×n-124-0+n-124-1·n-2+⋯+n-124-n-32n-n-12=4n-12n-2×n-124×n-12-1(n-2)+2(n-3)n-32n-n-12+⋯+n-32n-n-12n-124×n-12=4n-12n-2×n-138-n∑k=1n-3/2‍k+∑k=1n-3/2‍kk+1=4n-12n-2×n-138-nn-1n-38n-138-nn-1n-38+n-1n+1n-324=1n-1n-2×n-122-nn-32+n+1n-36=nn+16n-1n-2.


### 3.7. Betweenness Centrality of Vertices in Ladder Graphs

The ladder graphLn [19, 20] is defined as the Cartesian product P2×Pn (see Figure 7). It is a planar undirected graph with 2n vertices and n+2(n-1) edges.Figure 7
Ladder graphL5.Theorem 8.
The betweenness centrality of a vertex in a ladder graphLn is given by
(19)CBvk=k-1n-k+∑j=0k-1‍∑i=1n-k‍k-jk-j+i+∑j=0k-2‍∑i=0n-k‍i+1k-j+i,1≤k≤n.Proof.
By symmetry, letvk be any vertex such that 1≤k≤n+1/2. Consider the paths (in Figure 8) from upper left vertices {v1,…,vk-1} to upper right vertices {vk+1,…,vn} which give the betweenness centrality
(20)k-1n-k.
Now consider the paths from lower left vertices{vn+1,…,vn+k} to the upper right vertices {vk+1,…,vn} of vk which give the betweenness centrality
(21)k1k+1+1k+2+⋯+1nk-11k+1k+1+⋯+1n-1⋮12+13+⋯+1n-k-1=∑j=0k-1‍∑i=1n-k‍k-jk-j+i.
Again consider the paths from upper left vertices{v1,…,vk-1} to the lower right vertices {vn+k,…,v2n} of vk which give the betweenness centrality
(22)1k+2k+1+⋯+n-k-1n1k-1+2k+⋯+n-k-1n-1⋮12+23+⋯+n-k-1n-k-2=∑j=0k-2‍∑i=0n-k‍i+1k-j+i.
The above three equations when combined get the result.Figure 8
Ladder graphLn.


### 3.8. Betweenness Centrality of Vertices in Cycles

Theorem 9.
The betweenness centrality of a vertex in a cycleCn is given by
(23)CBv=n-228,ifniseven,n-1n-38,ifnisodd.Proof.
Case
1 (when
n
is even). Let n=2k,  k∈Z+, and let Cn=(v1,v2,…,v2k) be the given cycle. Consider a vertex v1 (see Figure 9). Then vk+1 is its antipodal vertex and there is no geodesic from vk+1 to any other vertex passing through v1. Hence we omit the pair (v1,vk+1). Consider other pairs of antipodal vertices (vi,vk+i) for i=2,3,…,k. For each pair of these antipodal vertices there exist two paths of the same length k and one of them contains v1. Thus each pair contributes 1/2 to the centrality of v1 which gives a total of 1/2(k-1). Now consider all paths of length less than k containing v1. There are k-i paths joining vi to vertices from v2k to vk+1+i passing through v1 for i=2,3,…,k-1 and each contributes centrality 1 to v1 giving a total ∑i=2k-1‍(k-i)=(k-1)(k-2)/2. Therefore the betweenness centrality of v1 is (1/2)(k-1)+k-1k-2/2=(1/2)(k-1)2=(1/8)(n-2)2. Since Cn is vertex transitive, the betweenness centrality of any vertex is given by (1/8)(n-2)2.
Case
2 (when
n
is odd). Let n=2k+1, k∈Z+, and let Cn=(v1,v2,…,v2k+1) be the given cycle. Consider a vertex v1 (see Figure 10). Then vk+1 and vk+2 are its antipodal vertices at a distance k from v1 and there is no geodesic path from the vertexes vk+1 and vk+2 to any other vertex passing through v1. Hence we omit v1 and the pair (vk+1,vk+2). Now consider paths of length ≤k passing through v1. There are k+1-i paths joining vi to vertices from v2k+1 to vk+1+i passing through v1 for i=2,3,…,k and each contributes a betweenness centrality 1 to v1 giving a total of ∑i=2k‍(k+1-i)=k(k-1)/2=(n-1)(n-3)/8. Since Cn is vertex transitive, the betweenness centrality of any vertex is given by n-1n-3/8.Figure 9
Even cycle with2k vertices.Figure 10
Odd cycle with2k+1 vertices.The relative centrality and graph centrality are as follows:(24)CB′v=CBvMax⁡CBv=2CBvn-1n-2=n-24n-1,ifniseven,n-34n-2,ifnisodd,CBCn=0.


### 3.9. Betweenness Centrality of Vertices in Circular Ladder GraphsCLn

The circular ladder graphCLn consists of two concentric n-cycles in which each pair of the n corresponding vertices is joined by an edge (see Figure 11). It is a 3-regular simple graph isomorphic to the Cartesian product K2×Cn.Figure 11
Circular ladder.Theorem 10.
The betweenness centrality of a vertex in a circular ladderCLn is given by
(25)CBv=n-12+14,whenniseven,n-124,whennisodd.Proof.
Case
1 (when
n
is even). Let n=2k, k∈Z+. Let C2k=(u1,u2,…,u2k) be the outer cycle and C2k′=(v1,v2,…,v2k) the inner cycle. Consider any vertex; say u1 in C2k. Then its betweenness centrality as a vertex in C2k is (k-1)2/2. Now the geodesics from outer vertices ui to the inner vertices v1,v2k,…,vk+i for i=2,…,k (see Figure 12) and from u2k+2-i to v1,v2,…,vk+2-i for i=2,…,k by symmetry contribute to u1 the betweenness centrality
(26)2∑i=2k‍1i+2i+1+⋯+k+1-ik+k+2-i2k+2=212+1+23+⋯+1+2+⋯+k-1kkkkkkik+2+3+⋯+k2k+2=2∑p=2k‍1+2+⋯+p-1p+kk+1-22k+1=2∑p=2k‍p-12+kk+1-22k+1=k22-1k+1.
Again the pair (uk+1,v1) contributes to u1 the betweenness centrality 2/2k+2. Therefore the betweenness centrality of u1 is given as
(27)CBu1=k-122+k22-1k+1+1k+1=k-122+k22=2k-12+14=n-12+14.
Case
2 (when
n
is odd). Let n=2k+1,  k∈Z+. Let C2k+1=(u1,u2,…,u2k+1) be the outer cycle and C2k+1′=(v1,v2,…,v2k+1) the inner cycle. Consider any vertex; say u1 in C2k+1. Then its betweenness centrality as a vertex in C2k+1 is k(k-1)/2. Now consider the geodesics from outer vertices ui to the inner vertices v1,v2k+1,…,vk+i+1 for i=2,…,k+1 (see Figure 13) and from u2k+3-i to v1,v2,…,vk+2-i for i=2,3,…,k+1 which give a betweenness centrality
(28)2∑i=2k‍1i+2i+1+⋯+k+2-ik+1=212+1+23+⋯+1+2+⋯+kk+1=2∑p=2k+1‍1+2+⋯+p-1p=2∑p=2k+1‍p-12=kk+12.
Therefore the betweenness centrality of u1 is given as
(29)CBu1=kk-12+kk+12=k2=n-124.Figure 12
Circular ladderCL2k.Figure 13
Circular ladderCL2k+1.The relative centrality and graph centrality are as follows:(30)CB′v=2CBv2n-12n-2=n-12+122n-12n-2,whenniseven,n-142n-1,whennisodd,CBG=0.


### 3.10. Betweenness Centrality of Vertices in Trees

In a tree, there is exactly one path between any two vertices. Therefore the betweenness centrality of a vertex is the number of paths passing through that vertex. A branch at a vertexv of a tree T is a maximal subtree containing v as an end vertex. The number of branches at v is deg⁡(v).Theorem 11.
The betweenness centralityCB(v) of a vertex v in a tree T is given by
(31)Cn1,n2,…,nk=∑i<j‍ninj,
where the arguments ni denote the number of vertices of the branches at v excluding v, taken in any order.Proof.
Consider a vertexv in a tree T. Let there be k branches with number of vertices n1,n2,…,nk excluding v. The betweenness centrality of v in T is the total number of paths passing through v. Since all the branches have only one vertex v in common, excluding v, every path joining a pair of vertices of different branches passes through v. Thus the total number of such pairs gives the betweenness centrality of v. Hence C=∑i<j‍ninj.Example 12.
Consider the tree given in Figure14.Figure 14
A tree with 7 vertices.Here(32)CBv1=CBv4=CBv6=CBv7=C6=0,CBv2=C1,3,2=11,CBv3=C5,1=5,CBv5=C1,1,4=9.Example 13.
Table2 gives the possible values for the betweenness centrality of a vertex in a tree of 9 vertices.Table 2
Possible values for betweenness centrality in a tree of 9 vertices.
Number of args.
Possible combinations
Values
8
C
(
1,1
,
1,1
,
1,1
,
1,1
)
28
7
C
(
2,1
,
1,1
,
1,1
,
1
)
27
6
C
(
2,2
,
1,1
,
1,1
)
26
C
(
3,1
,
1,1
,
1,1
)
25
5
C
(
2,2
,
2,1
,
1
)
25
C
(
3,2
,
1,1
,
1
)
24
C
(
4,1
,
1,1
,
1
)
22
4
C
(
2,2
,
2,2
)
24
C
(
3,2
,
2,1
)
23
C
(
3,3
,
1,1
)
22
C
(
5,1
,
1,1
)
18
C
(
4,2
,
1,1
)
21
3
C
(
3,3
,
2
)
21
C
(
4,2
,
2
)
20
C
(
4,3
,
1
)
19
C
(
5,2
,
1
)
17
C
(
6,1
,
1
)
13
2
C
(
4,4
)
16
C
(
5,3
)
15
C
(
6,2
)
12
C
(
7,1
)
7
1
C
(
8
)
0We consider the different possible combinations of the arguments inC so that the sum of arguments is 8.


### 3.11. Betweenness Centrality of Vertices in Hypercubes

Then-cube or n-dimensional hypercube Qn is defined recursively by Q1=K2 and Qn=K2×Qn-1. That is, Qn=(K2)n Harary [21]. Qn is an n-regular graph containing 2n vertices and n2n-1 edges. Each vertex can be labeled as a string of n bits 0 and 1. Two vertices of Qn are adjacent if their binary representations differ at exactly one place (see Figure 15). The 2n vertices are labeled by the 2n binary numbers from 0 to 2n-1. By definition, the length of a path between two vertices u and v is the number of edges of the path. To move from u to v it suffices to cross successively the vertices whose labels are those obtained by changing the bits of u one by one in order to transform u into v. If u and v differ only in i bits, the distance (hamming distance) between u and v denoted by d(u,v) is i [22, 23]. For example, if u=(101010) and v=(110011), then d(u,v)=3.Figure 15
Hypercubes.There exists a path of length at mostn between any two vertices of Qn. In other words an n-cube is a connected graph of diameter n. The number of geodesics between u and v is given by the number of permutations  d(u,v)!. A hypercube is bipartite and interval regular. For any two vertices u and v, the interval I(u,v) induces a hypercube of dimension d(u,v) [24]. Another important property of n-cube is that it can be constructed recursively from lower dimensional cubes (see Figure 15). Consider two identical (n-1)-cubes. Each (n-1)-cube has 2n-1 vertices and each vertex has a labeling of (n-1)-bits. Join all identical pairs of vertices of the two cubes. Now increase the number of bits in the labels of all vertices by placing 0 in the ith place of the first cube and 1 in the ith place of second cube. Thus we get an n-cube with 2n vertices, each vertex having a label of n-bits and the corresponding vertices of the two (n-1)-cubes differ only in the ith bit. This n-cube so constructed can be seen as the union of n pairs of (n-1)-cubes differing in exactly one position of bits. Thus the number of (n-1)-cubes in an n-cube is 2n. The operation of splitting an n-cube into two disjoint (n-1)-cubes so that the vertices of the two (n-1)-cubes are in a one-to-one correspondence will be referred to as tearing [23]. Since there are n bits, there are n directions for tearing. In general there are nk2n-k number of k-subcubes associated with an n-cube.Theorem 14.
The betweenness centrality of a vertex in a hypercubeQn is given by 2n-2(n-2)+1/2.Proof.
The hypercubeQn of dimension n is a vertex transitive n-regular graph containing 2n vertices. Each vertex can be written as an n tuple of binary digits 0 and 1 with adjacent vertices differing in exactly one coordinate. The distance between two vertices x and y denoted by (x,y) is the number of places in which the corresponding coordinates of x and y differ and the number of distinct geodesics between x and y is d(x,y)! [22]. Let 0=(0,0,…,0) be a vertex in Qn whose betweenness centrality has to be determined. Consider all k-subcubes containing the vertex 0 for 2≤k≤n. Each k-subcube has vertices with n-k zeros in their labels. Since each k-subcube can be distinguished by k coordinates, the number of k-subcubes containing the vertex 0 is nk. The vertex 0 lies on a geodesic joining a pair of vertices if and only if the pair of vertices forms a pair of antipodal vertices of some subcube containing 0 [24]. So we consider all pairs of antipodal vertices excluding the vertex 0 and its antipodal vertex in each k-subcube containing 0. If a vertex of a k-subcube has r ones, then its antipodal vertex has k-r ones. For any pair of such antipodal vertices there are k! geodesics joining them and of that r!(k-r)! paths are passing through 0. Thus each pair contributes r!(k-r)!/k!, that is, 1/kr, to the betweenness centrality of 0.
By symmetry, whenk is even the number of distinct pairs of required antipodal vertices are given by kr for 1≤r<k/2 and 1/2kr for r=k/2. When k is odd, the number of distinct pairs of required antipodal vertices is given by kr for 1≤r≤k-1/2. Taking all such pairs of antipodal vertices in a k-subcube we get the contribution of betweenness centrality as ∑r=1k/2-1‍kr1/kr+1/2kk/21/kk/2=k-1/2, when k is even, and ∑r=1k-1/2‍kr1/kr=k-1/2, when k is odd. Therefore considering all k-subcubes for 2≤k≤n, we get the betweenness centrality of 0 as
(33)CB0=∑k=2n‍k-12nk=12∑k=2n‍knk-∑k=2n‍nk=2n-2n-2+12.
Therefore, for any vertex v,
(34)CBv=2n-2n-2+12.The relative centrality and graph centrality are as follows:(35)CB′v=2CBv2n-12n-2=2n-1n-2+12n-12n-2,CBG=0.


## 3.1. Betweenness Centrality of Vertices in Wheels

Wheel Graph  Wn. A Wheel graph Wn is obtained by joining a new vertex to every vertex in a cycle Cn-1. It was invented by the eminent graph theorist W. T. Tutte. A wheel graph on 7 vertices is shown in Figure 1.Figure 1
Wheel graphW7.Theorem 1.
The betweenness centrality of a vertexv in a wheel graph Wn, n>5, is given by
(5)CBv=n-1n-52,ifvisthecentralvertex,12,otherwise.Proof.
In the wheel graphWn the central vertex is adjacent to each vertex of the cycle Cn-1. Consider the central vertex of Wn for n>5. On Cn-1 each pair of adjacent vertices contributes centrality 0, each pair of alternate vertices contributes centrality 1/2, and all other pairs contribute centrality 1 to the central vertex. Since there are n-1 vertices on Cn-1, there exist n-1 adjacent pairs, n-1 alternate pairs, and n-12-2(n-1)=(n-1)(n-6)/2 other pairs. Therefore the betweenness centrality of the central vertex is given by 1/2(n-1)+1(n-1)(n-6)/2=(n-1)(n-5)/2. Now for any vertex on Cn-1, there are two geodesics joining its adjacent vertices on Cn-1, one of which passing through it. Therefore the betweenness centrality of any vertex on Cn-1 is 1/2.Note. It can be seen easily that CB(v)=0 for every vertex v in W4 and
(6)CBv=23,ifvisthecentralvertex,13,otherwise
in W5.The relative centrality and graph centrality are as follows:(7)CB′v=2CBvn-1n-2=n-5n-2,ifvisthecentralvertex,1n-1n-2,otherwise,CBWn=∑i=1n‍CB′v*-CB′vin-1=n2-6n+4n-1n-2.


## 3.2. Betweenness Centrality of Vertices in the GraphKn-e

A complete graph on 6 vertices with one edge deleted is shown in Figure2.Figure 2
Complete graphK6-(v1,v4).Theorem 2.
LetKn be a complete graph on n vertices and e=(vi,vj) an edge of it. Then the betweenness centrality of vertices in Kn-e is given by
(8)CB(v)=1n-2,ifv≠vi,vj,0,otherwise.Proof.
Suppose the edge(vi,vj) is removed from Kn. Now vi and vj can be joined by means of any of the remaining n-2 vertices. Thus there are n-2 geodesics joining vi and vj each containing exactly one vertex as intermediary. This provides a betweenness centrality 1/n-2 to each of the n-2 vertices. Again vi and vj do not lie in between any geodesics and therefore their betweenness centralities are zero.The relative centrality and graph centrality are as follows:(9)CB′v=2CBvn-1n-2=2n-1n-22,v≠vi,vj,0,otherwise,CBG=∑i=1n‍CB′v*-CB′vin-1=4n-12n-22.


## 3.3. Betweenness Centrality of Vertices in Complete Bipartite Graphs

Complete Bipartite Graphs  Km,n. A graph is complete bipartite if its vertices can be partitioned into two disjoint nonempty sets V1 and V2 such that two vertices x and y are adjacent if and only if x∈V1 and y∈V2. If V1=m and V2=n, such a graph is denoted Km,n. For example, see K3,4 in Figure 3.Figure 3
Complete bipartite graphK3,4.Theorem 3.
The betweenness centrality of a vertex in a complete bipartite graphKm,n is given by
(10)CBv=1mn2,ifdeg⁡v=n,1nm2,ifdeg⁡v=m.Proof.
Consider a complete bipartite graphKm,n with a bipartition {U,W} where U={u1,u2,…,um} and W={w1,w2,…,wn}. The distance between any two vertices in U (or in W) is 2. Consider a vertex u∈U. Now any pair of vertices in W contributes a betweenness centrality 1/m to u. Since there are n2 pairs of vertices in W,  CB(u)=1/mn2. In a similar way it can be shown that, for any vertex w in W, CB(w)=1/nm2.The relative centrality and graph centrality are as follows:(11)CB′v=2CBvm+n-1m+n-2=2m+n-1m+n-2×1mn2,ifdeg⁡v=n,2m+n-1m+n-2×1nm2,ifdeg⁡v=m,CBKm,n=∑i=1n‍CB′v*-CB′vim+n-1=m3-n3-m2-n2nm+n-12m+n-2,ifm>n,n2n-1-m2m-1mm+n-12m+n-2,ifn>m.


## 3.4. Betweenness Centrality of Vertices in Cocktail Party Graphs

The cocktail party graphCP(n) [17] is a unique regular graph of degree 2n-2 on 2n vertices. It is obtained from K2n by deleting a perfect matching (see Figure 4). The cocktail party graph of order n is a complete n-partite graph with 2 vertices in each partition set. It is the graph complement of the ladder rung graph Ln′ which is the graph union of n copies of the path graph P2 and the dual graph of the hypercube Qn [18].Figure 4
Cocktail party graphCP(3).Theorem 4.
The betweenness centrality of each vertex of a cocktail party graph of order2n is 1/2.Proof.
Let the cocktail party graphCP(n) be obtained from the complete graph K2n with vertices {v1,…,vn,vn+1,…,v2n} by deleting a perfect matching {(v1,vn+1),(v2,vn+2),…,(vn,v2n)}. Now for each pair (vi,vn+i) there is a geodesic of length 2 passing through each of the other 2n-2 vertices. Thus for any particular vertex, there are n-1 pairs of vertices of the above matching not containing that vertex giving a betweenness centrality 1/2n-2 to that vertex. Therefore the betweenness centrality of any vertex is given by n-1/2n-2=1/2.The relative centrality and graph centrality are as follows:(12)CB′v=2CBv2n-12n-2=12n-12n-2,CBG=0.


## 3.5. Betweenness Centrality of Vertices in Crown Graphs

The crown graph [18] is the unique n-1 regular graph with 2n vertices obtained from a complete bipartite graph Kn,n by deleting a perfect matching (see Figure 5). A crown graph on 2n vertices can be viewed as an undirected graph with two sets of vertices ui and vi and with an edge from ui to vj whenever i≠j. It is the graph complement of the ladder graph L2n. The crown graph is a distance-transitive graph.Figure 5
Crown graph with 8 vertices.Theorem 5.
The betweenness centrality of each vertex of a crown graph of order2n is n+1/2.Proof.
Let the crown graph be the complete bipartite graphKn,n with vertices {u1,…,un,v1,…,vn} minus a perfect matching {(u1,v1),(u2,v2),…,(un,vn)}. Consider any vertex; say u1. Now for each pair (ui,vi) other than (u1,v1) there are n-2 paths of length 3 passing through u1 out of (n-1)(n-2) paths joining ui and vi. Since there are n-1 such pairs, they give v1 the betweenness centrality (n-1)×n-2/(n-1)(n-2)=1. Again for each pair from {v2,v3,v4,…,vn} there exists exactly one path passing through v1 out of n-2 paths. Since there are n-12 such pairs, they give v1 the betweenness centrality n-121/n-2=n-1/2. Therefore the betweenness centrality of v1 is given by 1+n-1/2=n+1/2. Since the graph is vertex transitive, the betweenness centrality of any vertex is given by n+1/2.The relative centrality and graph centrality are as follows:(13)CB′v=2CBv2n-12n-2=n+12n-12n-2,CBG=0.


## 3.6. Betweenness Centrality of Vertices in Paths

Theorem 6.
The betweenness centrality of any vertex in a path graph is the product of the number of vertices on either side of that vertex in the path.Proof.
Consider a path graphPn of n vertices {v1,v2,…,vn} (see Figure 6). Take a vertex vk in Pn. Then there are k-1 vertices on one side and n-k vertices on the other side of vk. Consequently there are (k-1)×(n-k) number of geodesics containing vk. Hence CB(vk)=(k-1)(n-k).Figure 6
Path graphPn.Note that, by symmetry, vertices at equal distance away from both ends ofPn have the same centrality and it is maximum at the central vertex (vertices) and minimum at the end vertices. Consider
(14)Max⁡CBvk=nn-24,whenniseven,n-124,whennisodd.Relative centrality of any vertexvk is given by
(15)CB′vk=2CBvkn-1n-2=2k-1n-kn-1n-2.Corollary 7.
Graph centrality ofPn is given by
(16)CBPn=nn+16n-1n-2,ifnisodd,nn+26n-12,ifniseven.Proof.
Whenn is even, by definition
(17)CBPn=2n-12n-2∑i=1n‍CBv*-CBvi=4n-12n-2×nn-24-0+nn-24-1·n-2+⋯+nn-24-n-42n-n-22=4n-12n-2×nn-24×n-22-1(n-2)+2n-3+⋯+n-42n-n-22+⋯+n-42n-n-22=4n-12n-2×nn-228-n∑k=1n-4/2‍k+∑k=1n-4/2‍kk+1=4n-12n-2×nn-228-nn-2n-48nn-228-nn-2n-48+n-2n-48+n-2n-3n-424=1n-12×nn-22-nn-42+n-42+n-3n-46=nn+26n-12.
When n is odd, by definition
(18)CBPn=2n-12n-2∑i=1n‍CBv*-CBvi=4n-12n-2×n-124-0+n-124-1·n-2+⋯+n-124-n-32n-n-12=4n-12n-2×n-124×n-12-1(n-2)+2(n-3)n-32n-n-12+⋯+n-32n-n-12n-124×n-12=4n-12n-2×n-138-n∑k=1n-3/2‍k+∑k=1n-3/2‍kk+1=4n-12n-2×n-138-nn-1n-38n-138-nn-1n-38+n-1n+1n-324=1n-1n-2×n-122-nn-32+n+1n-36=nn+16n-1n-2.


## 3.7. Betweenness Centrality of Vertices in Ladder Graphs

The ladder graphLn [19, 20] is defined as the Cartesian product P2×Pn (see Figure 7). It is a planar undirected graph with 2n vertices and n+2(n-1) edges.Figure 7
Ladder graphL5.Theorem 8.
The betweenness centrality of a vertex in a ladder graphLn is given by
(19)CBvk=k-1n-k+∑j=0k-1‍∑i=1n-k‍k-jk-j+i+∑j=0k-2‍∑i=0n-k‍i+1k-j+i,1≤k≤n.Proof.
By symmetry, letvk be any vertex such that 1≤k≤n+1/2. Consider the paths (in Figure 8) from upper left vertices {v1,…,vk-1} to upper right vertices {vk+1,…,vn} which give the betweenness centrality
(20)k-1n-k.
Now consider the paths from lower left vertices{vn+1,…,vn+k} to the upper right vertices {vk+1,…,vn} of vk which give the betweenness centrality
(21)k1k+1+1k+2+⋯+1nk-11k+1k+1+⋯+1n-1⋮12+13+⋯+1n-k-1=∑j=0k-1‍∑i=1n-k‍k-jk-j+i.
Again consider the paths from upper left vertices{v1,…,vk-1} to the lower right vertices {vn+k,…,v2n} of vk which give the betweenness centrality
(22)1k+2k+1+⋯+n-k-1n1k-1+2k+⋯+n-k-1n-1⋮12+23+⋯+n-k-1n-k-2=∑j=0k-2‍∑i=0n-k‍i+1k-j+i.
The above three equations when combined get the result.Figure 8
Ladder graphLn.


## 3.8. Betweenness Centrality of Vertices in Cycles

Theorem 9.
The betweenness centrality of a vertex in a cycleCn is given by
(23)CBv=n-228,ifniseven,n-1n-38,ifnisodd.Proof.
Case
1 (when
n
is even). Let n=2k,  k∈Z+, and let Cn=(v1,v2,…,v2k) be the given cycle. Consider a vertex v1 (see Figure 9). Then vk+1 is its antipodal vertex and there is no geodesic from vk+1 to any other vertex passing through v1. Hence we omit the pair (v1,vk+1). Consider other pairs of antipodal vertices (vi,vk+i) for i=2,3,…,k. For each pair of these antipodal vertices there exist two paths of the same length k and one of them contains v1. Thus each pair contributes 1/2 to the centrality of v1 which gives a total of 1/2(k-1). Now consider all paths of length less than k containing v1. There are k-i paths joining vi to vertices from v2k to vk+1+i passing through v1 for i=2,3,…,k-1 and each contributes centrality 1 to v1 giving a total ∑i=2k-1‍(k-i)=(k-1)(k-2)/2. Therefore the betweenness centrality of v1 is (1/2)(k-1)+k-1k-2/2=(1/2)(k-1)2=(1/8)(n-2)2. Since Cn is vertex transitive, the betweenness centrality of any vertex is given by (1/8)(n-2)2.
Case
2 (when
n
is odd). Let n=2k+1, k∈Z+, and let Cn=(v1,v2,…,v2k+1) be the given cycle. Consider a vertex v1 (see Figure 10). Then vk+1 and vk+2 are its antipodal vertices at a distance k from v1 and there is no geodesic path from the vertexes vk+1 and vk+2 to any other vertex passing through v1. Hence we omit v1 and the pair (vk+1,vk+2). Now consider paths of length ≤k passing through v1. There are k+1-i paths joining vi to vertices from v2k+1 to vk+1+i passing through v1 for i=2,3,…,k and each contributes a betweenness centrality 1 to v1 giving a total of ∑i=2k‍(k+1-i)=k(k-1)/2=(n-1)(n-3)/8. Since Cn is vertex transitive, the betweenness centrality of any vertex is given by n-1n-3/8.Figure 9
Even cycle with2k vertices.Figure 10
Odd cycle with2k+1 vertices.The relative centrality and graph centrality are as follows:(24)CB′v=CBvMax⁡CBv=2CBvn-1n-2=n-24n-1,ifniseven,n-34n-2,ifnisodd,CBCn=0.


## 3.9. Betweenness Centrality of Vertices in Circular Ladder GraphsCLn

The circular ladder graphCLn consists of two concentric n-cycles in which each pair of the n corresponding vertices is joined by an edge (see Figure 11). It is a 3-regular simple graph isomorphic to the Cartesian product K2×Cn.Figure 11
Circular ladder.Theorem 10.
The betweenness centrality of a vertex in a circular ladderCLn is given by
(25)CBv=n-12+14,whenniseven,n-124,whennisodd.Proof.
Case
1 (when
n
is even). Let n=2k, k∈Z+. Let C2k=(u1,u2,…,u2k) be the outer cycle and C2k′=(v1,v2,…,v2k) the inner cycle. Consider any vertex; say u1 in C2k. Then its betweenness centrality as a vertex in C2k is (k-1)2/2. Now the geodesics from outer vertices ui to the inner vertices v1,v2k,…,vk+i for i=2,…,k (see Figure 12) and from u2k+2-i to v1,v2,…,vk+2-i for i=2,…,k by symmetry contribute to u1 the betweenness centrality
(26)2∑i=2k‍1i+2i+1+⋯+k+1-ik+k+2-i2k+2=212+1+23+⋯+1+2+⋯+k-1kkkkkkik+2+3+⋯+k2k+2=2∑p=2k‍1+2+⋯+p-1p+kk+1-22k+1=2∑p=2k‍p-12+kk+1-22k+1=k22-1k+1.
Again the pair (uk+1,v1) contributes to u1 the betweenness centrality 2/2k+2. Therefore the betweenness centrality of u1 is given as
(27)CBu1=k-122+k22-1k+1+1k+1=k-122+k22=2k-12+14=n-12+14.
Case
2 (when
n
is odd). Let n=2k+1,  k∈Z+. Let C2k+1=(u1,u2,…,u2k+1) be the outer cycle and C2k+1′=(v1,v2,…,v2k+1) the inner cycle. Consider any vertex; say u1 in C2k+1. Then its betweenness centrality as a vertex in C2k+1 is k(k-1)/2. Now consider the geodesics from outer vertices ui to the inner vertices v1,v2k+1,…,vk+i+1 for i=2,…,k+1 (see Figure 13) and from u2k+3-i to v1,v2,…,vk+2-i for i=2,3,…,k+1 which give a betweenness centrality
(28)2∑i=2k‍1i+2i+1+⋯+k+2-ik+1=212+1+23+⋯+1+2+⋯+kk+1=2∑p=2k+1‍1+2+⋯+p-1p=2∑p=2k+1‍p-12=kk+12.
Therefore the betweenness centrality of u1 is given as
(29)CBu1=kk-12+kk+12=k2=n-124.Figure 12
Circular ladderCL2k.Figure 13
Circular ladderCL2k+1.The relative centrality and graph centrality are as follows:(30)CB′v=2CBv2n-12n-2=n-12+122n-12n-2,whenniseven,n-142n-1,whennisodd,CBG=0.


## 3.10. Betweenness Centrality of Vertices in Trees

In a tree, there is exactly one path between any two vertices. Therefore the betweenness centrality of a vertex is the number of paths passing through that vertex. A branch at a vertexv of a tree T is a maximal subtree containing v as an end vertex. The number of branches at v is deg⁡(v).Theorem 11.
The betweenness centralityCB(v) of a vertex v in a tree T is given by
(31)Cn1,n2,…,nk=∑i<j‍ninj,
where the arguments ni denote the number of vertices of the branches at v excluding v, taken in any order.Proof.
Consider a vertexv in a tree T. Let there be k branches with number of vertices n1,n2,…,nk excluding v. The betweenness centrality of v in T is the total number of paths passing through v. Since all the branches have only one vertex v in common, excluding v, every path joining a pair of vertices of different branches passes through v. Thus the total number of such pairs gives the betweenness centrality of v. Hence C=∑i<j‍ninj.Example 12.
Consider the tree given in Figure14.Figure 14
A tree with 7 vertices.Here(32)CBv1=CBv4=CBv6=CBv7=C6=0,CBv2=C1,3,2=11,CBv3=C5,1=5,CBv5=C1,1,4=9.Example 13.
Table2 gives the possible values for the betweenness centrality of a vertex in a tree of 9 vertices.Table 2
Possible values for betweenness centrality in a tree of 9 vertices.
Number of args.
Possible combinations
Values
8
C
(
1,1
,
1,1
,
1,1
,
1,1
)
28
7
C
(
2,1
,
1,1
,
1,1
,
1
)
27
6
C
(
2,2
,
1,1
,
1,1
)
26
C
(
3,1
,
1,1
,
1,1
)
25
5
C
(
2,2
,
2,1
,
1
)
25
C
(
3,2
,
1,1
,
1
)
24
C
(
4,1
,
1,1
,
1
)
22
4
C
(
2,2
,
2,2
)
24
C
(
3,2
,
2,1
)
23
C
(
3,3
,
1,1
)
22
C
(
5,1
,
1,1
)
18
C
(
4,2
,
1,1
)
21
3
C
(
3,3
,
2
)
21
C
(
4,2
,
2
)
20
C
(
4,3
,
1
)
19
C
(
5,2
,
1
)
17
C
(
6,1
,
1
)
13
2
C
(
4,4
)
16
C
(
5,3
)
15
C
(
6,2
)
12
C
(
7,1
)
7
1
C
(
8
)
0We consider the different possible combinations of the arguments inC so that the sum of arguments is 8.


## 3.11. Betweenness Centrality of Vertices in Hypercubes

Then-cube or n-dimensional hypercube Qn is defined recursively by Q1=K2 and Qn=K2×Qn-1. That is, Qn=(K2)n Harary [21]. Qn is an n-regular graph containing 2n vertices and n2n-1 edges. Each vertex can be labeled as a string of n bits 0 and 1. Two vertices of Qn are adjacent if their binary representations differ at exactly one place (see Figure 15). The 2n vertices are labeled by the 2n binary numbers from 0 to 2n-1. By definition, the length of a path between two vertices u and v is the number of edges of the path. To move from u to v it suffices to cross successively the vertices whose labels are those obtained by changing the bits of u one by one in order to transform u into v. If u and v differ only in i bits, the distance (hamming distance) between u and v denoted by d(u,v) is i [22, 23]. For example, if u=(101010) and v=(110011), then d(u,v)=3.Figure 15
Hypercubes.There exists a path of length at mostn between any two vertices of Qn. In other words an n-cube is a connected graph of diameter n. The number of geodesics between u and v is given by the number of permutations  d(u,v)!. A hypercube is bipartite and interval regular. For any two vertices u and v, the interval I(u,v) induces a hypercube of dimension d(u,v) [24]. Another important property of n-cube is that it can be constructed recursively from lower dimensional cubes (see Figure 15). Consider two identical (n-1)-cubes. Each (n-1)-cube has 2n-1 vertices and each vertex has a labeling of (n-1)-bits. Join all identical pairs of vertices of the two cubes. Now increase the number of bits in the labels of all vertices by placing 0 in the ith place of the first cube and 1 in the ith place of second cube. Thus we get an n-cube with 2n vertices, each vertex having a label of n-bits and the corresponding vertices of the two (n-1)-cubes differ only in the ith bit. This n-cube so constructed can be seen as the union of n pairs of (n-1)-cubes differing in exactly one position of bits. Thus the number of (n-1)-cubes in an n-cube is 2n. The operation of splitting an n-cube into two disjoint (n-1)-cubes so that the vertices of the two (n-1)-cubes are in a one-to-one correspondence will be referred to as tearing [23]. Since there are n bits, there are n directions for tearing. In general there are nk2n-k number of k-subcubes associated with an n-cube.Theorem 14.
The betweenness centrality of a vertex in a hypercubeQn is given by 2n-2(n-2)+1/2.Proof.
The hypercubeQn of dimension n is a vertex transitive n-regular graph containing 2n vertices. Each vertex can be written as an n tuple of binary digits 0 and 1 with adjacent vertices differing in exactly one coordinate. The distance between two vertices x and y denoted by (x,y) is the number of places in which the corresponding coordinates of x and y differ and the number of distinct geodesics between x and y is d(x,y)! [22]. Let 0=(0,0,…,0) be a vertex in Qn whose betweenness centrality has to be determined. Consider all k-subcubes containing the vertex 0 for 2≤k≤n. Each k-subcube has vertices with n-k zeros in their labels. Since each k-subcube can be distinguished by k coordinates, the number of k-subcubes containing the vertex 0 is nk. The vertex 0 lies on a geodesic joining a pair of vertices if and only if the pair of vertices forms a pair of antipodal vertices of some subcube containing 0 [24]. So we consider all pairs of antipodal vertices excluding the vertex 0 and its antipodal vertex in each k-subcube containing 0. If a vertex of a k-subcube has r ones, then its antipodal vertex has k-r ones. For any pair of such antipodal vertices there are k! geodesics joining them and of that r!(k-r)! paths are passing through 0. Thus each pair contributes r!(k-r)!/k!, that is, 1/kr, to the betweenness centrality of 0.
By symmetry, whenk is even the number of distinct pairs of required antipodal vertices are given by kr for 1≤r<k/2 and 1/2kr for r=k/2. When k is odd, the number of distinct pairs of required antipodal vertices is given by kr for 1≤r≤k-1/2. Taking all such pairs of antipodal vertices in a k-subcube we get the contribution of betweenness centrality as ∑r=1k/2-1‍kr1/kr+1/2kk/21/kk/2=k-1/2, when k is even, and ∑r=1k-1/2‍kr1/kr=k-1/2, when k is odd. Therefore considering all k-subcubes for 2≤k≤n, we get the betweenness centrality of 0 as
(33)CB0=∑k=2n‍k-12nk=12∑k=2n‍knk-∑k=2n‍nk=2n-2n-2+12.
Therefore, for any vertex v,
(34)CBv=2n-2n-2+12.The relative centrality and graph centrality are as follows:(35)CB′v=2CBv2n-12n-2=2n-1n-2+12n-12n-2,CBG=0.


## 4. Conclusion

Betweenness centrality is a useful metric for analyzing graph structures. When compared to other centrality measures, computation of betweenness centrality is rather difficult as it involves calculation of the shortest paths between all pairs of vertices in a graph. We have derived expressions for betweenness centrality of graphs which are the basic components of larger and complex networks. This study is therefore helpful for analysing larger classes of graphs.



---

*Source: 241723-2014-12-25.xml*