# Community Structure Detection for Directed Networks through Modularity Optimisation
## 4 Conclusions  
This works reports novel mathematical programming formulation to address the problem of community structure detection in directed networks. While modularity optimisation has been extensively studied for undirected networks, there is little research effort to detect modules in directed networks. A mathematical programming-based optimisation approach has been introduced to fill the gap in literature. Modularity optimisation for a directed network can be conveniently formulated as an MINLP model, which can converge to locally optimal solutions quickly even in large networks. The MINLP model is reformulated as an MIP model by re-writing non-linear terms into linear equivalents, which can then be solved to obtain globally optimal solutions for small networks. The novel community detection method proposed consists of two major steps, taking advantage of both models. Firstly, the MINLP model is solved to produce an initial coarse network division. Given the initial network division, the iterative algorithm works by repeatedly removing the community memberships of random sets of nodes, solving the reduced MILP model and re-allocating the relaxed nodes to communities. Using synthetic and real-world directed networks covering a wide range of node and edge sizes, the proposed iterative algorithm considerably improves the quality of the initial coarse network partition. Compared with three community detection methods in literature, the proposed approach is demonstrated to identify the best network division consistently, yielding the largest modularity value. Another advantage of the proposed approach is its deterministic nature, which means multiple executions are likely to converge into the same network division. Finally, we note that owing to the nature of the mathematical programming framework used here, modelling can be flexible enough to allow additional constraints and parameters to be easily implemented according to user requirements [38]. Prior knowledge on a particular system can be incorporated, for example in the form of nodes with similar functional annotations that may be constrained to be allocated in the same community [39]. In future work, we plan to study how the density of nodes and distributions of in-degree and out-degree affect the hardness and calculation time of the optimisation problem. We also plan to modify current integer programming models so as to detect and prevent the resolution limit. **Acknowledgments:** [PERSON] acknowledges funding from the UK Engineering and Physical Sciences Research Council (EPSRC) Centre for Innovative Manufacturing in Emergent Macromolecular Therapies (EP/I033270/1) and [PERSON] acknowledges funding from Coordenacao de Aperfeicoamento de Pessoal de Nivel Superior (CAPES), Brasilia, Brazil (process number 13312138). Funding from the EU (to [PERSON], HEALTH-F2-2011-261366), the Leverhulme Trust (to [PERSON] and [PERSON], RPG- 2012-686) and the UK Engineering & Physical Sciences Research Council (to [PERSON], EPSRC Centre for Innovative Manufacturing in Emergent Macromolecular Therapies) is gratefully acknowledged. We gratefully acknowledge [PERSON] for data preparation. **Author Contributions:** [PERSON], [PERSON], [PERSON] and [PERSON] conceived and designed the experiments. [PERSON] and [PERSON] designed the computational model. [PERSON] and [PERSON] performed the experiments. [PERSON] and [PERSON] gathered network data. [PERSON], [PERSON], [PERSON] and [PERSON] analysed the data. [PERSON], [PERSON], [PERSON] and [PERSON] wrote the paper. **Conflicts of Interest:** The authors declare no conflict of interest. \begin{table}
\begin{tabular}{c c c c c c} \hline \hline  & _Myc. tub._ & _C. elegans_ & **Roget** & _P. falc._ & **gnutella08** \\ \hline Extremal & 0.4802 & 0.4731 & 0.5582 & 0.6685 & 0.2475 \\ Fast algorithm & 0.4567 & 0.5058 & 0.5002 & 0.6846 & 0.4624 \\ Tabu search & 0.4635 & 0.4438 & 0.5021 & 0.6496 & 0.2281 \\ DiMod & **0.5073** & **0.5076** & **0.5860** & **0.7238** & **0.4678** \\ \hline \hline \end{tabular}
\end{table}