دانلود رایگان مقاله الگوریتم تشخیص جامعه اجتماعی مبتنی بر لیبل انتشار خطای خاکستری موازی

Abstract

Community detection is one of the important methods for understanding the mechanism behind the function of social networks. The recently developed label propagation algorithm (LPA) has been gaining increasing attention because of its excellent characteristics, such as a succinct framework, linear time and space complexity, easy parallelization, etc. However, several limitations of the LPA algorithm, including random label initialization and greedy label updating, hinder its application to complex networks. A new parallel LPA is proposed in this study. First, grey relational analysis is integrated into the label updating process, which is based on vertex similarity. Second, parallel propagation steps are comprehensively studied to utilize parallel computation power efficiently. Third, randomness in label updating is significantly reduced via automatic label selection and label weight thresholding. Experiments conducted on artificial and real social networks demonstrate that the proposed algorithm is scalable and exhibits high clustering accuracy.

5. Conclusions

LPA, an efficient community detection algorithm, exhibits both merits and defects. In this study, we investigate the parallelization of the procedures of LPA and propose a fully parallel LPA. The calculation of vertex similarity on which label updating is based is parallel. Grey relational degree is integrated into Jaccard similarity to provide information for measuring similarity. The initialization and updating of the labels are also run in parallel, and multiple labels are allowed to be assigned to a vertex. Therefore, the proposed algorithm can discover overlapping communities. The experiments conducted on artificial and real networks demonstrate that the proposed algorithm runs well on both small and large networks. Several issues remain for further research. First, the label updating strategy can be enhanced to consider label weighting manners. Second, the algorithm can be improved further to be practical by considering both overlapping and hierarchical communities. Third, with the rapid emergence of new parallel computation frameworks aside from Hadoop and Spark, efficient parallel operators may be utilized to improve the performance of the algorithm.