基于不等概率叠加随机游走关键点识别-《计算机技术与发展》

文章信息/Info

Title:: Key Point Recognition Based on Unequal Probability Superposition Random Walk

Author(s):: NING Yang; WU Zhi-feng; ZHANG Ce; School of Information Technology Engineering,Tianjin University of Technology and Education,Tianjin 300222,China

Keywords:: Jaccard similarity; superimposed random walk; key node identification; SIR spread model; Kendall tau distance

摘要:: 关键节点识别是网络科学的重要研究内容,在医学、社会学、网络安全、电力交通、政治与经济学领域有重要研究意义。当前流行的关键点识别算法的原理是通过考虑局部范围和全局范围网络节点的特性衡量节点中心性,结合节点自身及邻居节点贡献进行关键节点识别。存在识别有效性低和时间复杂度高的问题, 不能在大规模网络中扩展。针对等概率叠加随机游走关键点识别方法没有考虑随机游走倾向性问题,? 采用节点相似性构造转移概率矩阵的方法,开展了不等概率叠加随机游走进行关键点识别的研究。通过在无向网络中与度中心性、介数中心性、接近中心性、等概率叠加随机游走评估方法间进行比较,各中心性算法与 SIR 模型的相关性比较的实验, 证明基于不等概率叠加随机游走能以较高的精度进行网络中关键点识别, 并且优于等概率叠加随机游走方法。

Abstract:: Key node identification is an important research content of network science,which has important research significance in the fields of medicine, sociology, network security, power transportation, politics and economics. The principle of the current key point recognition algorithm is to measure the centrality of nodes by considering the characteristics of local and global network nodes,and to identify key nodes by combining the contributions of nodes themselves and their neighbors. There are some problems such as low recognition efficiency and high time complexity,which cannot be extended in large-scale networks. Aiming at identifying key points of equal probability stacked random walk without considering the tendency of random walk,we use the method of constructing transition probability matrix by node similarity to carry out the research of identi-fying key points of different probability stacked random walk walk. By comparing the evaluation methods of degree centrality, closeness centra-lity, betweenness centrality and equal probability stacking random walk in undirected networks,and comparing the correlation of each centrality algorithm with SIR model,it is concluded that random walk based on unequal probability stacking can identify key points in networks with high accuracy. And it is superior to the conclusion of equal probability superposition random walk method.