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 57

v 2 v 5

v 3

v 1

v 4

Figure 3.3. Katz Centrality Example.

where 1 is a vector of all 1’s. Taking the first term to the left hand side and

factoringCKatz,

CKatz=β(I−αAT)−^1 · 1. (3.21)

Since we are inverting a matrix here, not allαvalues are acceptable.

Whenα=0, the eigenvector centrality part is removed, and all nodes get

the same centrality valueβ. However, onceαgets larger, the effect of

βis reduced, and when det(I−αAT)=0, the matrixI−αATbecomes

non-invertible and the centrality values diverge. The det(I−αAT) first DIVERGENCE

IN

CENTRALITY

COMPUTATION

becomes 0 whenα= 1 /λ, whereλis the largest eigenvalue^2 ofAT.In

practice,α< 1 /λis selected so that centralities are computed correctly.

Example 3.4.For the graph shown in Figure3.3, the adjacency matrix is

as follows:

A=

⎡

⎢⎢

⎢⎢

⎣

01110

10111

11011

11100

01100

⎤

⎥⎥

⎥⎥

⎦

=AT. (3.22)

The eigenvalues of A are (− 1. 68 ,− 1. 0 ,− 1. 0 ,+ 0. 35 ,+ 3 .32).The

largest eigenvalue of A isλ= 3. 32. We assumeα= 0. 25 < 1 /λand

β= 0. 2. Then, Katz centralities are

CKatz=β(I−αAT)−^1 · 1 =

⎡

⎢⎢

⎢⎢

⎣

1. 14

1. 31

1. 31

1. 14

0. 85

⎤

⎥⎥

⎥⎥

⎦

. (3.23)

Thus, nodesv 2 , andv 3 have the highest Katz centralities.