基于节点影响力的理性节点标签传播算法

A rational label propagation algorithm based on node influence

社区发现能够揭示真实社会网络的拓扑结构和重要节点。由于具有线性时间复杂度,无需定义目标函数及目标参数,标签传播算法(LPA)作为经典社区发现算法被广泛应用在学术和实践领域。针对LPA算法更新顺序的无序性和标签选择的随机性,提出基于节点影响力的理性节点标签传播算法(RLPBNI)。将节点影响力排序作为更新顺序,引入理性节点概念进行标签选择,并定义重叠度进行社区再降维。实验结果表明,与其他对比算法相比,RLPBNI算法不但可有效提高社区划分精度,且更容易发现混合程度较高的网络中隐藏的社区。

Community discovery can reveal the topology and important nodes of real social networks.Due to its linear time complexity and no need to define objective functions and objective parameters,Label Propagation Algorithm(LPA)is widely used in academic and practical fields as a classic community discovery algorithm.Aiming at the update disorder of LPA algorithm and the randomness of label selection,a Rational Node Label Propagation Algorithm Based on Node Influence(RLPBNI)is proposed.The algorithm takes the node influence ranking as the update order,introduces the concept of rational nodes for label selection,and defines the overlap degree for community dimensionality reduction.The analysis of the experimental results shows that,compared with other comparative algorithms,the RLPBNI algorithm can not only effectively improve the accuracy of community division,but also more easily discover hidden communities in networks with a high degree of mixing.