Community Detection in Networks with Less Significant Community Structure

摘要

Label propagation is a low complexity approach to community detection in complex networks. Research has extended the basic label propagation algorithm (LPA) in multiple directions including maximizing the modularity, a well-known quality function to evaluate the goodness of a community division, of the detected communities. Current state-of-the-art modularity-specialized label propagation algorithm (LPAm+) maximizes modularity using a two-stage iterative procedure: the first stage is to assign labels to nodes using label propagation, the second stage merges smaller communities to further improve modularity. LPAm+ has been shown able to achieve excellent performance on networks with significant community structure where the network modularity is above a certain threshold. However, we show in this paper that for networks with less significant community structure, LPAm+ tends to get trapped in local optimal solutions that are far from optimal. The main reason comes from the fact that the first stage of LPAm+ often misplaces node labels and severely hinders the merging operation in the second stage. We overcome the drawback of LPAm+ by correcting the node labels after the first stage. We apply a label propagation procedure inspired by the meta-heuristic Record-to-Record Travel algorithm that reassigns node labels to improve modularity before merging communities. Experimental results show that the proposed algorithm, named meta-LPAm+, outperforms LPAm+ in terms of modularity on networks with less significant community structure while retaining almost the same performance on networks with significant community structure.