Computer Engineering and Applications ›› 2022, Vol. 58 ›› Issue (16): 184-193.DOI: 10.3778/j.issn.1002-8331.2203-0148

• Pattern Recognition and Artificial Intelligence • Previous Articles     Next Articles

Discovering Critical Nodes of Social Networks Based on Propagation Features

QIAN Rong, WANG Jiarui, XING Fangyuan, XU Jianting, ZHANG Kejun   

  1. 1.Beijing Electronic Science and Technology Institute, Beijing 100070, China
    2.Xidian University, Xi’an 710071, China
  • Online:2022-08-15 Published:2022-08-15

基于传播属性的社交网络重要节点发现

钱榕,王嘉瑞,邢方远,许建婷,张克君   

  1. 1.北京电子科技学院,北京 100070
    2.西安电子科技大学,西安 710071

Abstract: Node importance ranking is widely used in the field of complex networks. The improved iterative resource allocation algorithm(IIRA) based on node propagation features improves the accuracy of node importance ranking. However, the algorithm does not consider the impact of node similarity on node resource allocation. In view of its shortcomings, a similarity-based resource allocation algorithm(SBRA) with node similarity as the input indicator is proposed to make the resource allocation strategy more in line with the real social network. On the basis of SBRA algorithm, referring to the idea of background node in LeadeRank algorithm, a LeadeRank similarity-based resource allocation algorithm(L-SBRA) is proposed. Finally, based on the SIR model of propagation dynamics, through the comparative experiments between various algorithms, the rationality of the similarity as the basis for resource allocation and the introduction of background node is verified, and the effectiveness and superiority of the improved algorithm are proved.

Key words: complex network, social network, critical node, propagation features

摘要: 节点重要性排序在复杂网络领域中有着广泛的应用。基于节点传播属性的迭代资源分配改进算法(improved iterative resource allocation,IIRA)通过引入节点传播属性,提升了节点重要性排序的准确性,但该算法并未考虑节点相似性对节点资源分配的影响,存在局限性。针对其不足,提出了一种以节点相似性为输入指标的资源分配算法(similarity-based resource allocation,SBRA),使得资源分配策略更加符合真实的社交网络;在SBRA算法的基础上借鉴LeaderRank算法中背景节点的思想,引入高阶邻居节点间的资源流动,提出了一种基于节点相似度和高阶流动资源分配算法(LeaderRank similarity-based resource allocation,L-SBRA);基于传播动力学的SIR模型,通过各算法之间的对比实验,验证了相似性作为资源分配依据以及引入背景节点的合理性,并且证明了改进算法的有效性和优越性。

关键词: 复杂网络, 社交网络, 重要节点, 传播属性