一种改进的基于相干邻居亲近度的标签传播算法

An Improved Label Propagation Algorithm Based on Coherence Neighborhood Propinquity

关键词:  社区发现  标签传播算法  相干邻居亲近度  节点间依赖度  核心CNP网络

Key words:  community detection  label propagation algorithm  coherent neighborhood propinquity  coherent neighborhood dependence  core CNP network

摘要:

[目的]提高现有的基于相干邻居亲近度(Coherence neighborhood propinquity)的标签传播算法(Label propagation algorithm,LPA)社区发现的准确性,并减少标签传播过程花费的时间。[方法]在CNP-LPA算法基础上,引入节点间依赖度,提出一种改进的CNP-LPA+算法,在预处理阶段结合相干邻居亲近度与节点间依赖度,将依赖度高的节点并入本区域内的核心节点,并在得到的核心CNP网络基础上传播标签,显著提高了社区发现的质量。选取CNP-LPA算法使用的6组社交网络数据集,采用模块度Q评估LPA、CNP-LPA、CNP-LPA+3种算法的划分结果。[结果]CNP-LPA+算法在所有数据集上均取得了最高的Q值,有效提高了算法的准确性,并减少了标签传播过程花费的时间。[结论]CNP-LPA+算法是有效的。

Abstract:

[Objective] To improve the accuracy of community detection by CNP-LPA and reduce the time it takes for the label propagation process.[Methods] In this paper,an improved CNP-LPA+ algorithm is proposed.In the preprocessing stage,the nodes with high dependency are integrated into the core nodes of the local region according to the coherent neighborhood propinquity and dependency.The quality of communities is significantly improved by spreading labels on the core CNP network.Six groups of social network data sets are selected,the modularity measure Q is used to evaluate the results of detecting by LPA,CNP-LPA,CNP-LPA+ algorithms.[Results] Experiments show that the CNP-LPA+ algorithm achieves the highest Q value on all data sets, which improves the accuracy of the algorithm and reduces the time spent on the label propagation process.[Conclusion] CNP-LPA+ algorithm is effective.