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.