计算机应用 ›› 2019, Vol. 39 ›› Issue (9): 2669-2674.DOI: 10.11772/j.issn.1001-9081.2019020324

• 网络与通信 • 上一篇    下一篇

基于H运算的动态网络重要节点识别方法

邵豪1, 王伦文1, 邓健2   

  1. 1. 国防科技大学 电子对抗学院, 合肥 230037;
    2. 陆军工程大学石家庄校区 二系, 石家庄 050003
  • 收稿日期:2019-02-27 修回日期:2019-05-07 发布日期:2019-06-17 出版日期:2019-09-10
  • 通讯作者: 邓健
  • 作者简介:邵豪(1995-),男,浙江金华人,硕士研究生,主要研究方向:网络拓扑识别、网络行为分析;王伦文(1966-),男,安徽怀宁人,教授,博士,主要研究方向:智能信息处理;邓健(1997-),男,安徽合肥人,主要研究方向:电子信息处理。
  • 基金资助:

    国防科技创新特区项目(17-H863-01-ZT-003-204-03)。

Important node identification method for dynamic networks based on H operation

SHAO Hao<sup>1</sup>, WANG Lunwen<sup>1</sup>, DENG Jian<sup>2</sup>   

  1. 1. Institute of Electronic Countermeasure, National University of Defense Technology, Hefei Anhui 230037, China;
    2. Second Department, Shijiazhuang Campus, Army Engineering University, Shijiazhuang Hebei 050003, China
  • Received:2019-02-27 Revised:2019-05-07 Online:2019-06-17 Published:2019-09-10
  • Supported by:

    This work is partially supported by Science and Technology Innovation Special Zone Project of Military (17-H863-01-ZT-003-204-03).

摘要:

传统K-shell网络重要节点识别方法迭代时需网络全局拓扑信息,而且难以应用于动态网络。为解决该问题,提出基于邻域优先异步H运算的动态网络重要节点识别方法。首先,证明该算法收敛于Ks值,其次以各节点的度作为h指数初始值;然后,通过节点h指数排序和邻居节点h指数变化选择更新节点,同时针对动态网络节点的增减数目和最大度,修改h指数适应拓扑变化,直至算法收敛并找到重要节点。仿真实验结果表明,该方法通过邻居节点局部信息且以更高效率找到动态网络的重要节点,收敛时间在静态网络中较随机选择更新节点法与变化邻居选点法分别下降77.4%和28.3%,在网络拓扑变化后分别下降84.3%和38.8%。

关键词: 动态网络, 重要节点, h指数, H运算, K-shell, 邻居节点

Abstract:

Focused on the issue that the traditional important node identification method for K-shell networks needs global topology during iteration and cannot be used in dynamic networks, an important node identification method for dynamic networks based on neighborhood priority asynchronous H operation was proposed. Firstly, the algorithm was proved to converge to Ks (K-shell) value; then the degree of each node was taken as the initial value of h-index, and the nodes to be updated were selected by the h-index ranking of the node and the h-index change of the neighbor nodes; meanwhile the h-index was modified to adapt to the topology change according to the number change and maximum degree of the dynamic network nodes, finally the algorithm converged to the Ks and the important nodes were found. The simulation results show that the algorithm can find important nodes effectively by local information of neighbor nodes with less convergence time. Compared with the random selection algorithm and the neighborhood-variety selection algorithm, the convergence time of the proposed algorithm decreases by 77.4% and 28.3% respectively in static networks and 84.3% and 38.8% respectively in dynamic networks.

Key words: dynamic network, important node, h-index, H operation, K-shell, neighbor node

中图分类号: