Community Detection Based on Modularity and k-Plexes

Community identification is of great worth for analyzing the structure or characteristics of a complex network. Many community detection methods have been developed, such as modularity-based optimization models, which are widely used but significantly restricted in “resolution limit”. In this paper, we propose a novel algorithm, called modularity optimization with k-plexes (MOKP), to solve this problem, and this algorithm can identify communities smaller than a scale. The proposed algorithm uses k-plexes to generate community seeds from the whole network and assigns the remaining nodes by modularity optimization. To save computational time, we further propose the improved MOKP algorithm (IMOKP) by reducing the scale of the network before community seeds generation and adjusting rules of nodes assignment. Extensive experimental results demonstrate our proposed algorithms perform better than several state-of-the-art algorithms in terms of accuracy of detected communities on various networks, and can effectively detect small communities in terms of a newly defined index, namely small community level, on multiple networks as well.