A fast divisive community detection algorithm based on edge degree betweenness centrality

摘要

Many complex systems in the real world such as social networks can be modeled by complex networks. The complex network analysis and especially community detection is an important research topic in graph analysis that aims to identify the structure of a graph and its similar groups of nodes. In recent years, various algorithms such as Girvan and Newman’s method (GN) is introduced which is based on a divisive approach for graph clustering. Although GN is a highly popular and widely used method, it suffers from scalability and computational complexity. GN needs O(m3) and O(m3 + m3logm) time to detects communities in unweighted and weighted graphs respectively. Hence, in this paper, a faster method is suggested that detects communities in O(m2) for both weighted and unweighted graphs. In this paper, firstly, we define degree for each edge and then we propose a new and fast approach for the calculation of edges betweenness that is based on edge degree centrality. Furthermore, in order to boost the speed of the algorithm, we suggest instead of just one edge, multiple edges can be removed in each iteration. Since the proposed method wants to enhance the GN method, in the evaluation section the quality of detected communities, the accuracy and speed of the suggested method are assessed by the comparison with the GN method. Results prove that our proposed method is extremely faster than plain GN and the detected communities often have better quality than the plain GN method. Furthermore, we compare our proposed method with meta-heuristic algorithms which are a novel approach for community detection. Results clarify that the suggested method is notably faster, scalable, stable, reliable, and efficient than meta-heuristic algorithms.