Social Media Mining: An Introduction

(Axel Boer) #1

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.
Free download pdf