Multistep greedy algorithm identifies community structure in real-world and computer-generated networks

We have recently introduced a multistep extension of the greedy algorithm for modularity optimization. The extension is based on the idea that merging $l$ pairs of communities $(l>1)$ at each iteration prevents premature condensation into few large communities. Here, an empirical formula is presented for the choice of the step width $l$ that generates partitions with (close to) optimal modularity for 17 real-world and 1100 computer-generated networks. Furthermore, an in-depth analysis of the communities of two real-world networks (the metabolic network of the bacterium E. coli and the graph of coappearing words in the titles of papers coauthored by Martin Karplus) provides evidence that the partition obtained by the multistep greedy algorithm is superior to the one generated by the original greedy algorithm not only with respect to modularity, but also according to objective criteria. In other words, the multistep extension of the greedy algorithm reduces the danger of getting trapped in local optima of modularity and generates more reasonable partitions.

Figure 1

(Color online) Dependence of $Q_{\mathrm{MSG}-\mathrm{VM}}$ on the $\sqrt{L}$ prefactor $\alpha$ for the computer-generated networks. The averages are taken separately for each type of computer-generated networks. The vertical black line denotes $\alpha =0.25$, which is the value suggested in Eq. (2). The parameter range for $\alpha$ has been discretized to multiples of 0.001 to simplify the calculations.

Figure 2

(Color online) Clusterization of the metabolic network of E. coli and accuracy of pathway identification. Two exemplary pathways as taken from the KEGG database [36, 37] (pathways MAP00020 for “TCA cycle” and MAP00290 for “Valine, Leucine, Isoleucine Biosynthesis”) are highlighted by the colored areas. An excerpt of the network is shown here while the full network is in the supplementary material [32]. The misassigned vertices are indicated by letters; they are $\mathrm{a}=\left(\mathrm{S}\right)$-Malate for MSG-VM, and for the original greedy: $\mathrm{A}=3$-Carboxy-1-hydroxypropyl-ThPP, $\mathrm{B}=2$-Oxoglutarate, $\mathrm{C}=\text{Oxalosuccinate}$, $\mathrm{D}=\text{Succinate}$, $\mathrm{E}=\text{Fumarate}$, $\mathrm{F}=2$-Oxoisovalerate, and $\mathrm{G}=\text{Valine}$.