# Text Semantic Annotation: A Distributed Methodology Based on Community Coherence
## 2 Background
### Community Detection Algorithms  
Due to the extensive use of hierarchical data and its profitable application in copious sectors in industry, community detection has attracted the interest of the scientific community. Therefore, by adopting diverse techniques and by following principles of various scientific backgrounds, a profuse amount of research has been conducted for tackling this NP-hard class problem. As [PERSON] comprehensively presented [1], according to the evaluation strategy applied for unveiling the subjacent community hierarchy of any given information network, the existing methods can be distinguished into divisive algorithms, agglomerative algorithms, and other approaches. By originally considering the given information network as a single community, the principle idea of divisive algorithms is to identify and remove the edges interconnecting different sub-communities by the maximization of a global network topology criterion at each repetition. Specifically, considering the input graph as a single community, a well-defined network topology metric, such as edge betweenness, vertex centrality, split betweenness, flow betweenness, edge centrality, and information centrality, is repetitively calculated for any pair of directly connected nodes. At each iteration, the edges that maximize, or minimize accordingly, the previously calculated topological measure are considered inter-connection edges and thus removed. This repetitive procedure finishes once no further edge removal is feasible. Due to the inherent stepwise revelation of finer communities, the execution evolution of these methods can be presented as dendrograms. Among the ample number of divisive algorithms presented in [1], such as the [PERSON], [PERSON], and [PERSON] et al., the algorithm considered optimal in terms of execution performance and community extraction efficiency is that introduced by [PERSON] and [PERSON] [1]. Particularly, in case of sparse graphs, where the number of edges is linearly proportional to the number of nodes, this approach manages to identify the underlying community structure in O(m n\({}^{2}\)) time complexity, where n and m, respectively, denote the number of nodes and the number of edges. The topological metric adopted is the edge-betweenness, which is practically the number of shortest paths that each edge engages per repetition, and mathematically demonstrates its information spread. Despite the undoubted robustness of the definition of edge-betweenness, the excessive requirements for repetitively calculating the shortest paths for all possible pairs of nodes inevitably limit the application of this algorithm to merely small information networks. Contrary to the divisive algorithms, the agglomerative algorithms are bottom-up approaches that target an end result of a single community representing the input data graph. Specifically, by originally considering each node as an independent community, aka singletons, the ultimate goal of those methods is to repetitively merge the current step's communities by maximizing, or minimizing accordingly, a well-defined network topology-oriented similarity function. The formed meta-communities would apparently serve as the next iteration's communities. This iterative procedure ends if either a single community composed from the whole input data graph is formed or no further merging is possible. The extracted community structure's execution progress of the agglomerative algorithms can obviously be presented as a dendrogram, similarly to the divisive algorithm. There are many noteworthy agglomerative algorithms [1], such as the InfoMap, the fast greedy algorithm, the label propagation method, the Kernighan-Lin algorithm, and the Xiang algorithm. However, the algorithm that is generally considered the state of the art in terms of apparent interpretation, plain implementation, eminent community extraction performance, and efficient execution, is the Louvain algorithm [2].