Network descriptors based on betweenness centrality and transmission and their extremal values

Network descriptors based on betweenness centrality and transmission and their extremal values

Discrete Applied Mathematics 161 (2013) 2678–2686 Contents lists available at ScienceDirect Discrete Applied Mathematics journal homepage: www.elsev...

401KB Sizes 0 Downloads 7 Views

Discrete Applied Mathematics 161 (2013) 2678–2686

Contents lists available at ScienceDirect

Discrete Applied Mathematics journal homepage: www.elsevier.com/locate/dam

Network descriptors based on betweenness centrality and transmission and their extremal values Damir Vukičević a , Gilles Caporossi b,∗ a

Department of Mathematics, University of Split, Split, Croatia

b

GERAD & Department of Management Sciences, HEC Montréal, Montréal (Québec), Canada, H3T 2A7

article

abstract

info

Article history: Received 21 December 2011 Received in revised form 4 April 2013 Accepted 8 April 2013 Available online 30 April 2013

Transmission and betweenness centrality are key concepts in communication networks theory. In this paper, a series of network descriptors based on betweenness centrality and transmission are proposed. Their extremal values as well as some graphs to which they correspond are given. © 2013 Elsevier B.V. All rights reserved.

Keywords: Graph theory Communication network Centrality betweenness Transmission

1. Vertex centrality and transmission In this paper, we consider a simple connected graph G = (V , E ). The betweenness centrality [1,4] is used in social network analysis as the indicator of a node (person) centrality and is based upon the number of shortest paths between vertices of the network that uses a given vertex. The larger the value is, the more important the corresponding person is with respect to information circulation. Indeed, if we consider that each individual may retain information, vertices involved in a large number of communications are more critical. Based upon betweenness centrality, Girvan and Newman [5] define the edge betweenness buv of the edge between vertices u and v as follows: buv =

  skl uv k∈V l∈V ,k
skl

,

∀(u, v) ∈ E ,

(1)

kl where skl uv is the number of shortest paths between k and l that uses the edge (u, v) and s is the total number of shortest paths between k and l. In this paper, the vertex betweenness centrality of a vertex v is defined as the sum of the betweenness centralities of the edges adjacent to v ,

c ( u) =



buv .

(2)

v|(u,v)∈E

In contrast to Freeman’s definition, the paths from a vertex v to other vertices are considered in the definition of c (v). To avoid confusion, we will therefore use the term adjusted betweenness centrality here. Indeed, betweenness centrality and adjusted betweenness centrality are closely related and differ by |V | − 1.



Corresponding author. Tel.: +1 514 340 6053 6032; fax: +1 514 340 5665. E-mail addresses: [email protected] (D. Vukičević), [email protected] (G. Caporossi).

0166-218X/$ – see front matter © 2013 Elsevier B.V. All rights reserved. http://dx.doi.org/10.1016/j.dam.2013.04.005

D. Vukičević, G. Caporossi / Discrete Applied Mathematics 161 (2013) 2678–2686

2679

If we denote by t (u) the transmission of vertex u, t (u) =



d(u, v),

(3)

v∈V

where d (u, v) denotes the distance between vertices u and v . If we denote by W (G) the Wiener index defined as W (G) =

 

d(u, v),

(4)

u∈V v∈V ,u
a property of adjusted betweenness centrality is that



c (u) =

u∈V



t (u) = 2W (G).

(5)

u∈V

2. Measures in a communication context In the case of a communication network, we can interpret t (u) as the contribution of the vertex u to the communicational cost of the network while c (u) may be viewed as the amount of the communication processed by the vertex u. Hence, in a way t (u) is the cost of u and c (u) is the benefit that network gets form the communication processing done in the vertex u. Therefore, one can analyze what is the ‘‘added value’’ to the network provided by the vertex u as the difference ν(u) = c (u) − t (u). We call this quantity network surplus of the vertex u. Another way to measure the vertex ‘productivity’ c (u) to the network is to calculate the ratio of these two values. We call this quantity N (u) = t (u) networkness of the vertex u. The vertex is highly networked if many shortest paths pass through it and it is not far from all other vertices. Hence, both quantities ν(u) and N (u) can be also interpreted in the context of the social networks. Obviously, person is well networked if c (u) is large and t (u) is small. Further, we can normalize the values of t (u) and c (u) in such a way that their average value is 1 by defining: cˆ (u) =

n · c ( u)  c (v)

v∈V (G)

tˆ(u) =

n · t ( u)  , t (v)

v∈V (G)

where n is the number of vertices of G. Note that cˆ (u) tˆ(u)

n·c (u)  c (v)

=

v∈V (G)

n·t (u)  t (v)

=

v∈V (G)

n·c (u) 2W (G) n·t (u) 2W (G)

=

c (u) t ( u)

= N (u).

Further we define the normalized network surplus as

νˆ (u) = cˆ (u) − tˆ(u). Now, using analogy with minimum and maximum degrees, we define mc (G) = min {c (u) : u ∈ V (G)} ; Mc (G) = max {c (u) : u ∈ V (G)} ; mt (G) = min {t (u) : u ∈ V (G)} ; Mt (G) = max {t (u) : u ∈ V (G)} ; mN (G) = min {N (u) : u ∈ V (G)} ; MN (G) = max {N (u) : u ∈ V (G)} ; mν(G) = min {ν(u) : u ∈ V (G)} ; M ν(G) = max {ν(u) : u ∈ V (G)} ; mcˆ (G) = min cˆ (u) : u ∈ V (G) ;





M cˆ (G) = max cˆ (u) : u ∈ V (G) ;





mtˆ(G) = min tˆ(u) : u ∈ V (G) ;





M tˆ(G) = max tˆ(u) : u ∈ V (G) ;





mνˆ (G) = min νˆ (u) : u ∈ V (G) ;





M νˆ (G) = max νˆ (u) : u ∈ V (G) .





2680

D. Vukičević, G. Caporossi / Discrete Applied Mathematics 161 (2013) 2678–2686

We are interested in finding lower and upper bounds of these values for graphs with n vertices. Finally, we define max M cˆ (n) = max M cˆ (G), G is a simple connected graph on n vertices ;





min mνˆ (n) = min mνˆ (G), G is a simple connected graph on n vertices .





3. Results In paper [3], it has been proved that Theorem 1. For each graph with n vertices it holds that

n − 1 ≤ mc (G) ≤

 2 n    ,

4 2  n − 1



4

n even;

,

n odd.

The lower bound is reached by vertices whose neighbors are all adjacent and the upper bound is reached by any vertex in a cycle. Theorem 2. For each graph with n vertices it holds that n − 1 ≤ Mc (G) ≤ (n − 1)2 . The lower bound is reached by any vertex of a complete graph and the upper bound for the central vertex of a star. Values of mt and Mt are proportional to constants well studied in the mathematical literature. They are known as proximity and remoteness and it holds that mt = π · (n − 1) and Mt = ρ · (n − 1). From the paper [2], it easily follows that Theorem 3. For each graph with n vertices it holds that

n − 1 ≤ mt (G) ≤

 2 n    ,

4 2  n − 1



4

n even;

,

n odd.

The lower bound is reached if and only if G contains a dominating vertex and the upper bound is reached if and only if G is either cycle Cn or a path Pn . Theorem 4. For each graph with n vertices it holds that n − 1 ≤ Mt (G) ≤

n2 − n 2

.

The lower bound is reached if and only if G is the complete graph Kn and the upper bound is reached if and only if G the path Pn . Let us prove that: Corollary 5. For each graph with n vertices it holds that 2 n

≤ mN (G) ≤ 1.

The upper bound is reached for any vertex of the vertex-transitive graph and the lower bound is reached for the end-vertex of a path. Proof. From Theorems 4 and 1, it follows that mN ≥

2 . n

Let us prove the upper bound:

c (u)  2W (G) u∈V (G) min , u ∈ V (G) ≤  = = 1.  t (u) t ( u) 2W (G)





c (u)

u∈V (G)

Corollary 6. For each graph with n vertices it holds that 1 ≤ MN (G) ≤ n − 1. The upper bound is reached for the central vertex of a star and the lower bound is reached for any vertex of the vertex-transitive graph.

D. Vukičević, G. Caporossi / Discrete Applied Mathematics 161 (2013) 2678–2686

2681

Proof. The upper bound follows directly from Theorems 2 and 3. Let us prove the lower bound:

 c (u)  c ( u) 2W (G) u∈V (G) max , u ∈ V (G) ≥  = = 1.  t (u) t (u) 2W (G) 

u∈V (G)

Completely analogously, it can be proved that: Corollary 7. For each graph with n vertices it holds that n2 − 3n + 2 2

≤ mν(G) ≤ 0.

The lower bound is reached for the end-vertex of a path and the upper bound is reached for any vertex of the vertex-transitive graph and Proof. Let us just prove the upper bound. It holds that 1

min {c (u) − t (u), u ∈ V (G)} ≤



n 1

=

n

 

(c (u) − t (u))

u∈V (G)



 

c (u) −

u∈V (G)



t ( u)

u∈V (G)

=

1 n

(2W (G) − 2W (G)) = 0. 

Corollary 8. For each graph with n vertices it holds that 0 ≤ M ν(G) ≤ (n − 1) (n − 2) . The lower bound is reached for any vertex of the vertex-transitive graph and the upper bound is reached for the central vertex of a star. It can be easily seen that: Proposition 9. For each graph with n vertices it holds that M tˆ(G) ≥ 1. The bound is reached for any vertex of the vertex-transitive graph. This is a much harder problem to determine the upper bound. Let us prove that: Theorem 10. For each graph G with n vertices, it holds that   D(D+1) n  i · (n − D − 1 ) + 2  M tˆ(G) ≤ max ·      : 1 ≤ i ≤ D ≤ n − 1 . 2 D D2 i i2 1 1 − 2 + 2 + 2 + 2 (n − D − 1) + 6 D 2 + 3D + D2 + 3 (n − D − 1) (n − D − 2) Moreover, this bound is tight. If the maximum is obtained for D = n − 1, then the bound is reached for the end-vertex of a path Pn and if D < n − 1, then this bound is reached for the vertex v0 of the graph G (n, i, d), a graph such that there is a graph with the vertex set V = {v0 , . . . , vD } ∪ {w1 , . . . , wn−D−1 } and edge set E = vj vj+1 : j = 0, . . . , D − 1 ∪ vi−1 wj , vi wj , vi+1 wj : j = 0, . . . , n − D − 1









  ∪ wj wk : 1 ≤ j < k ≤ n − D − 1 . Such a graph is presented in Fig. 1. Proof. Let u be a vertex of graph G for which M tˆ obtains the maximal value. Let us denote D = max {d (u, v) : v ∈ V (G)} , let u = w0 w1 . . . wD be one shortest path from u to wD and let ni be the number of vertices at distance i from u. If D = n − 1, then G is a path Pn on vertices and the claim can be verified by a simple computation. Hence, let us suppose that D < n − 1.

2682

D. Vukičević, G. Caporossi / Discrete Applied Mathematics 161 (2013) 2678–2686

Fig. 1. Graph G (n, i, D) where Kn−D−1 denotes complete graph on n − D − 1 vertices.

Let ni be the number of vertices on distance i from u. Note that



D −1  D 

d (u1 , u2 ) =

u1 ,u2 ∈{w0 ,...,wd }

1

(k − j) =

6

j=0 k=j+1













d (u1 , u2 ) ≥

u1 ,u2 ∈V (G)\{w0 ,...,wd }

D 2 + 3D + D2 ;

1=

n−D−1

d ( u1 , u2 ) =

u1 ∈{w0 ,...,wd } u2 ∈V (G)\{w0 ,...,wd }

i=1

=

j+

j =1

D  

1+

i=1

D −i 

;

2

u1 ,u2 ∈V (G)\{w0 ,...,wd }

 D i  



 j + 1 (ni − 1)

j =1

D 2

+

D2

−D·i+i

2

2



(ni − 1) .

Hence,



W (G) =

d (u1 , u2 ) +

u1 ,u2 ∈{w0 ,...,wd }





d (u1 , u2 ) +

u1 ,u2 ∈V (G)\{w0 ,...,wd }

d ( u1 , u2 )

u1 ∈{w0 ,...,wd } u2 ∈V (G)\{w0 ,...,wd }

D    D 1  D2 D 2 + 3D + D2 + 3 (n − D − 1) (n − D − 2) + − D · i + i2 1+ + 6 2 2 i =1







(ni − 1) .

On the one hand, it holds that the sum of all distances from w0 = u to {w0 , w1 , . . . , wD } is equal to D 

j=

D (D + 1) 2

j =1

.

Hence,

M t˜(G) ≤



Note that

n 2

D(D+1) 2

·

1 6

D−1

+



i · (ni − 1)

i=1

D 2 + 3D + D2 + 3 (n − D − 1) (n − D − 2) +

 





D   i =1

D(D+1) 2

i=1

(n − D − 1 ) +

D 2

+

D2 2

+

i 2

+

i2 2



(ni − 1)





2

i 2

+

i2 2



 . (n − D − 1) (ni − 1)

(ni − 1) = n − D − 1, therefore D−1

n



D−1

i · (n − D − 1) · (ni − 1) i=1  ·     2 1 2 D 2 + 3D + D2 + 3 (n − D − 1) (n − D − 2) (n − D − 1) + 1 − D2 + D2 + 6 n

n−D−1

M t˜(G) ≤

1−

·

i · (n − D − 1 ) +

i=1 D   i=1

1+

D 2

+

   n ·  ≤ max 2 1+  

D2 2

 − D · i + i2 (n − D − 1) +

1 6

D(D+1) 2

2

+ D2 − D · i + i2 (n − D − 1) + where1 ≤ i ≤ D ≤ n − 1 D 2

(ni − 1)

D 2 + 3D + D2 + 3 (n − D − 1) (n − D − 2)

 

i · (n − D − 1) +





1 6



D(D+1) 2



(n i − 1 )

    ,     . 2 D 2 + 3D + D + 3 (n − D − 1) (n − D − 2)  

D. Vukičević, G. Caporossi / Discrete Applied Mathematics 161 (2013) 2678–2686

2683

If all inequalities are equalities, then only one ni ̸= 0 and all vertices attached to diametrical paths form complete graph and are connected with the predecessor on the path (if it exists) and are connected to successor on the path (if it exists). Namely, the graph is isomorphic to G (n, i, d).  Lemma 11. Let n 2

·

2 1+ D + D2 2



q (n, D, i) =

−D·i+i2

D(D+1) i·(n−D−1)+ 2   1 (n−D−1)+ 6 [D(2+3D+D2 )+3(n−D−1)(n−D−2)]



n

.

It holds that





n

1

max {q (n, D, i)} ≤

lim sup

2

1≤i≤D≤n

.

Proof. Note that

         lim sup  max {q (n, D, i)} ,      0 . 49 n   D ≤n     1 ≤ i ≤ D ≤ n               {q (n, D, i)} , lim sup max {q (n, D, i)} = max lim sup  max n n   1≤i≤D≤n n0.49 ≤D≤n0.51     1≤i≤D≤n                      lim sup max {q (n, D, i)}    D≥n0.51 1≤i≤D≤n

n

and that q (n, D, i) = 



2D n 3



√ 3

2D

n

3



Dn 2



√ 2

+ 2Di n + 2D2 i n − 2i

D2 n 2

− in − Din + in2 . √ n − 2Di2 n − n3/2 − Dn3/2 + D2 n3/2 − 2Din3/2 + 2i2 n3/2 + n5/2 +

It holds that





lim sup  max {q (n, D, i)} = 0, D≤n0.49 1≤i≤D≤n

n

because all the summands in the numerator and the denominator except n5/2 are of the smaller order than n5/2 . It holds that:





lim sup  max {q (n, D, i)} = 0, D≥n0.51 1≤i≤D≤n

n

because all the summands in the numerator are of smaller order than D2 n3/2 and the denominator after reduction of the summands of order smaller than D2 n3/2 reduces to:



2D3



√ √ + 2D2 i n − 2Di2 n + D2 n3/2 − 2Din3/2 + 2i2 n3/2 3 √  √  2D3 n 2 3/2 = 2 (D − i) · i · D − n n + D n − > 0. n

3

Now, let us calculate:

 lim sup  n

 max

n0.49 ≤D≤n0.51 1≤i≤D≤n

{q (n, D, i)} =

  after reduction of all summands in the numerator and the denominator that

of the smaller order than n5/2 

= lim sup  n

 

max

n0.49 ≤D≤n0.51 1≤i≤D≤n

{q (n, D, i)}

2684

D. Vukičević, G. Caporossi / Discrete Applied Mathematics 161 (2013) 2678–2686

 = lim sup  n

max

n0.49 ≤D≤n0.51 1≤i≤D≤n

D2 n3/2 − 2Din3/2 + 2i2 n3/2 + n5/2

 = lim sup  n

max

n0.49 ≤D≤n0.51 1≤i≤D≤n

n

This proves the lemma.

max

n0.49 ≤D≤n0.51 1≤i≤D≤n

i2 n3/2 + n5/2

√ 2

  ≤ applying inequality between



arithmetic and geometric mean



in2

i2 n3/2





in2

 = lim sup 



in2

·

n5/2

 = 1. 2



Now, we can prove: Theorem 12. It holds that max M tˆ(n)

 lim



n

n→∞

1

=



2

.

Proof. From Theorem 10 and Lemma 11, it follows that

 lim sup

max M tˆ(n)



n



1



n

2

.  √  √   √  √  n , n (where G n, n , n are graphs from

It suffices to show that for the sequence of graphs Gn = G n, Fig. 1) holds that





M tˆ Gn2

lim

 =



n

n→∞

1 2

.

Simple calculation shows that √ √ 2 √  2 ⌊ n⌋2 n √  + − n n− n n+ n n 2  √ 2 √ √ 3 √ √  √ 2 √ 2 √ 2 n−2 n n−2 n n − n3/2 − n n3/2 n n3/2 − 2 n n3/2 + 2 n n3/2 + n5/2



⌊ n⌋n M t˜(G) = lim

n→∞

2



 n

2



⌊ n⌋



n

3





⌊ n⌋

2

3√

n

3

√  = lim √ 2 n→∞ n

+2

n n

n3/2 − 2

 Hence indeed, limn→∞

√ 2 √

n3/2 + 2





M tˆ G 2 n

n+2

n

2

√ 2 n

n

√ 3 √

n

√ 2 n

= 12 .

n3/2 + n5/2

=

1 2

.



Now, let us prove: Theorem 13. For each graph G with n vertices it holds that n 2n − 2

≤ mtˆ(G) ≤ 1.

The lower bound is reached for the central vertex of a star and the upper bound is reached for any vertex of the vertex-transitive graph. Proof. The upper bound is obvious, let us prove the lower one. Let u ∈ V (G) be the vertex that minimizes mtˆ. It holds that: tˆ(u) =

n · t ( u)

 2 t ( u) +



  v,w∈V (G)\{u}

d (v, w)

n · t (u)

 2 t ( u) +

  v,w∈V (G)\{u}

(d (v, u) + d (u, w))

D. Vukičević, G. Caporossi / Discrete Applied Mathematics 161 (2013) 2678–2686

n · t (u)

=





2 t (u) + (n − 2)

=

2685

 v∈V (G)\{u}

n · t ( u) 2 [t (u) + (n − 2) · t (u)]

=

d (u, v) n 2n − 2

. 

Theorem 14. For each graph G with n vertices it holds that 1 ≤ M cˆ (G) ≤

n 2

.

The lower bound is reached for any vertex of the vertex-transitive graph and the upper bound is reached for the central vertex of a star. Proof. Obviously, M cˆ (G) ≤ n · lower bound is obvious. 

1 2

since each edge contributes to two vertices. Simple check shows that M cˆ (Sn ) =

n . 2

The

Theorem 15. For each graph G with n vertices it holds that 3 n+1

≤ mcˆ (G) ≤ 1.

The lower bound is reached for the end-vertex of a path and the upper bound is reached for any vertex of the vertextransitive graph and Proof. The upper bound is obvious. The lower bound is obtained for the end vertex of the path, since the smallest possible number (n − 1) of the shortest paths pass through it and the path has the largest Wiener index.  Theorem 16. For each graph G with n vertices it holds that 0 ≤ M νˆ (G) ≤

n 2



n 2n − 2

.

The lower bound is reached for any vertex of the vertex-transitive graph and the upper bound is reached for the central vertex of a star. Proof. The upper bound follows from Theorems 13 and 14. Let us prove the lower bound:

 1 min cˆ (u) − tˆ(u), u ∈ V (G) ≤



1



 cˆ (u) − tˆ(u)

n

=

n

  



u∈V (G)

  u∈V (G)



cˆ (u) −

tˆ(u) =

u∈V (G)

1 n

(2W (G) − 2W (G)) = 0.

It can be simply checked that equality holds for any vertex of the vertex-transitive graph. Completely analogously, it can be seen that: Theorem 17. For each graph G with n vertices it holds that mνˆ (G) ≤ 0. This bound is reached for any vertex of the vertex-transitive graph. Let us prove: Theorem 18. It holds

 lim

n→∞

min mνˆ (n)



n



1

=− . 2



2686

D. Vukičević, G. Caporossi / Discrete Applied Mathematics 161 (2013) 2678–2686

Proof. Since cˆ is positive, it follows that

 lim

min mνˆ (n)





1

≥− . 2

n

n→∞

 √  √   √  √  n , n (where G n, n , n are graphs from

It suffices to show that for the sequence of graphs Gn = G n, Fig. 1) holds

 lim

mνˆ (Gn )



1

=− . 2

n

n→∞



Simple calculation shows that M νˆ Gn2





n−1

= −n ·

√ 

n + n2

√ 

n −

√ 2 n

+ 2n

√ 2 n

√ 3 −3 n



√  ⌈√n⌉2 +n n − 2 − √   √ 2 2⌈√n⌉3 . √ 2 ⌈ n⌉ −n + n 2 + 3 − n n +n n − 3 −

⌈ n⌉ 2

Hence,

 lim

n→∞

M νˆ Gn2





n



1

=− .  2

Acknowledgments The authors would like to thank Suzana Antunović and an anonymous referee for their useful comments. This work was supported by NSERC (Canada) and Croatian Ministry of Sciences (Grant nos. 177/0000000/0884 and 037/0000000/2779) and project GReGAS within EuroGIGA collaborative research project. References [1] J.M. Anthonisse, The Rush in a Directed Graph, Mathematisch Centrum, Amsterdam, 1971. [2] M. Aouchiche, P. Hansen, Proximity and remoteness in graphs: results and conjectures, Networks 58 (2) (2011) 95–102. [3] G. Caporossi, M. Paiva, D. Vukicević, M. Segatto, Centrality and betweenness: vertex and edge decomposition of the wiener index, MATCH Commun. Math. Comput. Chem. 68 (1) (2012) 293–302. [4] L.C. Freeman, A set of measures of centrality based on betweenness, Sociometry 40 (1977) 35–41. [5] M. Girvan, M.E.J. Newman, Community structure in social and biological networks, Proceedings of the National Academy of Sciences USA 99 (2002) 7821–7826.