GLLPA: A Graph Layout based Label Propagation Algorithm for community detection

摘要

Community is an important property of networks. Recently, label propagation based community detection algorithms develop rapidly, since they can discover communities with high efficiency. However, the results of most of them are inaccurate and unstable because the node order of label updating and the mechanism of label propagation are random. In this paper, a new label propagation algorithm, Graph Layout based Label Propagation Algorithm (GLLPA), is proposed to reveal communities in networks, which aims at detecting accurate communities and improving stability by exploiting multiple graph layout information. Firstly, GLLPA draws networks to compact layout based on the force-directed methods with (a,r)-energy model, then a label initialization strategy is proposed to assign the nodes locating in a position with the same label. Secondly, GLLPA begins to draw networks to uniform layout and conduct community detection simultaneously, in which we design node influence and label influence based on node attraction in the uniform layout to handle the instability problem and enhance its accuracy and efficiency. Experimental results on 16 synthetic and 15 real-world networks demonstrate that the proposed method outperforms state-of-the-art algorithms in most networks. (C) 2020 Elsevier B.V. All rights reserved.