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

6.2 Community Evolution 167

two snapshots:

TC=||Xt−Xt− 1 ||^2. (6.30)

Unfortunately, this requires bothXtandXt− 1 to have the same number

of columns (number of communities). Moreover,Xt is not unique and

can change by orthogonal transformations;^3 therefore, the distance value

||Xt−Xt− 1 ||^2 can change arbitrarily. To remove the effect of orthogonal

transformations and allow different numbers of columns,TCis defined as

TC=

1

2

∣∣∣∣

XtXtT−Xt− 1 XTt− 1

∣∣∣∣ 2

,

=

1

2

Tr

((

XtXtT−Xt− 1 XTt− 1

)T(

XtXTt −Xt− 1 XTt− 1

))

,

=

1

2

Tr

(

XtXtTXtXtT− 2 XtXtTXt− 1 XtT− 1 +Xt− 1 XTt− 1 Xt− 1 XTt− 1

)

,

=Tr

(

I−XtXTtXt− 1 XtT− 1

)

,

=Tr

(

I−XTtXt− 1 XtT− 1 Xt

)

, (6.31)

where^12 is for mathematical convenience, andTr(AB)=Tr(BA) is used.

Therefore, evolutionary clustering objective can be stated as

Costt=αTr

(

XtTLXt

)

+(1−α)

1

2

∣∣∣∣

XtXTt −Xt− 1 XtT− 1

∣∣∣∣ 2

,

=αTr

(

XtTLXt

)

+(1−α)Tr

(

I−XTtXt− 1 XtT− 1 Xt

)

,

=αTr

(

XtTLXt

)

+(1−α)Tr

(

XtTIXt−XTtXt− 1 XTt− 1 Xt

)

,

=Tr

(

XtTαLXt

)

+Tr

(

XTt(1−α)IXt−XTt(1−α)Xt− 1 XTt− 1 Xt

)

.

(6.32)

Assuming the normalized laplacian is used in spectral clustering,L=

I−D−t^1 /^2 AtDt−^1 /^2 ,

Costt=Tr

(

XTtα

(

I−D−t^1 /^2 AtDt−^1 /^2

)

Xt

)

+Tr

(

XTt (1−α)IXt−XTt (1−α)Xt− 1 XtT− 1 Xt

)

,

=Tr

(

XTt

(

I−αDt−^1 /^2 AtD−t^1 /^2 −(1−α)Xt− 1 XTt− 1

)

Xt

)

,

=Tr(XtLXˆ t), (6.33)

whereLˆ=I−αDt−^1 /^2 AtD−t^1 /^2 −(1−α)Xt− 1 XTt− 1. Similar to spectral

clustering,Xtcan be obtained by taking the top eigenvectors ofLˆ.