基于路径的投票算法识别关键节点组的研究  

Identifying Key Node Group Based on Path Voting Algorithm

作　　者：宁阳 宁晴 武志峰[3] NING Yang;NING Qing;WU Zhifeng(Tianjin Electronic Information College,Tian’jin 300350,China;Beijing Union University,Beijing 100101,China;Tianjin University of Technology and Education,Tian’jin 300222,China)

机构地区：[1]天津电子信息职业技术学院,天津300350 [2]北京联合大学,北京100101 [3]天津职业技术师范大学,天津300222

出　　处：《信息工程大学学报》2022年第2期167-172,178,共7页Journal of Information Engineering University

基　　金：国家自然科学基金青年科学基金资助项目(61601331);天津市自然科学基金青年科学基金资助项目(18JCQNJC04700)。

摘　　要：关键节点组识别在医学、社会学、电力交通、政治与经济学领域有重要研究意义。目前识别方法基本上是与其他理论的结合,例如图着色、社区划分、聚类、投票算法等。针对启发式聚类关键节点组识别方法中初始节点选择造成的随机性问题,结合投票算法,提出了基于路径的投票算法进行关键节点识别。基于SIR传播模型和平均路径长度设计了4组对比实验,在人工BA无标度网络和真实网络中分别与度中心性、介数中心性、接近中心性、启发式聚类算法评估方法进行比较,验证了基于路径的投票算法能以较高的精度进行网络中关键节点组的识别,并且优于启发式聚类算法。Key node group identification is of great significance in the fields of medicine,sociology,power transportation,politics and economics.At present,recognition methods are basically combined with other theories,such as graph coloring,community partition,clustering,voting algorithm and so on.To address the random problem caused by the initial node selection in the heuristic clustering key node group identification method,combined with the voting algorithm,a path based voting algorithm is proposed to identify the key nodes.Based on SIR propagation model and average path length,four groups of comparative experiments are designed,and compared with the evaluation methods of degree centrality,betweenness centrality,closeness centrality and heuristic clustering algorithm respectively in artificial BA scale-free network and real network.It is verified that the voting algorithm based on path can identify the key node groups in the network with high accuracy,and is better than Heuristic Clustering algorithm.

关 键 词：复杂网络 关键节点组 最短路径 投票算法 SIR传播模型 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]