Improved Weighted Label Propagation Algorithm in Social Network Computing

摘要

Nowadays social networks play an important role in people's daily life, where community detection is essential for business as well as security applications. And weighted networks are gradually taking the dominance in social networks whose attributes of the connections can be recorded and accessed flexibly. As the classic community detection algorithm Label Propagation Algorithm(LPA) failed to handle weighted social networks, the Weighted Label Propagation Algorithm(WLPA) was proposed recently. However, the WLPA still exposes insufficient accuracy, and costly time complexity compared with the LPA. In this paper, we optimize the WLPA in accuracy and execution time by modifying the propagation intensity and order in the label propagation process. And the optimization methods are confirmed to be efficient both in theoretical analysis and experimental verification. Moreover, the specific functions of the optimization methods are discussed in detail during the experiment. By means of the optimized community detection algorithm, we manage to extract the useful information of the Twitter social network. We also make use of the network visualization tool to recognize the concrete network structure and validate the community detection result.