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)