LILPA: A Label Importance Based Label Propagation Algorithm for Community Detection with Application to Core Drug Discovery

Abstract Community is an important feature of complex networks. Many label propagation based algorithms are proposed to detect communities in networks because of their high efficiency, however, most of their results are unstable due to the randomness of the node order of label update and the order of label choice. In this paper, a novel label propagation algorithm, Label Importance based Label Propagation Algorithm (LILPA), is proposed to discover communities by adopting fixed label update order based on the ascending order of node importance, utilizing label importance based on node importance and node attraction when labels are launched to other nodes and employing label update process based on node importance, node attraction and label importance for improving the instability and enhancing its accurate and efficiency. Meanwhile, Core Drug Discovery for Indications (CDDI) is a popular research field in Traditional Chinese Medicine (TCM). Then we apply LILPA in a drug network to discover drug communities and core drugs for treating different indications in TCM. Experimental results on 16 synthetic and 10 real-world networks demonstrate that LILPA obtains better accuracy and stability than state-of-the-art approaches. In addition, LILPA can discover effective core drugs in drug networks.