Please use this identifier to cite or link to this item:
Scopus Web of Science® Altmetric
Type: Journal article
Title: Improved network community detection using meta-heuristic based label propagation
Author: Le, B.
Shen, H.
Nguyen, H.
Falkner, N.
Citation: Applied Intelligence, 2019; 49(4):1451-1466
Publisher: Springer
Issue Date: 2019
ISSN: 0924-669X
Statement of
Ba-Dung Le, Hong Shen, Hung Nguyen, Nickolas Falkner
Abstract: 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.
Rights: © Springer Science+Business Media, LLC, part of Springer Nature 2018
RMID: 0030103803
DOI: 10.1007/s10489-018-1321-0
Grant ID:
Published version:
Appears in Collections:Computer Science publications

Files in This Item:
There are no files associated with this item.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.