摘要
识别复杂网络中的关键节点对分析网络结构、控制传播过程具有十分重要的意义。经典的关键节点识别算法已被拓展应用到各类现实网络的分析中,各种方法存在优势的同时,也存在一定缺陷。针对交通网络中现有关键节点识别算法多数没有兼顾节点的局部特征和网络全局环境的问题,提出了一种基于“结构洞”的Page Rank改进算法——ST-Page Rank。该方法通过分析节点在全局网络中的位置和邻居节点间的拓扑结构关系,利用结构洞的重要性指标来表征交通网络相邻节点间的客流贡献关系,克服了Page Rank算法存在的平均分配缺陷以及结构洞忽略了网络全局属性的不足,将“结构洞”和“Page Rank算法”的优点融为一体。仿真实验部分选取真实的美国航空网络,利用SIR传播模型和肯德尔相关系数进行评价,将ST-Page Rank与度中心性、紧密中心性、介数中心性、特征向量中心性、K-shell分解法、Page Rank算法以及结构洞约束系数识别结果进行对比。实验结果表明,所提算法能合理、有效地识别交通网络中的关键节点,具有一定的理论和实践意义。
It is very important to identify the key nodes in complex networks for analyzing the network structure and controlling the propagation process.The classic algorithm for key node recognition has been extended and applied to the analysis of various real networks.While various methods have their respective advantages,they also have certain shortcomings.In view of the fact that most of the existing key node recognition algorithms in the transportation network do not take into account the local characteristics of the nodes and the global environment of the network,this paper proposes an improved Page Rank algorithm(ST-Page Rank)based on the"structure hole".By analyzing the position of nodes in the global network and the topological structure relationship between neighbor nodes,this method uses the importance index of structural holes to characterize the passenger flow contribution relationship between adjacent nodes in the traffic network,which overcomes the shortcomings of the average distribution in the Page Rank algorithm and deficiencies of the global network attributes in the structural holes,and combines the advantages of"structural holes"and"Page Rank".Simulation experimental part selects the real American aviation network,uses the SIR propagation model and Kendall correlation coefficient to evaluate,and decomposes ST-Page Rank with degree centrality,closeness centrality,betweenness centrality,eigenvector centrality,and K-shell decomposition.Comparing the recognition results of the method,Page Rank algorithm and structural hole constraint coefficients,the experimental results show that the algorithm proposed in this paper can identify key nodes in the transportation network reasonably and effectively,and is of certain theoretical and practical significance.
作者
王秋玲
贺僚僚
徐宏
魏子昂
柯宇昊
官文英
朱璋元
WANG Qiuling;HE Liaoliao;XU Hong;WEI Zi'ang;KE Yuhao;GUAN Wenying;ZHU Zhangyuan(College of Transportation Engineering,Chang’an University,Xi’an 710064,China;China Railway First Group Limited Company,Xi'an 710054,China)
出处
《西安电子科技大学学报》
EI
CAS
CSCD
北大核心
2021年第6期197-203,共7页
Journal of Xidian University
基金
国家社会科学基金重大项目(20&ZD099)
陕西省交通运输厅科研项目(20-34X)
长安大学中央高校基本科研业务费专项资金(300102341102)。
关键词
关键节点识别
结构洞
SIR传播模型
肯德尔系数
key node identification
structural hole
SIR propagation model
Kendall coefficient
