Social Media Mining: An Introduction

P1: WQS Trim: 6.125in×9.25in Top: 0.5in Gutter: 0.75in
CUUS2079-06 CUUS2079-Zafarani 978 1 107 01885 3 January 13, 2014 17:15

156 Community Analysis

SPECTRAL The solution to this problem is the top eigenvectors ofL.^1 GivenL, the CLUSTERING topkeigenvectors corresponding to the smallest eigen values are computed and used asXˆ, and thenk-means is run on Xˆ to extract communities memberships (X). The first eigenvector is meaningless (why?); hence, the rest of the eigenvectors (k−1) are used ask-means input.

Example 6.3.Consider the graph in Figure6.8. We find two communities in this graph using spectral clustering (i.e., k= 2 ). Then, we have

D=diag(2, 2 , 4 , 4 , 4 , 4 , 4 , 3 ,1). (6.16)

The adjacency matrix A and the unnormalized laplacian L are

A=

⎡

⎢⎢

⎣

011000000

101000000

110110000

001011100

001101100

000110110

000111010

000001101

000000010

⎤

⎥⎥

⎦

, (6.17)

L=D−A=

⎡

⎢⎢

⎣

2 − 1 − 1000000

− 12 − 1000000

− 1 − 14 − 1 − 10000

00 − 14 − 1 − 1 − 100

00 − 1 − 14 − 1 − 100

000 − 1 − 14 − 1 − 10

000 − 1 − 1 − 14 − 10

00000 − 1 − 13 − 1

0000000 − 11

⎤

⎥⎥

⎦

.

(6.18)