无悔学习算法增强复杂网络鲁棒性

⃝=⃝可在www.sciencedirect.com在线ScienceDirectICT Express 5（2019）163www.elsevier.com/locate/icte基于无悔学习的复杂网络鲁棒性增强孙仁秀韩国首尔东国大学电子电气工程系接收日期：2018年9月14日;接受日期：2018年2018年10月11日在线提供摘要优化复杂网络以使其对各种攻击模型具有弹性一直是学术界积极研究的重要问题。在所提出的优化方法中，各个节点的程度是平衡迭代的基础上的无遗憾学习算法，从而在一个强大的网络拓扑结构，增加抵御外界攻击的弹性。通过仿真结果，我们表明，所提出的鲁棒性增强的网络表现良好，有针对性的攻击相比，传统的优化网络。c2018 韩 国 通 信 与 信 息 科 学 研 究 所 （ KICS ） 。 Elsevier B. V. 的 出 版 服 务 。 这 是 CC BY-NC-ND 许 可 证 下 的 开 放 获 取 文 章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。关键词：复杂网络;网络鲁棒性;无悔学习1. 介绍已被应用于解决诸如脑网络、社交网络和无线网络等领域中的问题的流行且重要的复杂网络之一是无标度网络（SFN）[1SFN的主要优点之一是与其他复杂网络相比，它可以承受随机攻击[4，5]。然而，SFN近来已经有许多增加的研究努力，以基于各种优化技术来优化SFN拓扑以解决这一重要问题。然而，已经提出的许多技术本质上是启发式的，2. 问题公式化2.1. 鲁棒性度量在分析随机攻击和故意攻击模型下网络鲁棒性的各种度量中，我们采用了Schenider等人提出的R度量[11 ]第10段。在随机攻击模型中，网络中的节点是随机选择的，并与所有连接的链接一起删除。对于故意攻击模型，不断选择和删除链接数或节点度最高的最重要节点。R度量表示为1复杂性在本文中，我们提出了一种新的方法，R=1∑s（q），（1）基于No-Regret学习算法设计了一个优化的鲁棒网络。No-Regret算法是一个强大的工具，它基于使用过去模式的策略集来调整一组动作（8No-Regret算法被广泛使用的原因是它保证了被制定为策略博弈的问题中的相关均衡解。电子邮件地址：isohn@dongguk.edu。同行评审由韩国通信和信息科学研究所（KICS）负责https://doi.org/10.1016/j.icte.2018.10.001Nq=1/N其中N是网络中节点的总数，s（q）是最大集群的大小，q是1/N。. . N/N是已删除节点的分数。为了评估网络的鲁棒性，R度量将最大集群中的节点数量与每移除q个节点的分数相加，并通过将总和除以N（网络中的初始节点数量）来归一化结果。鲁棒性值R可以达到的最大值为0.5。原因是2405-9595/c2018韩国通信和信息科学研究所（KICS）。出版社：Elsevier B.V.这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。2N======-=1001 00101 0⟨⟩∼−164I. Sohn / ICT Express 5（2019）163最好的鲁棒网络是格型网络，其中所有节点都连接到其他节点，并且格型网络的鲁棒性度量计算如下所示：R=（（N−1）/N+（N− 2）/N+· ··+（N-N）/N）/ N，=（（N−1）+（N− 2）+···+（N−N））/ N2，=（N（N+1）/2）/N2= 0。五加一。5为大N2.2. 基于度的网络优化为了表示网络拓扑，常用的方法是使用包含0和1的邻接矩阵，其中第i行和第j列中的1表示节点对（i，j）之间存在链路。因此，人们可以很容易地提出通过搜索具有相应邻接矩阵的所有可能的网络拓扑来找到最优鲁棒网络，并选择具有最大R的网络。然而，这是一个不可能完成的任务，需要一个复杂度为2N2的搜索过程.例如，要找到一个最佳的鲁棒网络，N五 、需要创建33，554，432个邻接矩阵，并且需要计算相应的R值因此，在本文中，我们使用节点度信息，而不是节点和链路组合来表示[12]中提出的网络拓扑。与搜索2N2个邻接矩阵以找到具有最大R的邻接矩阵相比，我们只需要搜索D N个度信息向量（DIV）。例如，如果节点度D 3和节点数N5、D N35使用243个DIV来找到具有最大R的网络。然而，为了计算R，我们需要获得实际的节点和链路交互信息，通常通过邻接矩阵表示。所以问题是，具有相同DIV的不同网络是否具有相似的鲁棒性性能。答案是肯定的。例如，假设我们有多个网络，N为5，DIV[3 3 2 4 2]，其中节点1，2，3，4，5的度分别为3，3，2，4，2。有2种可能的网络拓扑，DIV=[3 3 2 42]。DIV=[3 3 2 4 2]的邻接矩阵如下所示，所有网络的R=0。320.图1.一、N = 5时的稳健性性能。在所有可能的DIV中的搜索对于大型网络来说仍然是相当低效的。3. 该方法3.1. 无悔学习无悔学习算法是解决多智能体决策问题或多人重复博弈问题的有力工具。在一个多人重复博弈问题中，一个参与者面临一组行动或策略，必须选择一个行动来最大化他或她的收益。由于选择一个行动的结果或收益是由其他参与者的行动共同决定的。参与者反复进行游戏，通过观察过去的收益模式，参与者调整策略。在无遗憾学习算法中，玩家评估没有选择不同策略集的平均遗憾，然后调整策略选择过程以实现零遗憾。为了找到一个最佳的网络拓扑结构，最大的鲁棒性，我们制定了节点度选择问题作为一个⎡⎢0 1 1 1 0⎤⎥⎢⎣⎥⎦⎡⎢0 1 0 1 1⎤⎥⎢⎣⎥⎦战略游戏如下：Γ=K，{Sk}k∈K，{uk}k∈K，（2）其中策略博弈的组成部分如下所示：因此，我们可以得出结论，使用DIV来表示找到一个最佳的网络确实是一个有效的方法。我们现在有了一种基于DIV的低复杂度优化方法，可以找到比搜索所有可能的邻接矩阵组合更有效的鲁棒网络。 图 1、鲁棒性能R对所有可能的1. 参与者集合：K对应于网络中的N个2. 策略集：Sk是参与人k可以选择的策略集，对应于0N1可能的度或到其他节点3. 效用函数：uk是效用函数，定义为对于N=5示出了度信息组合。为u（s，s）=R（s， s）−αL（s， s），（3）N=5的网络，则有DN=45= 1664个可能的网络Kk−kk−kk−kDIV，1664个DIV中有1024个有效网络拓扑。如图所示，R值在0.1和0.4之间变化。正如人们所预期的那样，具有大R的网络具有大量的链路或具有最大度N−1的节点，DIV=[44 4 4 4]。暴力破解法其中s-k是其他参与者的联合策略，R是（1）中定义的鲁棒性度量，L是网络中的链路总数，α是平衡鲁棒性增益和链路成本的权重因子。1001 11011 01110 11110 10101 01001 0==I. Sohn / ICT Express 5（2019）163-166165图三. SFN、HCN和建议网络的网络拓扑。图二. 无悔学习算法。3.2. 该算法在我们提出的算法中，无遗憾学习算法被应用到搜索最佳度信息向量（DIV），这将代表一个攻击容忍的网络拓扑结构。使用无悔学习方法，我们取代了穷举搜索过程，以找到第2节中描述的最佳DIV。该算法从一个随机网络开始，初始网络中的度信息被用作初始DIV。在DIV中分配的度值被视为可能的策略，这些策略将被迭代调整以最大化效用。效用被定义为我们想要最大化的R度量和我们想要最小化的网络中的链路总数的负数之和，如（3）所述。后悔被定义为没有选择不同的策略或程度值的效用值的差异。因此，在学习算法中，基于其他节点的度信息和玩家节点的过去和当前度信息，通过从基于未选择的策略的效用中减去基于过去决策的效用来计算平均后悔。选择后悔值最大的策略作为参与人k在迭代t中的最优策略。详细的无悔学习算法如图所示。 二、4. 仿真结果为了进行比较分析，将基于No-Regret学习方法的网络与无标度网络(SFN)登山网络（Hill ClimbingHCN是一种基于单频网的优化网络，其中应用爬山算法迭代地交换单频网中的单对链路以搜索具有最大R度量的网络拓扑。虽然，爬山算法是能够找到一个最佳的鲁棒网络拓扑结构，有针对性的攻击，它需要大量的迭代复杂的计算。在所提出的方法中，在（3）中给出的效用函数中的权重因子被设置为α=（10N）−1，其中N是网络中的节点总数。此外，对于N20、30、40和50，策略M的数量分别被设置为6、10、12图3示出了SFN、HCN和所提出的网络的网络拓扑。如图所示，SFN具有少量的集线器，在众多的小尺寸节点之间具有大量的链路。至于HCN，可以注意到“洋葱连接”结构，这已经在各种文献中报道。所提出的网络显示了与其他两个网络相比，这是因为SFN和HCN的链路数量等于95，但是对于建议的网络，等于195。大量链接的原因是，无遗憾学习算法收敛到具有大R值的网络拓扑，但也有一个目标，即在给定固定数量的节点的情况下减少链接的总数。然而，建议的网络表现出最好的鲁棒性性能与R 0。3328与其他网络相比。在图4中，示出了针对SFN、HCN和使用具有故意攻击模型的R度量的建议网络的网络鲁棒性性能。为了公平的比较，随机打孔后，无遗憾学习算法已被应用到建议的网络，以匹配在其他传统网络的链路总数。数值结果在10次独立试验中取平均值，其中链接数在（32，36），（50，57），（70，74）和（93，97）之间，对于所有网络，N=20、30、40和50作为166I. Sohn / ICT Express 5（2019）163致谢本 研究 得 到了 教 育部 资助 的 韩国 国 家研 究 基金 会（ NRFK ） 基 础 科 学 研 究 计 划 的 支 持（2018R1D1A1B07041981）。利益冲突作者声明，本文中不存在利益冲突引用[1] X.F.的缩写Wang，G.陈伟，复杂网络：小世界、无标度和超越，IEEE电路系统杂志，3（1）（2003）6-20，第1季度。[2] I. Sohn，物联网系统的小世界和无标度网络模型，Mob。信息系统（2017年）。见图4。 SFN、HCN、建议网络的R与N从图中可以看出，对于目标攻击环境中的所有数量的链路，与SFN相比，优化的网络HCN和所提出的网络在鲁棒性方面显示出巨大的改进。此外，该网络表现出更好的性能相比，HCN具有较低的复杂性，特别是在少量的节点。5. 结论在本文中，找到一个最佳的鲁棒网络拓扑结构，以防止恶意攻击的问题表示为一个战略博弈，目标是找到最大化R度量的度分布。我们提出了利用网络中节点的度信息和网络中的总链接数，使用无悔学习来最大化效用函数。模拟结果表明，与文献中报道的常规优化方法相比，所提出的方法实现了高鲁棒性性能。[3] I. Sohn，建模和实施小世界网络，在：信息和通信技术融合国际会议，ICTC，2016年，第11页。414-416[4] 答 ： L. 巴 拉 巴 西 河 Albert ， Emergence of Scaling in RandomNetworks，Science 286（1999）509-512.[5] R. 阿 尔 伯 特 ， A.- L. Barabási ， Statistical mechanics of complexnetworks，Rev. Modern Phys. 74（2002）47-97.[6] 答：L. Barabási，Scale-free networks：a decade and beyond，Science325（2009）412-413.[7] Y.H.李岛，智-地Sohn，Reconstructing Damaged Complex NetworksBased onNeural Networks，Symmetry（2017）。[8] H.P. Young ， Strategic Learning and its Limits ， Oxford UniversityPress，Oxford，UK，2010.[9] I. Sohn，使用相关均衡的移动用户接入点选择游戏，PLoS One（2015）。[10] I.索恩，H。Liu，N. Ansari，Optimizing cellular networks enabledwithrenewal energy via strategic learning，PLoS One（2015）。[11] C.M. Schneider ， A.A. Moreira ， J.S. Andrade ， S. Havlin ， H.J.Herrmann，缓解对网络的恶意攻击，Proc. Natl. Acad. Sci. （2011）3838-3841。[12] I. Sohn，建模和实施小世界网络，在：信息和通信技术融合国际会议，ICTC，2017年，pp. 789-791。