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