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

54 Network Measures

to the summation of their centralities,

ce(vi)=

1

λ

∑n

j= 1

Aj,ice(vj), (3.8)

where λis some fixed constant. Assuming Ce=(Ce(v 1 ),Ce(v 2 ),...,

Ce(vn))T is the centrality vectors for all nodes, we can rewrite Equation

3.8as

λCe=ATCe. (3.9)

This basically means thatCeis an eigenvector of adjacency matrixAT

(orAin undirected networks, sinceA=AT) andλis the corresponding

eigenvalue. A matrix can have many eigenvalues and, in turn, many corre-

sponding eigenvectors. Hence, this raises the question: which eigenvalue–

eigenvector pair should we select? We often prefer centrality values to be

positive for convenient comparison of centrality values across nodes. Thus,

we can choose an eigenvalue such that the eigenvector components are

positive.^1 This brings us to thePerron-Frobeniustheorem.

PERRON-

FROBENIUS

THEOREM

Theorem 3.1(Perron-Frobenius Theorem).Let A∈Rn×nrepresent the

adjacency matrix for a [strongly] connected graph or A:Ai,j> 0 (i.e.

a positive n by n matrix). There exists a positive real number (Perron-

Frobenius eigenvalue)λmax, such thatλmaxis an eigenvalue of A and any

other eigenvalue of A is strictly smaller thanλmax. Furthermore, there exists

a corresponding eigenvectorv=(v 1 ,v 2 ,...,vn)of A with eigenvalueλmax

such that∀vi> 0.

Therefore, to have positive centrality values, we can compute the eigen-

values of Aand then select the largest eigenvalue. The corresponding

eigenvector isCe. Based on the Perron-Frobenius theorem, all the com-

ponents ofCewill be positive, and this vector corresponds to eigenvector

centralities for the graph.

Example 3.2.For the graph shown in Figure3.2(a), the adjacency matrix

is

A=

⎡

⎣

010

101

010

⎤

⎦. (3.10)

Based on Equation3.9, we need to solveλCe=ACe,or

(A−λI)Ce= 0. (3.11)