Social Media Mining: An Introduction

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

8.1 Measuring Assortativity 221

the same type (i.e., whenAij=1,δ(t(vi),t(vj))=1). We can normalize

modularity by dividing it by the maximum it can take:

Qnormalized=

Q

Qmax

(8.6)

=

1

2 m

∑

ij(Aij−

didj

2 m )δ(t(vi),t(vj))

max[ 21 m

∑

ijAijδ(t(vi),t(vj))−

1

2 m

∑

ij

didj

2 mδ(t(vi),t(vj))]

(8.7)

=

1

2 m

∑

ij(Aij−

didj

2 m )δ(t(vi),t(vj))

1

2 m^2 m−

1

2 m

∑

ij

didj

2 m δ(t(vi),t(vj))

(8.8)

=

∑

ij(Aij−

didj

2 m )δ(t(vi),t(vj))

2 m−

∑

ij

didj

2 m δ(t(vi),t(vj))

. (8.9)

Modularity can be simplified using a matrix format. Let∈Rn×kdenote

the indicator matrix and letkdenote the number of types,

x,k=

{

1 , ift(x)=k;

0 , ift(x) =k (8.10)

Note thatδfunction can be reformulated using the indicator matrix:

δ(t(vi),t(vj))=

∑

k

vi,kvj,k. (8.11)

Therefore, (T)i,j=δ(t(vi),t(vj)). LetB=A−ddT/ 2 mdenote the

modularity matrix whered∈Rn×^1 is the degree vector for all nodes. Given

that the trace of multiplication of two matrices∑ XandYTisTr(XYT)=

i,jXi,jYi,j andTr(XY)=Tr(YX), modularity can be reformulated

as

Q=

1

2 m

∑

ij

(Aij−

didj

2 m

)

︸ ︷︷ ︸

Bij

δ(t(vi),t(vj))

︸ ︷︷ ︸

(T)i,j

=

1

2 m

Tr(BT)

=

1

2 m

Tr(TB). (8.12)