# Community Structure Detection for Directed Networks through Modularity Optimisation
## 1 Introduction  
It is increasingly clear that a wide range of systems across different disciplines can be described using network representations. The edges in a network can be binary, weighted, directed and with a positive or negative sign, thus rendering networks a suitable tool to model diverse types of interactions [1]. One common observation is that real world networks are not random graphs with homogeneous edge distribution, rather, a high density of edges exist within subsets of the network, while edge density across these subgraphs is much lower, giving rise to the emergence of a property known as community structure [2].  
Community structure detection refers to the procedure of identifying the inherent higher order structure of a network by partitioning nodes into different modules. The modularity metric (Q) was introduced by [PERSON] and [PERSON] [3] for undirected networks and measures the quality of a network partition into communities. A modularity value close to 1 suggests strong community structure, i.e., a larger proportion of edges falling within modules than at random.  
Community detection is often formulated as an optimisation problem, where the partition that yields the maximum modularity for a target network is sought. This metric, however, has been proven to be NP-complete [4], and, therefore, exhaustive search algorithms are only applicable to small networks, as the number of possible partitions increases at least exponentially with the number of nodes. Modularity has also been shown to have a resolution limit [5] and a degenerate solution space [6]. There have been attempts in the literature to address resolution limit issues by adding aresolution parameter, but, as this parameter is hard to determine and increases method complexity, the problem is still not fully resolved [7].  
Despite its limitations, modularity is still the most popular community detection metric [7] and it has been used in a variety of applications. Various optimisation algorithms have been proposed in literature that are based on a number of methodologies, including simulated annealing [8; 9], greedy algorithm [10], extremal optimisation [11], spectral algorithm [3] and integer programming-based optimisation model [12; 13; 14; 15; 16; 17].  
While modularity optimisation for undirected networks has been well studied over the past decade, little has been done for module detection in directed networks. Many real world networks are inherently directed, including the World Wide Web [18], brain neural networks [19] and metabolic networks, where the directed edge represents material flow from one substrate to a product that may be irreversible [20]. In literature, the conventional manner of tackling the problem of community detection in directed networks is simply to treat the networks as undirected and apply the methods described above [21]; however, such approaches lose valuable information carried in edge directionality. Some algorithms use edge directionality to transform directed graphs to weighted networks or bipartite networks [22]. Recent algorithms propose the use of spectral optimisation [23], local extraction of communities [24] and blockmodeling or statistical inference models [25].  
In this study, we use the mathematical description of modularity for directed networks introduced by [PERSON] and [PERSON] [26] that explicitly considers the in and out-degree distributions of nodes in the network. We propose a two-step algorithm named DiMod composed of two mathematical programming models to detect modules in directed networks by maximising modularity. The two models have equivalent objective functions, but the terms of the equations are rearranged differently to accentuate a desired property of the mathematical model, as described in the section below. We compare the results of our method to three algorithms implemented in the Radatools software (v.4.0, DEIM, Tarragona, Spain) [27] on synthetic and real networks used as test cases.