Improved network community detection using meta-heuristic based label propagation

摘要

Label propagation is a low complexity approach to community detection in complex networks. The current state-of-the-art label propagation based algorithm (LPAm+) detects communities using a two-stage iterative procedure: the first stage is to assign labels, or community memberships, to nodes using label propagation to maximize modularity, a well-known quality function to evaluate the goodness of a community division, the second stage merges smaller communities to further improve modularity. LPAm+ achieves an excellent performance on networks of strong communities, which have more intra-community links than inter-community links. However, as the label propagation procedure in LPAm+ uses a greedy heuristic to maximize modularity, LPAm+ tends to get trapped in poor local maxima on networks with weak communities, which have more inter-community links than intra-community links. We overcome this drawback of LPAm+ by introducing a novel label propagation procedure inspired by the meta-heuristic Record-to-Record Travel algorithm to improve modularity before merging communities. To handle directed networks, we employ a directed version of modularity as the objective function to maximize. We also perform an empirical analysis to examine the sensitivity of our algorithm to its parameters. Experimental results on synthetic networks show that the proposed algorithm, named meta-LPAm+, outperforms LPAm+ in term of modularity on networks with weak communities while retaining a comparable performance on networks of strong communities. For 8 widely used real-world networks, meta-LPAm+ finds the highest modularity value obtained by previously published algorithms on 5 networks and has a comparable or higher modularity value than these algorithms on 3 other networks.