Local Random Walk Based Label Propagation Algorithm

Abstract

Community structure is one of the important characteristics of complex networks.Identifying communities of different functions in a network plays an important role for revealing important characteristics of complex networks.The community discovery algorithm based on label propagation uses the community label of direct neighbors of a node to updates its label,which might obtain inaccurate community structures.Furthermore,the results of multiple runs of the algorithm might be unstable.To solve this problem,a local random walk based label propagation algorithm(LRW-LPA) is proposed.First,the local importance of each node in its k-step neighborhood is calculated.Then,the node with the lowest local importance is selected as the starting node to perform the local random walk process.When walking out of the specified neighborhood,the random walker will return to the starting node and start the random walk again.Finally,the algorithm selects the label with the most occurrences in the local neighborhood to update the label of the starting node,and selects the label of the node with highest importance when there are multiple labels with the most occurrences.Due to LRW-LPA can determine an appropriate neighborhood of a node by adopting the local random walk process with restart,the stability of the algorithm improves greatly.Compared with LPA,BGLL,Infomap,Leiden,Walktrap and other classical algorithms on 12 real networks and 12 synthetic networks,it shows that the proposed LRW-LPA algorithm performs well in terms of normal mutual index(NMI),adjusted rand index(ARI) and modularity(Q).

Keywords

• complex network|clustering|community detection|label propagation|local random walk