Discovering community structure in social networks based on the synergy of label propagation and simulated annealing

Community detection is one of the critical research areas in the analysis of complex networks. Numerous algorithms have been devised for this purpose. Despite advances in this field, existing methods are far from accurately identifying the ground-truth community structures of many complex networks. In this paper, we propose a hybrid community detection method, named LPASA, to uncover communities in complex networks accurately. The proposed method is based on label propagation and the simulated annealing algorithm. Label propagation is a fast and straightforward community detection approach that utilizes the topological features of the input network. LPASA uses label propagation to provide the initial population and choose the best starting point for the next phase. Since community detection is an NP-complete problem, meta-heuristic methods such as Simulated Annealing (SA) can also be used for this problem. The SA Algorithm is a renowned and influential meta-heuristic algorithm for finding the global optimal. The proposed method uses a problem-specific variant of the SA algorithm to efficiently convergence to the best possible solution. To this end, instead of a completely random move from the current solution to a neighboring one, a pseudo-random motion is used that considers the network structure. LPASA needs no prior information to discover network communities. The experiments on synthetic and known real-world networks have shown that LPASA is accurate and comparable with the state-of-the-art community detection methods. The results showed that LPASA could improve the mean modularity up to 49.27% on real-world networks compared to various tested methods.