Betweenness centrality in Cartesian product of graphs

Betweenness centrality in Cartesian product of graphs

Available online at www.sciencedirect.com ScienceDirect AKCE International Journal of Graphs and Combinatorics xxx (xxxx) xxx www.elsevier.com/locate...

349KB Sizes 0 Downloads 5 Views

Available online at www.sciencedirect.com

ScienceDirect AKCE International Journal of Graphs and Combinatorics xxx (xxxx) xxx www.elsevier.com/locate/akcej

Betweenness centrality in Cartesian product of graphs Sunil Kumar R. ∗,1 , Kannan Balakrishnan Department of Computer Applications, Cochin University of Science and Technology, India Received 19 April 2018; accepted 15 March 2019 Available online xxxx

Abstract Betweenness centrality is a widely used measure in various graphs and it has a pivotal role in the analysis of complex networks. It measures the potential or power of a node to control the communication over the network. The computation is based on the assumption that information primarily flows over the shortest paths between the nodes of the network. In a graph, the power of a vertex is not an individual attribute, it depends on the influence of other vertices present. Betweenness centrality measures the extent to which a vertex becomes part of the shortest paths between pairs of other vertices in a graph. In this paper, we establish expression for betweenness centrality in Cartesian product of graphs. And investigate the same on certain graphs such as grid, Hamming graphs, hypercubes, Cartesian product of cycles etc. c 2019 Kalasalingam University. Production and Hosting by Elsevier B.V. This is an open access article under the CC BY-NC-ND ⃝ license (http://creativecommons.org/licenses/by-nc-nd/4.0/). Keywords: Betweenness centrality; Pairwise dependency; Cartesian product; Geodetic graph

1. Introduction Several centrality measures have so far been studied and their importance is increasing day by day. Betweenness centrality has a vital role in the analysis of networks. [1–4] It has many applications in a variety of domains such as biological networks [5–9], study of sexual networks and AIDS [10], identifying key actors in terrorist networks [11], transportation networks [12], supply chain management [13], bio-informatics–protein interaction networks [14,15], food webs [16] etc. Betweenness centrality [17,18] indicates the betweenness of a vertex (or an edge) in a network and it measures the extent to which a vertex (or an edge) lies on the shortest paths between pairs of other vertices. It is quite difficult to find out the betweenness centrality of a vertex in a large graph. The computation of this index based on direct application of definition becomes impractical when the number of vertices n is huge since it has complexity in the order of O(n 3 ). The fastest exact algorithm due to Brandes [19] requires O(n + m) space and O(nm) time where n is the number of vertices and m the number of edges in the graph. Exact computations of betweenness centrality can take a lot of time. But a large network can be thought of as it is made by joining smaller networks together. There are several graph operations which results in a larger graph and hence many of Peer review under responsibility of Kalasalingam University. Corresponding author. E-mail addresses: [email protected] (Sunil Kumar R.), [email protected] (K. Balakrishnan). 1 The work of the author is supported by the University Grants Commission (UGC), Government of India, under the scheme of Faculty Development Programme (FDP) for colleges. ∗

https://doi.org/10.1016/j.akcej.2019.03.012 c 2019 Kalasalingam University. Production and Hosting by Elsevier B.V. This is an open access article under the CC BY-NC-ND 0972-8600/⃝ license (http://creativecommons.org/licenses/by-nc-nd/4.0/).

Please cite this article as: Sunil Kumar R. and K. Balakrishnan, Betweenness centrality in Cartesian product of graphs, AKCE International Journal of Graphs and Combinatorics (2019), https://doi.org/10.1016/j.akcej.2019.03.012.

2

Sunil Kumar R. and K. Balakrishnan / AKCE International Journal of Graphs and Combinatorics xxx (xxxx) xxx

the properties of larger graphs can be derived from its constituent subgraphs. Graph operations are helpful for constructing new classes of composite graphs. Cartesian product is an important graph operation. It is assumed that the graphs under consideration are simple undirected connected graphs. 2. Background The concept of betweenness centrality of a vertex was first introduced by Bavelas in 1948 [20]. The importance of the concept of vertex centrality lies on how a vertex acts as a bridge among pairs of vertices in joining them by shortest paths. It gives the potential of a vertex for control of information flow in the network [21,22]. The following terminology is used. The order of a graph G, denoted by |G|, is the number of vertices in G. i.e., |G| = |V (G)|. The distance between two vertices u, v ∈ V (G), denoted by dG (u, v), is the length of any shortest u-v path in G. A shortest u-v path is also called a u-v geodesic. A graph G is a geodetic graph [23] if every pair of vertices of G is connected by a unique shortest path. The diameter, diam(G), of a graph G is given by max{d(u, v)|u, v ∈ V (G)}. Two vertices u and v of G satisfying d(u, v) = diam(G) are extreme vertices [24]. For a connected graph G and u, v ∈ G, the interval IG (u, v) between u and v is defined as the set of vertices that lie on shortest u-v paths; that is, IG (u, v) = {w ∈ G : d(u, v) = d(u, w) + d(w, v)} A graph G is vertex-transitive if every vertex in G can be mapped to any other vertex by some automorphism. A subgraph U of a graph G is isometric in G if dU (u, v) = dG (u, v) for all u, v ∈ U . A subgraph U of a graph G is (geodesically)convex in G if U contains all u-v geodesics of G for u, v ∈ U . A definition to betweenness centrality of a vertex in a graph G, given by Freeman [25] is as follows Definition 2.1 (Betweenness Centrality). If x ∈ V (G), the betweenness centrality B(x) for x is defined as ∑ B(x) = δ(u, v|x) {u,v}⊆V (G) u̸=v̸=x

where where δ(u, v|x) is called the pair-dependency of the pair {u, v} on x. It is defined as δ(u, v|x) = σσ(u,v|x) (u,v) σ (u, v) is the number of shortest u-v paths and σ (u, v|x) is the number of shortest u-v paths containing x. Observe that x ∈ V (G) lies on the shortest u-v path iff d(u, v) = d(u, x) + d(x, v). The number of shortest u-v paths passing through x is given by σ (u, v|x) = σ (u, x) × σ (x, v) Definition 2.2 (Cartesian Product, [26]). The Cartesian product of two graphs G and H , denoted by G□H , is a graph with vertex set V (G) × V (H ), where two vertices (g, h) and (g ′ , h ′ ) are adjacent if g = g ′ and hh ′ ∈ E(H ), or gg ′ ∈ E(G) and h = h ′ . The graphs G and H are called factors of the product G□H . For any h ∈ V (H ), the subgraph of G□H induced by V (G) × {h} is called G-fiber or G-layer, denoted by G h . Similarly, we can define H -fiber or H -layer. They are isomorphic to G and H respectively. G□H contains |H | copies of G and |G| copies of H . Projections are the maps from a product graph to its factors. They are weak homomorphisms in the sense that they respect adjacency. The two projections on G□H namely pG : G□H → G and p H : G□H → H defined by pG (g, h) = g and p H (g, h) = h refer to the corresponding G-, H - coordinates. Thus an edge in G□H is mapped into a single vertex by one of the projections pG or p H and mapped into an edge by the other. If G and H are connected, then G□H is also connected. Furthermore, the minimum degree denoted by δ(G) is additive under Cartesian products, i.e. δ(G□H ) = δ(G) + δ(H ). Assuming isomorphic graphs are equal, Cartesian product is commutative as well as associative. Lemma 2.1 ([27]). Let G and H be connected graphs. Then all G-fibers and H -fibers are convex subgraphs of G□H . k Definition 2.3 (Cartesian Product of Several Graphs, [27]). The Cartesian product G = □i=1 G i of graphs G 1 , G 2 , . . . , G k is defined on the k-tuples (v1 , v2 , . . . , vk ), where vi ∈ G i , 1 ≤ i ≤ k in such a way that two k-tuples (u 1 , u 2 , . . . , u k ) and (v1 , v2 , . . . , vk ) are adjacent if there exists an index l such that [u l , vl ] ∈ E(G l ) and u i = vi for i ̸= l. The k-tuple (v1 , v2 , . . . , vk ) is called coordinate vector, and the vi are the coordinates.

Please cite this article as: Sunil Kumar R. and K. Balakrishnan, Betweenness centrality in Cartesian product of graphs, AKCE International Journal of Graphs and Combinatorics (2019), https://doi.org/10.1016/j.akcej.2019.03.012.

Sunil Kumar R. and K. Balakrishnan / AKCE International Journal of Graphs and Combinatorics xxx (xxxx) xxx

3

k The Cartesian product G = G 1 □G 2 □ . . . □G k of k-factors is briefly denoted as G = □i=1 G i . The nth Cartesian n n product of a graph G is denoted as G = □i=1 G. It is to be noted that the product G is connected if and only if ∑k k each of its factor G i is connected and the diameter of the product is given by, diam(□i=1 G i ) = i=1 diam(G i ). k Proposition 2.1 ([28]). The Cartesian product G = □i=1 G i is vertex-transitive, if G i is vertex-transitive for each i = 1, 2, . . . , n

The following proposition shows that the distance between two vertices in the product graph is the sum of the distance between their projections in the factor graphs. Lemma 2.2 ([29]). If (g, h) and (g ′ , h ′ ) are vertices of a Cartesian product G□H , then [ ] dG□H (g, h), (g ′ , h ′ ) = dG (g, g ′ ) + d H (h, h ′ )

(1)

This can be generalized to the following lemma. k Lemma 2.3 (Distance Lemma [29]). Let G be the Cartesian product G = □i=1 G i of connected graphs, and let g = (g1 , . . . , gk ) and g ′ = (g1′ , . . . , gk′ ) be vertices of G. Then

dG (g, g ′ ) =

k ∑

dG i (gi , gi′ )

i=1

[ ] Lemma 2.2 implies that dG□H (g, h), (g ′ , h) = dG h (g, h), (g ′ , h). In other words, dG□H restricted to G h is dG h . It means that every shortest path in a G-fiber (or H -fiber) ia also a shortest path in G□H . Consider the following betweenness property of vertices in product graph. Proposition 2.2 ([27]). Let v1 = (g1 , h 1 ) and v2 = (g2 , h 2 ) be two vertices of G□H , then the vertex v3 = (g3 , h 3 ) lies in IG□H (v1 , v2 ) if and only if g3 ∈ IG (g1 , g2 ) and h 3 ∈ I H (h 1 , h 2 ). It can be generalized as the following k Proposition 2.3 ([27]). Let G = □i=1 G i . Let g(g1 , g2 , . . . , gk ), g ′ (g1′ , g2′ , . . . , gk′ ) and g ′′ (g1′′ , g2′′ , . . . , gk′′ ) be any three vertices in G. Then g ′′ ∈ IG (g, g ′ ) if and only if gi′′ ∈ IG i (gi , gi′ ) ∀i.

3. The betweenness centrality of vertices in Cartesian product of graphs The following proposition shows how the number of geodesics between two vertices u and v in a product graph G□H is related to the number of geodesics between their projections in the factor graphs. Proposition 3.1. If u = (g, h) and v = (g ′ , h ′ ) are vertices in G□H , then the number of shortest u-v paths in G□H is given by ( ) [ ] dG (g, g ′ ) + d H (h, h ′ ) σG□H (g, h), (g ′ , h ′ ) = σG (g, g ′ ) × σ H (h, h ′ ) × (2) dG (g, g ′ ) Proof. Consider the vertices u = (g, h) and v = (g ′ , h ′ ) in G□H . Let d = d(u, v) denote the distance between u and v in G□H . Suppose there exist unique shortest paths between g and g ′ in G and h and h ′ in H . A shortest path from u to v is a sequence of d edges and the image of each edge under the projections pG and p H is an edge lying between g and g ′ or h and h ′ . If the sequence of d edges of the u-v path in G□H makes a sequence of dG edges in G and a sequence of d H edges in H , then d = dG + d H . Since dG and d H are the same for any shortest u-v path, the number of shortest paths ( ) between u and v in G□H is the number of ways of selecting dG edges (or d H edges) from d edges which is ddG . If there exist σG shortest paths between g and g ′ in G and σ H shortest paths ( ) between h and h ′ in H , then corresponding to each pair, there exist ddG shortest paths between u and v in G□H . [ ] ( ′ )+d (h,h ′ )) H Therefore, σG□H (g, h), (g ′ , h ′ ) = σG (g, g ′ ) × σ H (h, h ′ ) × dG (g,g ′ d G (g,g ) (dG□H ) For brevity, we may write σG□H = σG × σ H × dG □ Please cite this article as: Sunil Kumar R. and K. Balakrishnan, Betweenness centrality in Cartesian product of graphs, AKCE International Journal of Graphs and Combinatorics (2019), https://doi.org/10.1016/j.akcej.2019.03.012.

4

Sunil Kumar R. and K. Balakrishnan / AKCE International Journal of Graphs and Combinatorics xxx (xxxx) xxx

Corollary 3.1. If G and H are geodetic graphs, then the number of shortest paths between (g, h) and (g ′ , h ′ ) in G□H is given by ( ) [ ] dG (g, g ′ ) + d H (h, h ′ ) ′ ′ σG□H (g, h), (g , h ) = dG (g, g ′ ) By the associativity of □, Eq. (2) can be generalized as k Proposition 3.2. Let G = □i=1 G ni . If u ∑ = (u 1 , u 2 , . . . , u k ), v = (v1 , v2 , . . . , vk ) are two vertices in G such that σG i (u i , vi ) = σi , dG i (u i , vi ) = di and d = di , then ( )( )( ) d d − d1 d − d1 − d2 σG (u, v) = σ1 σ2 . . . σn ...1 d1 d2 d3 k Corollary 3.2. Let G = □i=1 G ni where each G ni are ∑ geodetic. If u = (u 1 , u 2 , . . . , u k ), v = (v1 , v2 , . . . , vk ) are two vertices in G such that dG i (u i , vi ) = di and d = di , then

( )( )( ) d d − d1 d − d1 − d2 σG (u, v) = ...1 d1 d2 d3 Proposition 3.3.

Let v1 , v2 and v3 be any three vertices in G□H . Then

σG□H (v1 , v2 |v3 ) = σG□H (v1 , v3 ) × σG□H (v3 , v2 )

(3)

Theorem 3.1. The betweenness centrality of x = (g0 , h 0 ) in G□H is given by ∑ BG□H (x) = δG□H (u, v|x) u̸=v̸=x {u,v}⊆V (G□H )

where δG□H (u, v|x) = δG (g, g ′ |g0 ) × δ H (h, h ′ |h 0 ) ×

D1 × D2 D

with ( D1 =

) ( ) ( ) dG (g, g0 ) + d H (h, h 0 ) dG (g0 , g ′ ) + d H (h 0 , h ′ ) dG (g, g ′ ) + d H (h, h ′ ) , D2 = , D = dG (g, g0 ) dG (g0 , g ′ ) dG (g, g ′ )

Proof. The result follows from the definition of betweenness centrality and from Eqs. (1)–(3) Hence σG□H (u, v|x) σG (g, g ′ |g0 ) σ H (h, h ′ |h 0 ) D1 × D2 δG□H (u, v|x) = = × × □ ′ ′ σG□H (u, v) σG (g, g ) σ H (h, h ) D Definition 3.1 (Wiener Index of a Graph, [30]). The Wiener index of a graph G, denoted by W (G) is the sum of the distances between all (unordered) pairs of vertices of G. i.e., ∑ W (G) = d(vi , v j ) i< j

or, W (G) =

1 ∑ d(u, v) 2 u,v∈V (G)

Wiener index is also named total status or total distance of a graph. The Wiener index of Cartesian product [31– 33] of two graphs G and H is given by W (G□H ) = |G|2 W (H ) + |H |2 W (G) Please cite this article as: Sunil Kumar R. and K. Balakrishnan, Betweenness centrality in Cartesian product of graphs, AKCE International Journal of Graphs and Combinatorics (2019), https://doi.org/10.1016/j.akcej.2019.03.012.

Sunil Kumar R. and K. Balakrishnan / AKCE International Journal of Graphs and Combinatorics xxx (xxxx) xxx

5

Fig. 3.1. Rectangular grid Pm □Pn .

It can be extended to n ( ) ∑ ∏ n W (□i=1 Gi ) = W (G i ) |G j |2 i=1

(4)

j̸=i

The betweenness centrality of G is given by ( ) ∑ |G| B(v) = W (G) − 2 v∈V (G) If G is vertex transitive, the betweenness centrality of v ∈ G is given by ( ) W (G) − |G| 2 B(v) = |G|

(5)

3.1. Grid graphs Grid graphs are the Cartesian product of path graphs. Pm □Pn represents a rectangular grid R. If u( =) (g, h) and v = (g ′ , h ′ ) are any two vertices of R, then d(u, v) = |g − g ′ | + |h − h ′ | (l 1 -metric) and σ (u, v) = dd where 1 d1 = |g − g ′ | or |h − h ′ |. Consider the rectangular grid Pm □Pn given in Fig. 3.1. Take a vertex x in Pm □Pn ; then x = (a, b), where 1 ≤ a ≤ m, 1 ≤ b ≤ n. The paths Pna and Pmb passing through (a, b) divide the rectangular grid into four quadrants A, B, C, D sharing their common sides. Any pair of vertices lying in the diagonal regions A, B or C, D makes a contribution to the betweenness centrality of (a, b). Hence ] [ ] ∑ σ (u, x)σ (x, v) ∑ σ (w, x)σ (x, z) [ + − (a − 1) × (m − a) + (b − 1) × (n − b) B (a, b) = σ (u, v) σ (w, z) w,z u,v where u ∈ A, v ∈ B, w ∈ C and z ∈ D . Lemma 3.1. In an m × n grid, for any inner vertex w0 = (a, b), the vertices at a distance d = min{a, b, m − a, m − b} > 0 from w0 induces it the betweenness centrality 4d Proof. Consider the k-neighborhood (k-nbd) of w0 where k = min{a, b, m − a, m − b} > 0. Each k-nbd of w0 contains 4d vertices at a distance d from w0 for 1 ≤ d ≤ k and they are lying on a rhombus as in Fig. 3.2). Consider the vertices u and v lying on opposite sides of the rhombus where d(u, w0 ) = r1 +(d−r1 ) and d(v, w0 ) = r2 +(d−r2 ) Please cite this article as: Sunil Kumar R. and K. Balakrishnan, Betweenness centrality in Cartesian product of graphs, AKCE International Journal of Graphs and Combinatorics (2019), https://doi.org/10.1016/j.akcej.2019.03.012.

6

Sunil Kumar R. and K. Balakrishnan / AKCE International Journal of Graphs and Combinatorics xxx (xxxx) xxx

Fig. 3.2. Neighborhood of w0 in P7 □P7 .

(rd1 )(rd2 ) to w0 . (r12d +r2 ) Split the distance d(u, v) = 2d into (2d − r ) + r , the horizontal and vertical components and consider the pairs of vertices (u, v) for each r . It can be easily seen that they contribute the betweenness centrality 2 for r = 0; 4 for 1 ≤ r ≤ d − 1; 2 for r = d. Thus the betweenness centrality induced by the vertices at a distance d is given by 2 + 4(d − 1) + 2 = 4d. □ for 0 ≤ r1 , r2 ≤ d such that d(u, v) = 2d. Now the pair (u, v) induces the betweenness centrality

Theorem 3.2. In an m × n grid, for any vertex w0 = (a, b), 1 < a < m, 1 < b < n, the k-nbd of w0 where k = min{a, b, m − a, m − b} > 0 denoted by Nk (w0 ) contains 2k(k + 1) vertices and the betweenness centrality of w0 induced by Nk (w0 ) is given by ( ) B w0 , Nk (w0 ) = 2k 2 (k + 1) Proof. Let w0 be an inner vertex of the m × n grid. Then the pairs of vertices (u, v) for d(u, w0 ) = r1 and d(v, w0 ) = r2 such that d(u, v) = r1 + r2 = d induces a betweenness centrality 2d. Since there exist d − 1 pairs of (r1 , r2 ) for d ≥ 2, the pairs of vertices at a distance d induce a betweenness centrality 2d(d − 1). To find the betweenness centrality of w0 induced by Nk (w0 ), consider (r1 , r2 ) for 1 ≤ r1 , r2 ≤ k and we get k+1 k ( ) ∑ ∑ B w0 , Nk (w0 ) = 2d(d − 1) + 2(k + r )(k − r + 1) = 2k 2 (k + 1) □ d=2

r =2

k Remark 1. Using Corollary 3.2 the number of geodesics of length kn in the grid G = □i=1 Pn+1 from (0, 0, . . . , k times) to (n, n, . . . , k times) obtained follows the k-ary de Bruijn sequence s(k, n) where s(k, n) = (kn)! (n!)k (O E I S A000984)

3.2. Hamming graphs Hamming graphs are Cartesian products of complete graphs. i.e., H = □ri=1 K ni for some r ≥ 1 and n i ≥ 2. The vertices of H can be labeled with vector (a1 , a2 , . . . , ar ) where ai ∈ {0, 1, . . . , n i − 1}. Two vertices of H are adjacent if the corresponding vectors differ in precisely one coordinate. The distance (named Hamming distance) between two vertices u and v denoted by d(u, v) is the number of positions in which the two vectors differ. Hypercubes are Cartesian product of complete graphs K 2 . An r -dimensional hypercube (or r -cube) denoted by Q r is given by, Q r = □ri=1 K 2 . It can also be defined recursively, Q r = K 2 □Q r −1 . Hypercubes are important classes of graphs having many interesting structural properties. The number of geodesics between u, v ∈ Q r is given by Please cite this article as: Sunil Kumar R. and K. Balakrishnan, Betweenness centrality in Cartesian product of graphs, AKCE International Journal of Graphs and Combinatorics (2019), https://doi.org/10.1016/j.akcej.2019.03.012.

Sunil Kumar R. and K. Balakrishnan / AKCE International Journal of Graphs and Combinatorics xxx (xxxx) xxx

7

σ (u, v) = d(u, v)!. For a connected graph G, the condition “I (u, v) induces a d(u, v)-dimensional hypercube for any two vertices u and v of G ” implies that G is a Hamming graph [24]. The following lemma highlights the importance of Hamming graphs. Lemma 3.2 ([34]). A graph G is a nontrivial subgraph of the Cartesian product of graphs if and only if G is a nontrivial subgraph of the Cartesian product of two complete graphs. Proposition 3.4. Let H be the Hamming graph given by H = K n 1 □K n 2 □ . . . □K nr . Then the betweenness centrality of v ∈ H is given by r r ∑ 1∏ [ 1] 1 ni r − 1 − + B(v) = 2 i=1 n 2 i=1 i Proof. Let H = □ri=1 K ni . Since H is vertex transitive, from Eqs. (4) and (5), r r r ( ) ∏ r ∑ ∑ ∏ ni W (H ) = W (K ni ) |K n j |2 = n 2j 2 i=1 j=1, j̸=i i=1 j=1, j̸=i r

r

∑ 1] 1 (∏ )2 [ = ni r− 2 i=1 n i=1 i (|H |) W (H ) − 2 B H (v) = |H | r r ∑ 1∏ [ 1] 1 = ni r − 1 − + 2 i=1 n 2 i=1 i



Corollary 3.3. If K p , K q and K r are complete graphs, then for v ∈ K p □K q ( p − 1)(q − 1) B(v) = 2 for v ∈ K p □K q □K r ] 1[ B(v) = 2 pqr − ( pq + pr + qr ) + 1 2 Corollary 3.4. If v ∈ □ri=1 K n , then ] 1[ B(v) = (r − 1)n r − r n r −1 + 1 2 when n = 2, v ∈ Qr , the r -cube, then 1 B(v) = (r − 2)2r −2 + 2 3.3. Product of cycles Consider the product of cycles □ri=1 Cni . Now from Eqs. (4) we get for n i ∈ 2Z+ r r 1 (∏ )2 ∑ n W (□i=1 Cni ) = ni ni 8 i=1 i=1

(6)

and for n i ∈ 2Z+ + 1 n W (□i=1 Cni ) ==

r r 1 (∏ )2 ∑( 1) ni ni − 8 i=1 ni i=1

(7)

For any Cn , W (Cn ) = 18 n 3 when n is even, and W (Cn ) = 18 (n 3 − n) when n is odd. Now from Eqs. (5)–(7) we get Please cite this article as: Sunil Kumar R. and K. Balakrishnan, Betweenness centrality in Cartesian product of graphs, AKCE International Journal of Graphs and Combinatorics (2019), https://doi.org/10.1016/j.akcej.2019.03.012.

8

Sunil Kumar R. and K. Balakrishnan / AKCE International Journal of Graphs and Combinatorics xxx (xxxx) xxx

Proposition 3.5. If G is the Cartesian product of r even cycles. i.e., G = □ri=1 Cni , n i ∈ 2Z+ , then for v ∈ G B(v) =

r r r (∏ )] 1 [∏ ∑ ni ni − 4 ni − 1 8 i=1 i=1 i=1

if n i = 2ki , B(v) = 2r −2

r ∏

ki

i=1

r [∑

] 1 ki − 2 + 2 i=1

Proposition 3.6. If G is the Cartesian product of r odd cycles. i.e., G = □ri=1 Cni , n i ∈ 2Z+ + 1, then for v ∈ G B(v) =

r r r (∏ )] 1 [∏ ∑( 1) ni −4 ni − 1 ni − 8 i=1 ni i=1 i=1

Corollary 3.5. Consider two cycles Cm and Cn . Let v ∈ Cm □Cn then ⎧ 1 ⎪ ⎪ (mn − 1)(m + n − 4) , when m and n ar e odd ⎪ ⎪ ⎪ ⎨8 1 B(v) = [mn 2 + m(m − 4)n + 4] , when m and n ar e even ⎪ 8 ⎪ ⎪ ⎪ ⎪ ⎩ 1 [mn 2 + (m 2 − 4m − 1)n + 4] , when m odd and n is even. 8 In another form, ( ) ( ) ⎧ k1 k2 ⎪ ⎪ k1 k2 (k1 + k2 ) + + when m = 2k1 + 1, n = 2k2 + 1 ⎪ ⎪ 2 2= ⎪ ⎨ B(v) = k1 k2 (k1 + k2 − 2) + 1 when m = 2k1 , n = 2k2 ⎪ ⎪ 2 ⎪ ⎪ ⎪ ⎩k k (k + k − 1) + 1 (k − 1)2 when m = 2k + 1, n = 2k 1 2 1 2 2 1 2 2 3.4. Product of path and cycle Consider G = Pm □Cn . Then G has m layers of Cn (also n layers of Pm ) and it can be embedded on the surface of a cylinder. Theorem 3.3. Let G = Pm □Cn . Then for (i, j) ∈ G If (i, j) ∈ Pm □C2k+1 ( ) ( ) i ] k k + 1 [∑ B[(i, j)] = + i(1 + 2k)(m − i − 1) + 2 (Hm−i+r − H1+r ) + H1+i − H1 2 2 r =0

Case 1.

Case 2.

If (i, j) ∈ Pm □C2k i

B[(i, j)] =

[∑ ] (k − 1)2 + 2ik(m − i − 1) + k 2 (Hm−i+r − H1+r ) + H1+i − H1 2 r =0

Proof. Let G = Pm □Cn where V (Pm ) = {0, 1, . . . , m − 1} and V (Cn ) = {0, 1, . . . , n − 1}. Since each layer of Cn is vertex-transitive, it is enough to find B(v) for only one layer of Pm . Case 1. When n is odd



Please cite this article as: Sunil Kumar R. and K. Balakrishnan, Betweenness centrality in Cartesian product of graphs, AKCE International Journal of Graphs and Combinatorics (2019), https://doi.org/10.1016/j.akcej.2019.03.012.

Sunil Kumar R. and K. Balakrishnan / AKCE International Journal of Graphs and Combinatorics xxx (xxxx) xxx

9

Fig. 3.3. Pm □C2k+1 .

Let n = 2k + 1, k ∈ Z + . Consider the vertices of Pmk , i.e., {(0, k), (1, k), . . . , (m − 1, k)}. First consider the vertex (0, k). It is in the outer layer, see Fig. 3.3. There are 2k vertices other than (0, k) in this layer. The betweenness centrality of (0, k) is the sum of the contributions of this outer layer Cn0 with itself and with inner layers Cns , for 1 ≤ s ≤ m − 1. By symmetry, we consider only the k vertices on Cn0 , i.e., {(0, k − 1), (0, k − 2), . . . , (0, 0)}. Each vertex in {(0, k − r ), 1 ≤ r ≤ k − 1} make pairs with k − r consecutive vertices (0, k + r ), 1 ≤ r ≤ k − 1 of (k ) (k ) ∑ 0 the same layer and give the betweenness centrality rk−1 =1 (k − r ) = 2 to (0, k). i.e., the layer C n contributes 2 to the betweenness centrality of (0, k). Now we find the contribution of the outer layer with inner layers. By symmetry, we consider the set of vertices {(0, k − r ), 1 ≤ r ≤ k − 1} of the outer layer making pairs with k − r consecutive vertices of inner layers {(q, k + r ), 1 ≤ r ≤ k − 1, 1 ≤ q ≤ m − 1}, (i.e., with vertices lying between the layers Pmk+1 and Pm2k−r ) and the vertex {(0, 0)} making pairs with the vertices of the layer Pmk except (0, k) and double the value got in these two cases. Since Pm and Cn are geodetic we can use in Corollary 3.1 to find the ( the formula given ) number of shortest paths in the product graph. i.e., if ( p, c) ∈ I ( p1 , c1 ), ( p2 , c2 ) then the contribution of this pair to ( p, c) is ) ( ) ( ) ( | p − p1 | + |c − c1 | | p − p2 | + |c − c2 | | p1 − p2 | + |c1 − c2 | −1 × × | p − p1 | | p − p2 | | p1 − p2 | If L 1 , L 2 , . . . , L m denote the layers Cn0 , Cn1 , . . . , Cnm−1 respectively. Then the contribution of L 1 with other layers to the betweenness centrality of the vertex (0, k) is given by ( ) k 1 + 2 + ··· + k 1∑ 1 k+1 1 1+2 1+2+3 (L 1 , L 2 ) ⇒ + + + ··· + = n= 2 2 3 4 k+1 2 n=1 2 ( ) k 1∑ 1 k+1 = n= 3 n=1 3 2 ( ) ( ) k 1 + 4 + 10 + · · · + k+2 1 1 + 4 1 + 4 + 10 1∑ 1 k+1 3 (L 1 , L 4 ) ⇒ + + + ··· + = n= (k+3) 4 10 20 4 n=1 4 2 3 1 + 3 + 6 + ··· + 1 1+3 1+3+6 (L 1 , L 3 ) ⇒ + + + ··· + (k+2) 3 6 10 2

(k+1) 2

Please cite this article as: Sunil Kumar R. and K. Balakrishnan, Betweenness centrality in Cartesian product of graphs, AKCE International Journal of Graphs and Combinatorics (2019), https://doi.org/10.1016/j.akcej.2019.03.012.

10

Sunil Kumar R. and K. Balakrishnan / AKCE International Journal of Graphs and Combinatorics xxx (xxxx) xxx

etc. ) ( ( ) ( ) + · · · + k+m−2 1 + m + m+1 1 + m + m+1 1 1+m m−1 2 2 (L 1 , L m ) ⇒ + ··· + + (m+1) + (m+2) (k+m−1) m 2 2 m−1 ( ) k 1 ∑ 1 k+1 = n= m n=1 m 2 ∑ Therefore, if Hm denotes the mth harmonic number i.e., Hm = rm=1 1/r with H0 = 0, then ( ) ( ) m ( ) ( ) k k+1 ∑1 k k+1 B[(0, k)] = +2 = +2 (Hm − H1 ) 2 2 r 2 2 r =2

(8)

Consider ( )the vertex ( ) (1, k) on L 2 . Now from Eq. (8)(the )vertices of L 2 with L 2 , L 3 , . . . , L m give the betweenness k+1 centrality k2 +2 k+1 (H − H ), and with L give 2 (H2 − H1 ). Again the vertices of L 1 with L 3 , L 4 , . . . , L m m−1 1 1 2 2 give the betweenness centrality [1 ] 1 (m − 2) + 2 (4 + 5 + · · · k ter ms) + (5 + 6 + · · · k ter ms) + · · · (m − 2) ter ms 3 4 ( ) k+1 = (1 + 2k)(m − 2) + 2 (Hm − H2 ) 2 Combining these we get, ( ) ( ) k k+1 B[(1, k)] = + (1 + 2k)(m − 2) + 2 (Hm−1 − H1 + Hm − H2 + H2 − H1 ) 2 2 Similarly, for the vertex (2, k), L 2 and L 1 with inner layers L 3 , L 4 . . . . , L m contribute betweenness centrality ] [1 1 (m − 3) + 2 (4 + 5 + · · · k ter ms) + (5 + 6 + · · · k ter ms) + · · · (m − 3) ter ms 3 4 [1 ] 1 + (m − 3) + 2 (5 + 6 + · · · k ter ms) + (5 + 6 + · · · k ter ms) + · · · (m − 3) ter ms 4 5 ( ) ( ) k+1 k+1 = 2(1 + 2k)(m − 3) + 2 (Hm − H3 ) + 2 (Hm−1 − H2 ) 2 2 Therefore, ( ) ( ) k k+1 B[(2, k)] = + 2(1 + 2k)(m − 3) + 2 (Hm−2 − H1 + Hm−1 − H2 + Hm − H3 + H3 − H1 ) 2 2 In general, ) t ( ) ( ] k + 1 [∑ k + t(1 + 2k)(m − t − 1) + 2 (Hm−t+r − H1+r ) + H1+t − H1 B[(t, k)] = 2 2 r =0 By symmetry, B[(i, j)] =

( ) ( ) i ] k k + 1 [∑ + i(1 + 2k)(m − i − 1) + 2 (Hm−i+r − H1+r ) + H1+i − H1 2 2 r =0

Again, B[(i, j)] = B[(m − i − 1, j)] for 0 ≤ i ≤

⌈m ⌉ 2

−1

Case 2. When m is even □ Let m = 2k, k ∈ Z + . As in Case 1., we can evaluate the betweenness centrality of each vertex on Pmk . But since the graph is even, for each pair of vertices lying on extreme path layers, there are two geodesics joining them and one of them passes through Pmk . So we have to multiply last terms of each expression in Case 1. by 12 . See Fig. 3.4 Please cite this article as: Sunil Kumar R. and K. Balakrishnan, Betweenness centrality in Cartesian product of graphs, AKCE International Journal of Graphs and Combinatorics (2019), https://doi.org/10.1016/j.akcej.2019.03.012.

Sunil Kumar R. and K. Balakrishnan / AKCE International Journal of Graphs and Combinatorics xxx (xxxx) xxx

11

Fig. 3.4. Pm □C2k .

The contribution of L 1 with other layers to the betweenness centrality of the vertex (0, k) is as follows (L 1 , L 1 ) ⇒

(k − 1)2 2

k 1 ] 1 1+2 1+2+3 1 + 2 + ··· + k 1 1 + 2 + ··· + k 1∑ [ n 1− + + + ··· + − = 2 3 4 k+1 2 k+1 2 n=1 k+1 ( ) 1 k+1 k2 k = − = 2 4 4 2 ( ) (k+1) 1 + 3 + 6 + · · · + k+1 1 1+3 1+3+6 1 1 + 3 + 6 + ··· + 2 2 (L 1 , L 3 ) ⇒ + + + ··· + − (k+2) (k+2) 3 6 10 2 2 2 ( ) k2 1 k+1 k = − = 3 6 6 2 (k+2) ( ) 1 + 4 + 10 + · · · + k+2 1 1 + 4 1 + 4 + 10 1 1 + 4 + 10 + · · · + 3 3 (L 1 , L 4 ) ⇒ + + + ··· + − (k+3) (k+3) 4 10 20 2 3 3 ) ( k k2 1 k+1 − = = 4 2 8 8

(L 1 , L 2 ) ⇒

etc. ( ) ( ) ( ) 1 + m + m+1 + · · · + k+m−2 1 + m + m+1 1 1+m 2 m−1 2 (L 1 , L m ) ⇒ + (m+1) + + ··· + (m+2) (k+m−1) m 2 2 m−1 (m+1) (k+m−2) ( ) 1 + m + + · · · + 1 k+1 k k2 1 2 m−1 − = − = (k+m−1) 2 m 2 2m 2m m−1 Therefore, B[(0, k)] =

m ∑ (k − 1)2 1 (k − 1)2 + k2 = + k 2 (Hm − H1 ) 2 r 2 r =2

(9)

Consider the vertex (1, k) on L 2 . Now from Eq. (9), the vertices of L 2 with L 2 , L 3 , . . . , L m give the betweenness 2 centrality (k−1) + k 2 (Hm−1 − H1 ), and L 2 with L 1 give k 2 (H2 − H1 ). The vertices of L 1 with L 3 , L 4 , . . . , L m give 2 Please cite this article as: Sunil Kumar R. and K. Balakrishnan, Betweenness centrality in Cartesian product of graphs, AKCE International Journal of Graphs and Combinatorics (2019), https://doi.org/10.1016/j.akcej.2019.03.012.

12

Sunil Kumar R. and K. Balakrishnan / AKCE International Journal of Graphs and Combinatorics xxx (xxxx) xxx

the betweenness centrality [1( ) 1( ) (m − 2) + 2 4 + 5 + · · · + (k + 3) + 5 + 6 + · · · + (k + 4) 3 4 )] [ k + 3 k + 4 k +m] 1( (m + 1) + (m + 2) + · · · + (m + k) − + + ··· + + ··· + m 3 4 m ( ) [ ] k+1 = 2 (m − 2)k + (Hm − H2 ) − k(Hm − H2 ) 2 Combining these we get, B[(1, k)] =

(k − 1)2 + 2k(m − 2) + k 2 (Hm−1 − H1 + Hm − H2 + H2 − H1 ) 2

Similarly, B[(2, k)] =

(k − 1)2 + 4k(m − 3) + k 2 (Hm−2 − H1 + Hm−1 − H2 + Hm − H3 + H3 − H1 ) 2

In general, t

B[(t, k)] =

[∑ ] (k − 1)2 (Hm−t+r − H1+r ) + H1+t − H1 + 2tk(m − t − 1) + k 2 2 r =0

By symmetry, i

B[(i, j)] =

[∑ ] (k − 1)2 + 2ik(m − i − 1) + k 2 (Hm−i+r − H1+r ) + H1+i − H1 2 r =0

Again, B[(i, j)] = B[(m − i − 1, j)] for 0 ≤ i ≤

⌈m ⌉ 2

−1



Corollary 3.6. The graph Pm □Cn is vertex transitive only when m = 2 known as cycle prism. The betweenness centrality of cycle prism is given by ⎧ ⎨k 2 when n = 2k + 1 B(v) = 1 ⎩ [(k − 1)2 + k 2 ] when n = 2k 2 4. Conclusion A composite graph can be constructed by applying different graph operations on smaller graphs and many of the structural properties of the composite graphs can be studied from its constituent smaller graphs. An expression for the betweenness centrality of Cartesian product of graphs has been derived and examined for different graph products. This can be extended to other graph-products such that an investigation on the behavior of centrality of larger graph can be made from the platform of its constituent smaller graphs. References [1] F de Pasquale, et al., A dynamic core network and global efficiency in the resting human brain, Cerebral Cortex (2015) bhv185. [2] Martín González Ana M, Dalsgaard Bo, Olesen Jens M, Centrality measures and the importance of generalist species in pollination networks, Ecol. Complex. 7 (1) (2010) 36–43. [3] Rubinov Mikail, Sporns Olaf, Complex network measures of brain connectivity: uses and interpretations, Neuroimage 52 (3) (2010) 1059–1069. [4] Salathé Marcel, et al., A high-resolution human contact network for infectious disease transmission, Proc. Natl. Acad. Sci. 107 (51) (2010) 22020–22025. [5] Jeong Hawoong, et al., Lethality and centrality in protein networks, Nature 411 (6833) (2001) 41–42. [6] Pinney J, McConkey G, Westhead D, Decomposition of biological networks using betweenness centrality, in: Proc. 9th Ann. Int’l Conf. on Research in Computational Molecular Biology (RECOMB 2005), 2005.

Please cite this article as: Sunil Kumar R. and K. Balakrishnan, Betweenness centrality in Cartesian product of graphs, AKCE International Journal of Graphs and Combinatorics (2019), https://doi.org/10.1016/j.akcej.2019.03.012.

Sunil Kumar R. and K. Balakrishnan / AKCE International Journal of Graphs and Combinatorics xxx (xxxx) xxx

13

[7] Del Sol Antonio, Fujihashi Hirotomo, O’Meara Paul, Topology of small-world networks of protein–protein complex structures, Bioinformatics 21 (8) (2005) 1311–1315. [8] Koschützki Dirk, Schreiber Falk, Centrality analysis methods for biological networks and their application to gene regulatory networks, in: Gene Regulation and Systems Biology, Vol. 2, Libertas Academica, 2008, p. 193. [9] Estrada Ernesto, Virtual identification of essential proteins within the protein interaction network of yeast, Proteomics 6 (1) (2006) 35–40. [10] Liljeros Fredrik, et al., The web of human sexual contacts, Nature 411 (6840) (2001) 907–908. [11] Krebs Valdis E, Mapping networks of terrorist cells, Connections 24 (3) (2002) 43–52. [12] Guimera Roger, et al., The worldwide air transportation network: anomalous centrality, community structure, and cities’ global roles, Proc. Natl. Acad. Sci. 102 (22) (2005) 7794–7799. [13] Cisic Dragan, Kesic Blanka, Jakomin Livij, Research of the power in the supply chain, in: International Trade, Economics Working Paper Archive EconWPA (April 2000), 2000. [14] Maliackal Poulo Joy, et al., High-betweenness proteins in the yeast protein interaction network, BioMed Res. Int. 2005 (2) (2005) 96–103. [15] Chen Jing, Aronow Bruce J, Jegga Anil G, Disease candidate gene identification and prioritization using protein interaction networks, BMC Bioinform. 10 (1) (2009) 1. [16] Jordán Ferenc, Keystone species and food webs, Philos. Trans. R. Soc. B 364 (1524) (2009) 1733–1741. [17] Borgatti Stephen P, Everett Martin G, A graph-theoretic perspective on centrality, Soc. Netw. 28 (4) (2006) 466–484. [18] Brandes Ulrik, On variants of shortest-path betweenness centrality and their generic computation, Social Networks 30 (2) (2008) 136–145. [19] Brandes Ulrik, A faster algorithm for betweenness centrality*, J. Math. Sociol. 25 (2) (2001) 163–177. [20] Bavelas A, A mathematical model for group structure, human organization 7, 1630, Appl. Anthropol. 7 (3) (1948) 16–30. [21] Brandes Ulrik, Fleischer Daniel, Centrality Measures Based on Current Flow, Springer, 2005. [22] Borgatti Stephen P, Centrality and network flow, Soc. Netw. 27 (1) (2005) 55–71. [23] Ore Oystein, Theory of Graphs, Vol. 38, American Mathematical Society Colloquium Publications, 1962. [24] Mulder Henry Martyn, The interval function of a graph, MC Tracts 132 (1980) 1–191. [25] Freeman Linton C, A set of measures of centrality based on betweenness, Sociometry (1977) 35–41. [26] Sabidussi Gert, Graphs with given group and given graph-theoretical properties, Canad. J. Math 9 (515) (1957) C525. [27] Imrich Wilfried, Klavzar Sandi, Rall Douglas F, Topics in Graph Theory: Graphs and their Cartesian Product, CRC Press, 2008. [28] Xu Junming, Theory and Application of Graphs, Vol. 10, Springer Science & Business Media, 2013. [29] Hammack Richard, Imrich Wilfried, Klavžar Sandi, Handbook of Product Graphs, CRC press, 2011. [30] Wiener Harry, Structural determination of paraffin boiling points, J. Am. Chem. Soc. 69 (1) (1947) 17–20. [31] Graovac Ante, Pisanski Tomaž, On the Wiener index of a graph, J. Math. Chem. 8 (1) (1991) 53–62. [32] Yeh Yeong-Nan, Gutman Ivan, On the sum of all distances in composite graphs, Discrete Math. 135 (1–3) (1994) 359–365. [33] Dehmer Matthias, Emmert-Streib Frank, Quantitative Graph Theory: Mathematical Foundations and Applications, CRC Press, 2014. [34] Klavžar Sandi, Peterin Iztok, Characterizing subgraphs of Hamming graphs, J. Graph Theory 49 (4) (2005) 302–312.

Please cite this article as: Sunil Kumar R. and K. Balakrishnan, Betweenness centrality in Cartesian product of graphs, AKCE International Journal of Graphs and Combinatorics (2019), https://doi.org/10.1016/j.akcej.2019.03.012.