ISSN 2148-838Xhttp://dx.doi.org/10.13069/jacodesmath.508983 J. Algebra Comb. Discrete Appl. 6(1) • 21–38 Received: 9 May 2017 Accepted: 26 August 2018 0 Journal of Algebra Combinatorics Discrete Structures and Applications Betweenness centrality in convex amalgamation of graphs∗ Research Article Sunil Kumar Raghavan Unnithan, Kannan Balakrishnan Abstract: Betweenness centrality measures the potential or power of a node to control the communication over the network under the assumption that information flows primarily over the shortest paths between pair of nodes. The removal of a node with highest betweenness from the network will most disrupt communications between other nodes because it lies on the largest number of paths. A large network can be thought of as inter-connection between smaller networks by means of different graph operations. Thus the structure of a composite graph can be studied by analysing its component graphs. In this paper we present the betweenness centrality of some classes of composite graphs constructed by the graph operation called amalgamation or merging. 2010 MSC: 05C75, 05C76, 05C85 Keywords: Betweenness centrality, Central vertex, Extreme vertex, Convex subgraph, Vertex amalgamation, Edge amalgamation, Path amalgamation, Subgraph amalgamation. 1. Introduction A large network can be thought of as inter-connection between smaller networks by means of different graph operations. Graph operations are important for constructing new classes of composite graphs and many of the structural properties of larger graphs can be derived from their component graphs. There are many operations on two graphs G1 and G2 which result in a larger graph G. In this paper we define some betweenness centrality concepts, and derive the betweenness centrality for some classes of composite graphs constructed by the graph operation subgraph-amalgamation. ∗ This work was supported by the University Grants Commission (UGC), Government of India under the scheme of Faculty Development Programme (FDP) for colleges. Sunil Kumar Raghavan Unnithan (Corresponding Author), Kannan Balakrishnan; Department of Computer Applications, Cochin University of Science and Technology, Kerala, India (email: sunilstands@gmail.com, mul- layilkannan@gmail.com). 21 https://orcid.org/0000-0002-8254-6511 S. Kumar, K. Balakrishnan / J. Algebra Comb. Discrete Appl. 6(1) (2019) 21–38 2. Some betweenness centrality concepts The concept of betweenness centrality of a vertex was first introduced by Bavelas in 1948 [1]. Definition 2.1. [3]. Let G be a graph and x ∈ V (G), then the betweenness centrality of x in G, denoted by BG(x) or simply B(x) is defined as BG(x) = ∑ s,t∈V (G)\{x} σst(x) σst where σst(x) denotes the number of shortest s-t paths in G passing through x and σst, the total number of shortest s-t paths in G. The ratio σst(x) σst is called pair dependency or partial betweenness of (s, t) on x, denoted by δG(s, t, x). Betweenness centrality of some well known graphs has been studied in [7] and we use the following definitions [8]. 2.1. Betweenness centrality of a vertex in a subgraph Definition 2.2. Let G be a graph and H a subgraph of G. Let x ∈ V (H), then the betweenness centrality of x in H denoted by BH(x) is defined as BH(x) = ∑ s,t∈V (H)\{x} σHst(x) σHst where σHst(x) and σ H st denotes the number of shortest s-t paths passing through x and the total number of shortest s-t paths respectively, lying in H. 2.2. Betweenness centrality of a vertex induced by a subgraph Definition 2.3. Let G be a graph and H a subgraph of G. Let x ∈ V (G), then the betweenness centrality of x induced by H denoted by B(x, H) is defined as B(x, H) = ∑ s,t( ̸=x)∈V (H) σst(x) σst where σst(x) and σst denotes the number of shortest s-t paths passing through x and the total number of shortest s-t paths respectively in G. The betweenness centrality of a vertex induced by a subset S ⊂ V (G) is defined likewise. 2.3. Betweenness centrality of a vertex induced by a subset Definition 2.4. Let G be a graph and S a subset of V (G). Let x ∈ V (G), then the betweenness centrality of x induced by S denoted by B(x, S) is defined as B(x, S) = ∑ s,t( ̸=x)∈S σst(x) σst where σst(x) and σst denotes the number of shortest s-t paths passing through x and the total number of shortest s-t paths respectively in G. 22 S. Kumar, K. Balakrishnan / J. Algebra Comb. Discrete Appl. 6(1) (2019) 21–38 2.4. Betweenness centrality of a vertex induced by another vertex Definition 2.5. Let G be a graph and s, x, t ∈ V (G), then the betweenness centrality of x induced by s in G, denoted by BG(x, s) or simply B(x, s) is defined by BG(x, s) = ∑ t∈V (G)\x σst(x) σst . It can be easily seen that in any graph G, the betweenness centrality induced by a vertex on its extreme vertex or an end vertex is zero. Consider the following examples. B(xi, xj) = 0 for xi, xj ∈ Kn. Let Pn be a path on n vertices {x1, . . . , xn}, then B(xi, xj) = { i − 1, if i < j, n − i, if j < i. If Cn is a cycle on n vertices {x0, . . . , xn−1}, then if n is even, B(xi, x0) = { n−1−2i 2 , if 1 ≤ d(xi, x0) < n/2, 0, if d(xi, x0) = n/2, if n is odd, B(xi, x0) = n − 1 − 2i 2 , if 1 ≤ d(xi, x0) ≤ n − 1 2 . For a star Sn with central vertex x0, B(xi, x0) = 0, B(x0, xi) = n − 2 and (1) B(xi, xj) = 0 for i, j ̸= 0. (2) For a wheel Wn, n > 5 with central vertex x0, B(xi, x0) = 0, B(x0, xi) = n − 5. For i, j ̸= 0, B(xi, xj) = { 1/2, if d(xi, xj) = 1, 0, if d(xi, xj) = 2. It can be easily seen that for xi ∈ V (G), BG(xi) = 12 ∑ j ̸=i BG(xi, xj). 2.5. Betweenness centrality donated by a vertex Definition 2.6. Let G be a graph and x0 ∈ V (G), then the betweenness centrality donated by x0 in G, denoted by DBG(x0) or simply DB(x0), is defined as the sum of betweenness values induced by x0 on all other vertices in G, i.e., DBG(x0) = ∑ x∈V (G)\x0 BG(x, x0). The betweenness centrality received by a vertex, RBG(x0) is BG(x0) by definition. 23 S. Kumar, K. Balakrishnan / J. Algebra Comb. Discrete Appl. 6(1) (2019) 21–38 2.6. Betweenness centrality of a vertex induced by two disjoint subsets Definition 2.7. Let G be a graph and x ∈ V (G). Let S, T be two disjoint subsets of V (G), then the betweenness centrality of x induced by S and T denoted by B(x, S, T) is defined as B(x, S, T) = B(x, S) + B(x, T). 2.7. Betweenness centrality of a vertex induced by two disjoint subsets, one against the other Definition 2.8. Let G be a graph and x ∈ V (G). Let S, T be two disjoint subsets of V (G) where s(̸= x) ∈ S and t(̸= x) ∈ T , then the betweenness centrality of x induced by S against T , denoted by B(x, S|T) is defined as B(x, S|T) = ∑ s∈S, t∈T σst(x) σst where σst(x) and σst denotes the number of shortest s-t paths passing through x and the total number of shortest s-t paths respectively in G. In metric graph theory, a convex subgraph of an undirected graph G is a subgraph that includes every shortest path in G between two of its vertices. A subgraph H of a graph G is an isometric subgraph, if dH(u, v) = dG(u, v) for all u, v ∈ V (H). Clearly, a convex subgraph is an isometric subgraph, but the converse need not be true. 3. Subgraph-amalgamation One method of constructing composite graphs is merging or pasting two or more graphs together along a common subgraph. For any finite collection of graphs Gi, each with a fixed isomorphic subgraph H as common, the subgraph-amalgamation is the graph obtained by taking the union of all the Gi and identifying their fixed subgraphs H’s. The simplest one is vertex-amalgamation or vertex-merging. Theorem 3.1. Let G be the graph obtained by merging the graphs {Gi}ni=1 along n copies of isomorphic induced common convex subgraph H where H ⊂ Gi ∀i. Let Si = V (Gi − H) ∀i. Then, for x ∈ H and u ∈ Gk − H, BG(x) = n∑ i=1 BGi(x) − (n − 1)BH(x) + ∑ i α. Case 2: Both Cm and Cn are odd. 27 S. Kumar, K. Balakrishnan / J. Algebra Comb. Discrete Appl. 6(1) (2019) 21–38 Consider uα and uβ, a pair of extreme vertices of the end vertices xp and x1 of P where α = m+1 2 − p + 1 and β = m−1 2 and vδ and vγ be their eccentric vertices in C′ where δ = n−12 , γ = n+1 2 − p + 1. If ui ∈ U and vj ∈ V , then for xr ∈ P where 1 < r < p, {(ui, vj) : 1 ≤ i < α, δ < j ≤ n−p } or {(ui, vj) : β < i ≤ m−p, 1 ≤ j < γ} contributes the sum ( m+1 2 −p )( n+1 2 −p ) . Since there exists no more pair, B(xr, U|V ) = 2 ( m+1 2 −p )( n+1 2 −p ) . Consider the vertex x1. Now the pairs {(ui, vj) : 1 ≤ i < α, 1 ≤ j ≤ n − p} contributes the sum ( m+1 2 − p ) (n − p). The vertices {ui : α ≤ i ≤ β} contributes the sum 1 2 (n−p)(p−1) and the pairs {(ui, vj) : β < i ≤ m−p, 1 ≤ j ≤ n+12 −p} contributes the sum ( m+1 2 −p )( n+1 2 −p ) . Hence B(x1, U|V ) = ( m+1 2 −p )( n+1 2 −p ) +(n−p) ( m+p 2 −p ) . Consider the vertex ur, 1 ≤ r < α, the vertices lying between ur and uα contributes the sum (α − r − 1)(n − p), vertices from uα to uβ as given above and no vertex from the right. Hence B(ur, U|V ) = ( m+1 2 − p − r ) (n − p) + 1 2 (n − p)(p − 1) for 1 ≤ r < α. For uα, the vertices from uα+1 to uβ contributes 12(p − 2)(n − p − 1). Hence B(uα, U|V ) = 1 2 (p − 2)(n − p − 1). Consider a vertex on the left of uα, say uα+k, then no vertex on the right of uα is considered. The vertices from uα to uα+k−1 contributes 12k(n + k − 2p + 1) and the vertices from uα+k+1 to uβ contribute 1 2 (p − k − 2)(n − p − k − 1) and no more vertex from the right. Hence, B(uα+k, U|V ) = 1 2 k(n + k − 2p + 1) + 1 2 (p − k − 2)(n − p − k − 1). b b b b bbb b bb b b b b b b b u1uα v1x1 xp vγ uβ vδum−p vn−p Cm CnPpp − 2 p − 3 m 2 − p n+1 2 − p m 2 − p n+1 2 − p Figure 3. Even and odd cycles merged along a common subgraph Case 3: Cm is even and Cn is odd. Let uα and uβ where α = m2 − p + 1, β = m 2 be the eccentric vertices in Cm for the end vertices xp, x1 of P and vδ and vγ be their eccentric vertices in C′ where δ = n−12 , γ = n+1 2 − p + 1. See Figure 3. Consider xr ∈ P such that 1 < r < p. If ui ∈ U and vj ∈ V , then for each pair {(ui, vj) : 1 ≤ i < α, δ < j ≤ n − p or β < i ≤ m − p, 1 ≤ j < γ} there exists a geodesic passing through xr and contributes the sum (m 2 − p) ( n+1 2 − p ) and 1 2 ( n+1 2 − p ) for i = α. Since there exists no such other pair, B(xr, U|V ) = 12(m − 2p + 1)(n − 2p + 1). Consider the vertex x1. Now {(ui, vj) : 1 ≤ i < α, 1 ≤ j ≤ n−p} contributes the sum (m2 −p)(n−p). {(uα, vj) : 1 ≤ j ≤ δ} and {(uα, vj) : δ < j ≤ n − p} contributes the sum n−12 + 1 2 ( n+1 2 − p ) . {(uβ, vj) : 1 ≤ j ≤ γ − 1} contributes the sum n+12 − p. The vertices lying between uα and uβ contributes the sum 1 2 (n − p)(p − 2) and each vertex on the right of uβ gives the sum n+12 − p. The total of these sums gives B(x1, U|V ) which is 14 [ 3mn − (4p − 1)(m + n) + 6p2 − 4p + 1 ] . Consider the vertex ur, for 1 ≤ r < α. Now the vertices lying between ur and uα contributes the sum (α − r − 1)(n − p). Again uα and the vertices lying between uα and uβ have the same contribution as mentioned above, uβ gives 12 ( n+1 2 − p ) . For the vertex uα, vertices from uα+1 to uβ−1 and then uβ contributes to it as earlier. Consider a vertex on the right of uα, say uα+k. Again uα and uβ contributes the same as 12 ( n+1 2 − p ) . The vertices lying between uα and uα+k contribute (k − 1) ( n+1 2 − p ) + 1 2 k(k − 1). The vertices lying between uα+k and uβ contribute 1 2 (n − p − k)(p − k − 2). The sum of these gives B(uα+k, U|V ). Consider the vertex vr in Cn for 28 S. Kumar, K. Balakrishnan / J. Algebra Comb. Discrete Appl. 6(1) (2019) 21–38 1 ≤ r < γ. The vertices lying between vr and vγ offers (n+12 −p−r)(m−p) and the vertices from vγ to vδ offers (p−1)(m−p)/2 giving B(vr, U|V ) = (m−p)(n−p−2r)/2. For vγ, the vertices from vγ+1 to vδ gives B(vγ, U|V ) = 1/2[m(p−2)−p2+p+2]. For vγ+k, 1 ≤ k ≤ p−2, the vertices from vγ+k+1 to vδ offers 12(p−k−2)(m−p−k−1) and vertices from vγ to vγ+k−1 offers k 2 (m+k−2+1) so that vertices symmetric from vγ and vδ offers the same giving B(vγ+k, U|V ) = k(k−p+2)+(p/2)(m−p+1)−m+1. Corollary 3.7. Let G be the graph obtained by merging m copies of cycle Cn along a common path Pp = {x1, . . . , xp} as common subgraph where p < ⌈n2 ⌉ and U = {u1, . . . , un−p} be the vertex sets of Cn − Pp. Then the betweenness centrality of Cn in G is given by BG(xr) = mBCn(xr) − (m − 1)(r − 1)(p − r) + ( m 2 ) B(xr, U|V ), for xr ∈ Pp, BG(ur) = BCn(ur) + (m − 1)B(ur, U|V ), for ur ∈ U. where B(xr, U|V ) and B(ur, U|V ) are given by Case 1: If Cn is even, then B(xr, U|V ) = { n2/2 − 2n(p − 1/2) + 2(p2 − p + 1/3), for 1 < r < p, 3n2/4 − 2n(p − 1/4) + (9p2 − 6p + 2)/6, for r = 1, p. B(ur, U|V ) =   (n − p)(n − p − 2r)/2, for 1 ≤ r ≤ n 2 − p, n(2p − 3)/4 − (3p2 − 3p − 2)/6, for r = n 2 − p + 1, k(k − p + 1) + (n − p)(p − 2)/2 + 1/6, for r = n 2 − p + 1 + k, 1 ≤ k ≤ p − 2. Case 2: If Cn is odd, then B(xr, U|V ) = { 2 [ (n + 1)/2 − p ]2 , for 1 < r < p, 3n2/4 − 2n(p − 1/4) + (6p2 − 4p + 1)/4, for r = 1, p. B(ur, U|V ) =   (n − p)(n − p − 2r)/2, for 1 ≤ r ≤ n+1 2 − p, (p − 2)(n − p − 1)/2, for r = n+1 2 − p + 1, k(k − p + 2) + (p − 2)(n − p − 1)/2, for r = n+1 2 − p + 1 + k, 1 ≤ k ≤ p − 2. Proposition 3.8. Let G be the graph obtained by merging both ends of m copies of paths Pn together where V (Pn) = {1, 2, . . . , n}. Then the betweenness centrality of G is given by B(r) = { 1 4 m(m − 1)(n − 2)2, for r = 1, n, 1 2 (n − 1)(n − 3) + 1 m + (m−2) 2 [ (n − 1 − r)2 + (r − 2)2 ] , for 1 < r < n. Proof. Since the ends of m copies of path Pn are separately merged, any two copies of Pn form an even cycle C2n−2 in G. Since there are ( m 2 ) such cycles, B(r) = ( m 2 ) BC2n−2(r) = 1 4 m(m − 1)(n − 2)2 for r = 1, n. Consider an internal vertex of any path Pn say P (i) n . Now P (i) n and P (j) n for i ̸= j form a cycle of 2n − 2 vertices in G, where the pair of end vertices gives the centrality 1 m instead of 1 2 . Consider the path P (k)n where k ̸= j ̸= i. Let Ui and Uk denotes the vertex sets of P (i) n−2 and P (k) n−2 respectively where the merged end vertices 1 and n are deleted. Therefore, for any internal vertex r of Pn, BG(r) = BC2n−2(r) − 1 2 + 1 m + ∑ k ̸=i ̸=j B(r, Ui|Uk) = 1 2 (n − 1)(n − 3) + 1 m + (m − 2) 2 [ (n − 1 − r)2 + (r − 2)2 ] 29 S. Kumar, K. Balakrishnan / J. Algebra Comb. Discrete Appl. 6(1) (2019) 21–38 since, B(r, Ui, |Uk) = [ n − (r + 1) ]2 2 + 1 2 [1 + 3 + . . . (r − 2) terms] = 1 2 [ (n − 1 − r)2 + (r − 2)2 ] . 3.2. Edge-amalgamation of graphs The edge amalgamation of {Gi}ni=1 is the graph obtained by taking the union of all the Gi and identifying their fixed edges. An amalgamation of two edges e1 = u1v1 of a graph G1 and e2 = u2v2 of a graph G2 is a graph created by identifying u1 with u2 and v1 with v2 and then deleting one of the two edges corresponding to e1 or e2. The other edge will be called the amalgamated edge. The edge amalgamation of cycles are called generalized books [5]. Proposition 3.9. Let two cycles Cm and Cn are connected by merging a pair of edges. Let ui, vi be any vertices on Cm and Cn respectively at a distance i from the merged edge. Then betweenness centrality of the resulting graph is given by Case 1: If both Cm and Cn are even, then B(ui) =   (m−2)2 8 + (n−2)2 8 + (m−3)(n−3) 4 + (m−2)(n−2) 2 + 1 12 , for i = 0, (m−2)2 8 + (n−2)(m−2−2i) 2 , for 1 ≤ i < m 2 − 1, (m−2)2 8 + n 4 − 2 3 , for i = m 2 − 1. B(vi) are obtained on interchanging m and n. Case 2: If both Cm and Cn are odd (See Figure 4), then B(ui) =   (m−1)(m−3) 8 + (n−1)(n−3) 8 + (m−3)(n−3) 4 + (m−2)(n−2) 2 , for i = 0, (m−1)(m−3) 8 + (n−2)(m−2−2i) 2 , for 1 ≤ i < m−1 2 , (m−1)(m−3) 8 , for i = m−1 2 . B(vi) are obtained on interchanging m and n. Case 3: If Cm is even and Cn is odd, then B(ui) =   (m−2)2 8 + (n−1)(n−3) 8 + (m−3)(n−3) 4 + (m−2)(n−2) 2 , for i = 0, (m−2)2 8 + (n−2)(m−2−2i) 2 , for 1 ≤ i < m 2 − 1, (m−2)2 8 + n 4 − 2 3 , for i = m 2 − 1. B(vi) = { (n−1)(n−3) 8 + (m − 2)(n − 2 − 2i)/2, for 1 ≤ i < n−1 2 , (n−1)(n−3) 8 , for i = n−1 2 . 30 S. Kumar, K. Balakrishnan / J. Algebra Comb. Discrete Appl. 6(1) (2019) 21–38 b b b b b b b b b b bb b bbb b b b b bb ui ui u m−1 2 v n−1 2 vi vi Cm Cn Figure 4. Two odd cycles Cm and Cn identifying a pair of edges Proof. Consider a merged vertex. Since the merged vertex lies on both cycles Cm and Cn, each cycle induces a value for its betweenness centrality. Cm against Cn also induces a value. The betweenness centrality of merged vertex is their sum. For any other vertex u, it lies on one of the cycle and betweenness centrality is the sum of the betweenness centrality induced by that cycle and the other one on it. Corollary 3.10. Let the odd cycles Cn1, . . . , Cnm share a common edge. Then, for u0, an end vertex of the common edge and ui, a vertex in Cnk at a distance i from the common edge, we have B(u0) = 1 8 ∑ i (ni − 1)(ni − 3) + 1 4 ∑ i