Social Media Mining: An Introduction

(Axel Boer) #1

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