A New Random-Walk Based Label Propagation Community Detection Algorithm

Community detection is an effective tool for mining hidden information in social networks. Label propagation algorithms (LPA) have been proved to be very fast, which do not require prior information e.g., the number and the size of the communities. However, the results of these algorithms are random and not stable. In this paper, a novel random-walk based label propagation community detection algorithm (RWLPA) is proposed, which uses the distribution of position probability of random walker to measure the importance of nodes. Moreover, the sum of common neighbor´s weight has been introduced to merge the sub-communities. RWLPA can obtain a stable community detection result. Evaluations have been done in four datasets. In most cases, RWLPA obtains higher accuracy than other LPAs. A parallel algorithm is proposed to expand the algorithm to a larger dataset.