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 59

α<^1 λis selected, whereλis the largest eigenvalue ofATD−^1. In undirected

graphs, the largest eigenvalue ofATD−^1 isλ=1; therefore,α<1.

Example 3.5.For the graph shown in Figure3.4, the adjacency matrix is

as follows,

A=

⎡

⎢⎢

⎢⎢

⎣

01011

10101

01011

10100

11100

⎤

⎥⎥

⎥⎥

⎦

. (3.27)

We assumeα= 0. 95 < 1 andβ= 0. 1. Then, PageRank values are

Cp=β(I−αATD−^1 )−^1 · 1 =

⎡

⎢⎢

⎢⎢

⎣

2. 14

2. 13

2. 14

1. 45

2. 13

⎤

⎥⎥

⎥⎥

⎦

. (3.28)

Hence, nodesv 1 andv 3 have the highest PageRank values.

3.1.5 Betweenness Centrality

Another way of looking at centrality is by considering how important nodes

are in connecting other nodes. One approach, for a nodevi, is to compute

the number of shortest paths between other nodes that pass throughvi,

Cb(vi)=

∑

s =t =vi

σst(vi)

σst

, (3.29)

whereσstis the number of shortest paths from nodestot(also known

asinformation pathways), andσst(vi) is the number of shortest paths from

stotthat pass throughvi. In other words, we are measuring how central

vi’s role is in connecting any pair of nodessandt. This measure is called

betweenness centrality.

Betweenness centrality needs to be normalized to be comparable across

networks. To normalize betweenness centrality, one needs to compute the

maximum value it takes. Betweenness centrality takes its maximum value

when nodeviis on all shortest paths fromstotfor any pair (s,t); that

is,∀(s,t),s =t =vi, σstσ(stvi)=1. For instance, in Figure3.1, nodev 1 is