Biology Reference
In-Depth Information
K out =96 P o outside vertices and to K in =31 P i inside vertices. We generate
several random graphs using different K out and K in , and then test the perfor-
mance of our two algorithms. Figure 11.2 illustrates examples of these synthetic
random graphs with different levels of interconnectivity [7].
Notice that these
graphs belong to type I defined in Fig. 11.1.
Fig. 11.2.
Graphs with different K in : K out ratio
Table 11.2.
GA performances
K in : K out
Best Q N
Errors
Best Q S
Errors
12:4
0.499807
0
0.659431
0
11:5
0.437481
1
0.614884
0
10:6
0.376271
2
0.564478
1
9:7
0.318518
4
0.484211
6
8:8
0.261690
15
0.448903
20
Table 11.2 summarizes the results of the Genetic algorithm using Newman's
modularity ( Q N ) and the similarity-based modularity ( Q S ). Since the Genetic
algorithm falls into local minimums, we run the algorithm several times for each
parameter setting and report the best result. At K in : K out
11:5, the structures
are very clear, both modularity definitions perfectly identify the structure. At
K in : K out = 10:6, Q N has 2 errors, but Q S yields only one error. Since then,
along with the confusion increases, Q S begins slightly lagging from Q N .Thisis
due to the synthetic graphs are generated based on the ratio of K in : K out ,which
exactly matches with the definition of Q N . The accuracy comparison is plotted in
Fig. 11.3. We can conclude that the two modularity measures yield a comparable
accuracy for the synthetic graphs.
Likewise, we tested the fast hierarchical agglomerative clustering algorithm
(FHAC) to detect structure in the synthetic graphs. The results are summarized in
Table 11.3, and we plot accuracy curves in Fig. 11.4.
Comparing Fig. 11.3 and 11.4, one can see that the FHAC keeps accuracy
with GA when K out
6 ( K in =16
K out ), then accuracy drops significantly
Search WWH ::




Custom Search