Page 334 - Becoming Metric Wise

326 Becoming Metric-Wise

Here we assumed that the network has N nodes. Clearly the differ-
ence between these two clustering coefficients is that of an average of
ratios versus a ratio of averages.

10.2.4 Modularity
Many networks divide naturally into modules or communities. Roughly
speaking, communities are characterized by the fact that within a com-
munity network connections are dense, but between communities con-
nections are sparse. Fig. 10.3 shows a network with three communities.
The notion of modularity is defined (Newman, 2006; Newman &
Girvan, 2004) as follows. Consider a particular division of a network into
k communities. Then a symmetric k 3 k matrix E 5 (e ij ) ij is defined. The
cell e ij contains the fraction of all edges in the network that link vertices
in community i to vertices in community j. The sum of the elements on
k
P
the diagonal e jj , known as the trace of the matrix, gives the fraction of
j51
edges in the network that connect vertices in the same community.
Clearly, if we have a good division into communities then the ratio
k
X X
e jj = e ij should be close to one. The trace on its own, however, is
j51 i;j

Figure 10.3 A network with three communities.