# Community Structure Detection for Directed Networks through Modularity Optimisation
## 3 Results
### Real Networks  
We demonstrate the performance of our proposed method in tests of five real networks. Table 1 shows a summary of the network properties. We include the directed and weighted neural network of _Caenorhabditis elegans_[34]. Networks for _Mycobacterium tuberculosis_ and _Plasmodium falciparum_, represent biological pathway interactions as extracted from the Reactome database (May 2014) [35]. The network for Roget's Thesaurus details cross-references between categories of English words, where one edge points from one category to another if a reference is provided to the latter among the words of the former [36]. In order to show that DiMod can solve larger problems, we include a snapshot of the Gnutella peer-to-peer network, gnutella08, obtained from the Stanford Large Network Dataset Collection (SNAP) [37].  
Figure 1: Performance of algorithms on synthetic directed networks.  
Our tests have shown that the second model (MIP) improves the quality of network division obtained by the MINLP model in the first stage. Table 2 below outlines the improvement in modularity between the more coarse initial network division provided by the MINLP and that of the final solution identified by the MIP step. Roget's Thesaurus is the network benefiting the most from the iterative procedure, where modularity is improved by about 16%. The iterative algorithm also boosts modularity by nearly 10% for _Mycobacterium tuberculosis_ while improvements of around 4% can be observed in _C. elegans_ and _Plasmodium falciparum_ networks. The gnutella08 network also has an improvement of approximately 8% from the first to the second step and Figure 2 shows how modularity is improved at the end of each MIP iteration.  
As for synthetic networks, results obtained through DiMod for real networks are compared against modularity maximisation approaches in the literature (extremal optimisation [11], fast algorithm [10] and Tabu search [29]). Overall, the methodology proposed here consistently outperforms other methods, as shown in Table 3, which summarises our computational results.  
\begin{table}
\begin{tabular}{c c c c} \hline \hline  & **Nodes** & **Edges** & **Type of Network** \\ \hline _Mycobacterium tuberculosis_ & 194 & 849 & unweighted \\ _Caenorhabditis elegans_ & 297 & 2345 & weighted \\ Roget’s thesaurus & 994 & 5058 & unweighted \\ _Plasmodium falciparum_ & 1390 & 6497 & unweighted \\ gnutella08 & 6301 & 20,777 & unweighted \\ \hline \hline \end{tabular}
\end{table}
Table 1: Summary of networks used as benchmarks in this study.  
\begin{table}
\begin{tabular}{c c c c c} \hline \hline  & _Myc. tub._ & _C. elegans_ & **Roget** & _P. falc._ & **gnutella08** \\ \hline Initial modularity & 0.4636 & 0.4877 & 0.5063 & 0.6978 & 0.4333 \\ Final modularity & 0.5073 & 0.5076 & 0.5860 & 0.7238 & 0.4678 \\ Improvement & 9.43\% & 4.08\% & 15.75\% & 3.72\% & 7.97\% \\ Number of modules & 9 & 5 & 13 & 20 & 24 \\ \hline \hline \end{tabular}
\end{table}
Table 2: Modularity improvement achieved by second step of the proposed method over the initial division network given by the MINLP.  
Figure 2: Improvement of modularity at the end of each MIP iteration for gnutella08 network.