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


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