|
今天给大家介绍哈佛大学Yang-Yu Liu课题组和加利福尼亚大学洛杉矶分校Yizhou Sun课题组发表在nature machine intelligence上的一篇文章“Finding key players in complex networks through deep reinforcement learning”，作者提出一种基于深度强化学习框架FINDER来寻找一组能对网络功能产生最大影响的关键节点序列。  研究背景 寻找网络中一组最优节点集合是网络科学中的重要课题。删除（增添）一部分重要的节点能极大减弱（增强）网络的连通性，从而影响网络的功能，利用这一特性，可以高效地破坏网络结构，也可以设计出对于攻击或者扰动表现出更优鲁棒性的网络。传统方法难以兼顾效率和性能，且大多数只针对特定的场景。得益于近年来深度学习在组合优化问题的发展，Fan Changjun等提出了一种基于深度强化学习的方法来寻找网络中的关键节点序列。  2 研究方法 整个深度学习过程的目的：使累积归一化的连通性ANC最小。对于节点无权值的网络，作者定义ANC为：
critical node（CN）问题中，被定义为
其中为节点移除后损失系数，且 整个深度强化学习过程中，将移除节点后的残余网络定义为状态，决策为移除（或激活）已经确定的关键节点，收益为累积归一化连通性的衰减。具体的深度学习过程主要包括以下四个步骤： (1) 编码 编码的目的是利用基于神经网络的图表征学习，将网络的结构信息转化为低维嵌入向量。具体做法是采用一种类似于GraphSAGE的归纳式图表征学习方法来聚合节点嵌入向量，这些向量被初始化为该节点的邻居的特征（如度，移除代价），接着通过一个附带可学习参数的非线性算子转换,将网络节点信息聚合K次，可以将其视为K次神经网络，当前层节点的嵌入向量由上一层该节点以及它邻居的嵌入向量获得，最后一层为输出层，即得到关于每个节点的嵌入向量，这些向量包含了节点的结构位置以及节点特征间的长期交互作用信息。 为了得到网络更为复杂的信息，引入一个虚拟节点，该节点以网络中所有真实节点为邻居，而这些真实节点的邻居不包含该虚拟节点。重复上面的图表征学习方法，得到该节点的嵌入向量。 （2）解码 在解码过程中，作者定义一个评分函数Q function, 利用编码过程得到状态和决策的嵌入信息，计算出一个关于节点的得分Q来评价可能的决策的优劣。根据得分Q采取贪心策略，具体做法是以概率选中Q值最大的节点，以1-的概率随机选择其他节点。作者在实验过程中实际采取的策略是以概率选择Q值最大的前k个节点，以微小的精度损失来减小时间复杂度。 当残余网络只包含孤立节点，收集n步转移信息，即4元组并将它们存入经验回放缓冲区，执行贪心策略50000次，同时更新参数。 （3）训练模型 该过程是为了得到合适的参数。作者定了损失函数如下：
其中,,为在经验回收缓冲区采样得到关于未来收益更为精确的值，表示折扣因子，为更新后的网络参数，表示节点有连边，为节点的嵌入向量，为原始网络的节点数，函数包含两部分：1. Q-learning loss使预测值和目标值误差最小；2. 在嵌入空间中，Graph reconstruction loss用来保留原始网络结构。实验中作者采用30-50个节点的BA网络模型，进行大量训练，最终使以上损失函数的值最小。 （4） 应用 将训练好的模型用于合成网络和真实网络，这个过程中为了减小时间复杂度，作者每次移除一部分节点而不是每次移除一个。实验最终发现：移除网络1%的节点对网络的性能几乎没有影响。 3 数据 作者将训练的模型分别用于两类网络数据集：1. 人工生成的网络不同规模的BA网络各100个，节点个数分为为30-50,50-100，100-200,200-300,300-400以及400-500。2. 真实网络：Crime,HI-II-14,Digg,Enron,Gnutella31,Epinions,Facebook,Youtobe，Flickr,具体信息如下：  4 实验 对于人工生成三类网络数据：节点无权值网络，节点权值与度成比例的网络以及随机节点权值网络，针对关键节点(CN)和网络分解(ND)两个问题，作者将提出FINDER框架与其他方法进行比较，最终得出结论：在节点权值分布不同的网络中，无论是CN问题还是ND问题，FINDER始终优于其他方法。具体表现为采用FINDER方法移除相同百分比的节点，对网络的连通性破坏更严重。  对于真实网络，节点都是无权的，为了改变节点权值，作者采取了两种策略：1. 将与度成比例非负数赋予节点获得node-degree网络，2. 随机将权值赋予节点获得node-random-weight网络。依然针对CN问题和ND问题，作者将FINDER方法与其他方法进行对比，下图显示，移除相同比例的节点，FINDER能更大程度破坏这些真实网络的连通性，图表示随着移除节点的比例变化，网络的连通性的变化。对于CN问题，网络连通性表示为  对于不同的情况（网络权值分布差异，CN与ND问题的不同），FINDER优于其他方法。特别地，对于节点权值不同的网络，即 node-degree-weight以及node-random-weight网络，FINDER应用后的表现远远超过其他方法。如图k中，为了实现网络连通性衰减为50%，其他方法需要移除整个网络中超40%的节点，应用FINDER则只需要移除大约14%的节点，即实现对网络相同的破坏效果 ，FINDER方法更为高效。 FINDER性能分析 当网络节点权值存在差异时，FINDER在寻找关键节点时性能远胜过其他方法。为了探究其原因，作者在真实网络crime中给节点随机分配权值（节点移除的代价），并绘制出不同方法寻找到的关键节点的代价分布直方图，从图中可以看到：无论是CN问题还是ND问题，FINDER寻找出的关键节点往往移除代价较小，从而能够实现一种更为高效的节点移除策略。 5 结论 作者提出了一种深度强化学习框架FINDER，该方法只采用小规模的BA网络进行训练，而将它应用于寻找大型真实网络的关键节点时，无论在效率还是性能上都表现优异。针对不同的网络问题，依据定义的连通性度量方式选择对应奖励机制即可。FINDER的表现体现了BA网络模型的应用价值，加深了深度学习技术与复杂网络的融合。应用FINDER也有助于设计出鲁棒性更强的网络系统。 数据与代码 https:///10.24433/CO.3005605.v1 https://github.com/FFrankyy/FINDER 参考资料 Fan, C., Zeng, L., Sun, Y. et al. Finding key players in complex networks through deep reinforcement learning. Nat Mach Intell 2, 317–324 (2020). https:///10.1038/s42256-020-0177-2 |
|
|
，其中为原网络的节点个数，为第块连通块的大小（节点个数），为原网络的连通性，为从原网络中移除节点序列后的连通性。网络分解问题(ND)中，被定义为，即极大连通子图的大小。对于有些问题，节点被分配了不同的权值，ANC被重新定义为：
。
，对于ND问题，连通性为
