Social Media Mining: An Introduction

P1: qVa Trim: 6.125in×9.25in Top: 0.5in Gutter: 0.75in
CUUS2079-03 CUUS2079-Zafarani 978 1 107 01885 3 January 13, 2014 16:45

3.1 Centrality 61

v 1 v 2

v 3

v 4

v 5

Figure 3.5. Betweenness Centrality Example.

For other nodes, we have

Cb(v 2 )= 2 ×((1︸︷︷/1)︸

s=v 1 ,t=v 3

+ (1︸︷︷/1)︸

s=v 1 ,t=v 4

+ (2︸︷︷/2)︸

s=v 1 ,t=v 5

+ (1︸︷︷/2)︸

s=v 3 ,t=v 4

+ ︸︷︷︸ 0

s=v 3 ,t=v 5

+ ︸︷︷︸ 0

s=v 4 ,t=v 5

)

= 2 × 3. 5 = 7 , (3.34)

Cb(v 3 )= 2 ×(0︸︷︷︸

s=v 1 ,t=v 2

+ ︸︷︷︸ 0

s=v 1 ,t=v 4

+ (1/2)

︸︷︷︸

s=v 1 ,t=v 5

+ ︸︷︷︸ 0

s=v 2 ,t=v 4

+ (1/2)

︸︷︷︸

s=v 2 ,t=v 5

+ ︸︷︷︸ 0

s=v 4 ,t=v 5

)

= 2 × 1. 0 = 2 , (3.35)

Cb(v 4 )=Cb(v 3 )= 2 × 1. 0 = 2 , (3.36)

Cb(v 5 )= 2 ×(0︸︷︷︸

s=v 1 ,t=v 2

+ ︸︷︷︸ 0

s=v 1 ,t=v 3

+ ︸︷︷︸ 0

s=v 1 ,t=v 4

+ ︸︷︷︸ 0

s=v 2 ,t=v 3

+ ︸︷︷︸ 0

s=v 2 ,t=v 4

+ (1︸︷︷/2)︸

s=v 3 ,t=v 4

)

= 2 × 0. 5 = 1 , (3.37)

where centralities are multiplied by 2 because in an undirected graph∑

s =t =vi

σst(vi)

σst =^2

∑

s =t =vi,s<t

σst(vi)

σst.

3.1.6 Closeness Centrality

In closeness centrality, the intuition is that the more central nodes are, the

more quickly they can reach other nodes. Formally, these nodes should have

a smaller average shortest path length to other nodes. Closeness centrality

is defined as

Cc(vi)=

1

l ̄vi, (3.38)

wherel ̄vi=n−^11

∑

vj =vili,jis nodevi’s average shortest path length to other

nodes. The smaller the average shortest path length, the higher the centrality

for the node.