基于图神经网络的复杂网络关键节点检测算法_陈娜.pdf

642023 adio Engineering Vol.53 No.1doi:103969/jissn10033106202301009引用格式:陈娜基于图神经网络的复杂网络关键节点检测算法 J 无线电工程，2023，53(1):6472 CHEN NaAlgorithm forDetection of Crucial Nodes in Complex Networks Based on Graph Neural Network J adio Engineering，2023，53(1):6472基于图神经网络的复杂网络关键节点检测算法陈娜(山西工程科技职业大学 计算机工程学院，山西 晋中 030619)摘要:针对复杂网络关键节点检测算法准确性低及可靠性不足的问题，结合图神经网络(Graph Neural Network，GNN)模型提出了一种新的复杂网络关键节点检测算法。将复杂网络建模为图模型，通过注意力机制学习每个邻居节点的权重;利用 GNN 强大的图学习和推理能力，评估网络中节点与连接的关键性评分;采用强化学习(einforcement Learning，L)搜索 GNN 的超参数，从而提高关键节点检测算法的可扩展性及可靠性。仿真实验结果表明，由该算法检测的关键节点具有较高的准确性，并且具有较快的运算速度。关键词:复杂网络;关键节点检测;网络关键节点;社区检测;深度学习;深度神经网络中图分类号:TP391文献标志码:A开放科学(资源服务)标识码(OSID):文 章 编 号:10033106(2023)01006409Algorithm for Detection of Crucial Nodes in Complex NetworksBased on Graph Neural NetworkCHEN Na(College of Computer Engineering，Shanxi Vocational University of Engineering Science and Technology，Jinzhong 030619，China)Abstract:To deal with the problems of low accuracy and reliability of traditional crucial nodes detection algorithms for complexnetworks，a new crucial nodes detection algorithm for complex networks is proposed based on graph neural networks model Firstly，thecomplex networks are modeled as graph model，and the attention mechanism is utilized to learn the weight of each neighbor node;then，the powerful graph learning and inferential abilities of the graph neural network are used，as a result，the cruciality scores of nodes andlinks in the networks are evaluated;finally，the reinforcement learning is adopted to search the super parameters of the graph neuralnetworks in order to improve the scalability and reliability of the crucial nodes detection algorithm Simulation experimental results showthat the crucial nodes detected by the proposed algorithm are more accurate，at the same time，the computation speed of the proposedalgorithm is fastKeywords:complex networks;crucial nodes detection;crucial network node;community detection;deep learning;deepneural network收稿日期:20220905基金项目:国家社科基金(14BTQ027)Foundation Item:National Social Science Foundution of China(14BTQ027)0引言关键节点1 在复杂网络中处于重要地位，其行为对复杂网络中的信息传播具有极大的影响，分析并预测大规模复杂网络的关键节点在舆情传播、政策宣传和商业营销等领域均具有巨大的应用价值2。目前主流的关键节点挖掘方法根据技术差异可分为4 类3:基于评分规则的方法、基于复杂网络图的方法、基于影响传播模型的方法以及多维融合的方法。其中复杂网络图4 包含了丰富的网络结构信息，通过拓扑结构寻找关键用户，具有准确、高效的优点。度中心性5、接近中心性5、中介中心性6 可从不同角度评估节点在网络中的重要性，但这3 种评价方法的可靠性均不足。Pageank 算法7 是一种迭代的节点关键性评估指标，该指标基于特征向量中心度(Eigenvector Centrality)提高了评估的可靠性，但其计算量大，难以适用于大规模复杂网络。研究者们尝试通过图计算理论8 挖掘复杂网络图的隐含信息，以分析复杂网络中节点与连接的关键性。然而，图计算理论不具备自主学习的能力，因此可扩展性与可靠性均较弱。近年来，图神经网信号与信息处理2023 年 无线电工程 第 53 卷 第 1 期65络(Graph Neural Network，GNN)的出现促使人工智能步入“认知智能”时代9，现已被成功用于求解推荐系统10、数据聚类11 以及图像处理12 等问题，并展现出极大的发展潜力。通常，复杂网络中节点的邻居节点影响力越大，其自身影响力也越大，而GNN 的核心思想是借助神经网络的权重参数将邻居节点信息纳入当前节点，因此 GNN 可自动考虑节点相关的复杂网络拓扑信息。由现有的相关研究成果可知，虽然 GNN 能自主学习输入图模型的拓扑信息，且具有较强的可扩展能力，然而，GNN 在大规模数据上的训练难度较大，且无法自适应地处理动态变化的网络问题。诸多学者将强化学习(einforcement Learning，L)技术13 引入到深度神经网络的训练阶段，通过L 提高深度神经网络的自学习能力。目前利用 L成功训练的神经网络模型主要有:循环神经网络14、递归神经网络15 和径向基函数神经网络16 等，L 技术不仅能增强神经网络的自学习能力，而且提高了神经网络在不同任务上的应用效果。受上述研究成果启发，本文利用 L 技术训练 GNN，增强GNN 的自学习能力，进而提高复杂网络关键节点检测算法的可扩展性与可靠性。本文将复杂网络建模为图模型，采用双重鲁棒性指标作为节点的关键性评价标准，然后利用 GNN的节点嵌入模块学习复杂网络节点的拓扑结构信息，利用回归模块推理节点的关键性评分。此外，提出了基于 L 的 GNN 训练方法，该方法通过奖励函数学习 GNN 的超参数并输出一个动作序列，该动作序列对应该复杂网络关键节点识别的 GNN 模型。实验结果表明，本算法使用 GNN 检测的关键节点具有较高的准确性，且检测速度较快。1网络模型假设 G=(V，E)表示一个图，V 与 E 分别为图的节点集与连接集，关键节点检测问题可描述为搜索一个关键节点子集 Vc，该子集对图的鲁棒性具有极大的影响。假设 u 为复杂网络的一个节点，v=N(u)为 u 的邻居节点集，那么 u 的关键性评分函数可表示为:ru=f(hu，hv)，(1)式中，hu，hv分别为节点 u 与 v 的特征向量;ru为关键性评分。GNN 在训练过程学习复杂网络的关键性评分关系 f()，输出预测的关键性评分关系f()。2基于 GNN 的关键节点检测模型GNN 在复杂网络关键节点检测问题上的模型包括 3 部分:选取图鲁棒性指标评价节点的关键性，节点的关键性越高成为关键节点的可能性则越大。使用 GNN 的嵌入模块学习包含邻居信息的节点关键性评分。使用 GNN 的回归模块推断未知节点的关键性评分。21节点关键性评估系统鲁棒性指标在图理论中反映了某个节点缺失对图产生的影响，为了提高本算法的兼容性与鲁棒性，采用 2 个图鲁棒性指标评价节点的关键性:有效图抗。定义为图中每对节点的有效阻抗总和。有效图抗 g的计算方法为:g=2N 1Nci=11i，(2)式中，i为图 G 的拉普拉斯矩阵特征值;c 为 G 包含的连接总数量。加权谱。定义为图中 n-圆环的正则化总和。将 n-圆环定义为一个节点序列 u1，u2，un，其中 ui与 ui+1相邻。加权谱 Ws的计算方法为:Ws=i(1 i)n，(3)式中，n 为圆环形状，例如，n=3 表示图中的三角形数量，本文复杂网络问题中将 n 设为 4。22节点嵌入模块GNN 第 1 个子模块基于图拓扑结构信息与节点关键性评分学习复杂网络每个节点的嵌入向量。如果节点在复杂网络中距离越近，那么节点在嵌入空间中距离也越近。GNN 将复杂网络节点映射到嵌入空间的流程如图 1 所示。图 1GNN 的节点嵌入模块Fig1Node embedding module of GNN信号与信息处理662023 adio Engineering Vol.53 No.1节点嵌入模块包含 2 个步骤:步骤 1:根据每个节点及其邻居节点学习一个描述符。假设邻居跳数为 K，例如，K=2 表示目标节点 2 跳距离以内的节点为该节点的邻居。节点 u的邻居节点可表示为:N(u)=u:D(u，v)K，uG，(4)式中，函数 D()计算 2 个节点之间的最小跳数;u 为目标节点;v 为图中的其他节点。步骤 2:通过聚合函数为每个节点创建一个邻居嵌入，并为每个邻居嵌入分配一个权重。通过注意力模块自动学习每个邻居节点的权重，该步骤的数学模型可定义为:hlN(v)=At(Qlhl1k)，kN(v)，(5)式中，hlN(v)表示 GNN 网络中节点 v 在神经网络第l 层的嵌入;hl1k表示 v 的第 k 个邻居节点在神经网络第 l1 层的嵌入;Ql为神经网络第 l 层的注意力权重。图 G 中全部节点的嵌入可定义为:hlv=eLU(Wl hl1vhl2vhlN(v)，kN(v)，(6)式中，hlv表示节点 v 在神经网络第 l 层的嵌入;hl1vl与 hl2vl分别表示节点 v 在神经网络第 l1 层与第 l2 层的嵌入;hlN(v)表示节点 v 所有邻居嵌入的聚合结果。式(5)与式(6)分别对 GNN 的各层进行聚合运算，最终输出节点 v 的嵌入表示。算法 1 描述了节点嵌入表示的处理流程。算法 1节点嵌入表示算法输入:图 G，输入节点特征 Xv，组合权重 W，聚合权重 Q。输出:节点嵌入向量 zv。1h0v=Xv;初始化阶段2foreach l from 1 to L do3foreach v from 1 to V do4hlN(v)=Att(Qlhl1k);5hlv=eLU(Wlhl1vhl2vhlN(v);表示聚合运算6endfor7endfor8return hlv;23回归模块GNN 的回归模块如图 2 所示。嵌入模块的输出传入 GNN 的回归模块，回归模块将嵌入向量转换成标量，该标量作为节点的关键性评分。假设嵌入模块的输出为 y0v=zv，回归模块的输出可描述为:ymv=f(Wmym1v+bm)，(7)式中，ym