Modularity optimization by conformational space annealing

We propose a modularity optimization method, Mod-CSA, based on stochastic global optimization algorithm, conformational space annealing (CSA). Our method outperforms simulated annealing in terms of both efficiency and accuracy, finding higher modularity partitions with less computational resources required. The high modularity values found by our method are higher than, or equal to, the largest values previously reported. In addition, the method can be combined with other heuristic methods, and implemented in parallel fashion, allowing it to be applicable to large graphs with more than 10 000 nodes.

Figure 1

Two crossover operators, (A) convergent copy and (B) divisive copy, are shown. (A) The community indexed by 1 from the source is copied into the target, and the new indices are set to 1 or 3 with the probability of $2/3$ and $1/3$. (B) The community indexed by 3 from the source is copied into the target, and the new index 2 is assigned.

Figure 2

Comparison of time complexities of CSA (red, circle) and SA (blue, cross) is shown. Network size $n$ represents the number of nodes, and CPU time corresponds to the average time to find final solutions in seconds.