1.本发明涉及属于计算机应用技术领域，特别涉及一种用于解决网络上鲁棒信息传播问题的方法及系统。
背景技术：2.随着近些年互联网的普及与高速发展，诸如微信、微博等社交网络的进入了人们的视野。这些平台极大的丰富了人类的社交，甚至已经成为了人类社会不可或缺的部分。随着用户规模的快速增长，社交平台成为人们发表观点、交流的重要渠道；与此同时，网络传播信息高效和用户数量庞大的特点使得线上营销成为了一种重要的商业营销方式。由于资金等成本限制，商家不可能针对每一个用户进行推广，往往会针对小部分具有较大影响力的“种子”用户进行产品推销，以此来达到快速提升产品影响力的目的，这种手段被称为“病毒营销”或“口碑营销”。因此，如何选择最具有影响力的“种子”用户成为了问题的关键，这个过程可以被建模为影响力最大化问题。
3.一般来说，网络系统上的影响力传播过程有以下几种常见的信息传播模型：独立级联模型(lc模型)、权重级联模型(wc模型)和线性阈值模型(lt模型)等。在这些研究的基础上，网络上的影响力最大化问题可被视为一个优化问题，即在一定性能评估因子的指导下，尝试从网络全部成员中寻找最优的种子节点组合。诸如爬山法、贪心算法等启发式算法可解决该问题，但他们都存在效率较低的缺点；同时，基于度、pagerank、betweenness等结构特性的评估方法也可以为解决影响力最大化问题提供参考，但这些方法可能存在影响力重叠的缺点。另外，离散粒子群算法、memetic算法等基于种群的搜索方法对解决此问题也展现了较好的效果，这些优化方法根据网络结构的特点和网络节点的信息，为解决影响力最大化问题提供了可以参考的解决方案。
4.此外，网络时常会面临复杂的应用环境，有时会因为自身或外界因素导致节点和链接的功能出现故障和波动。实际上，一个正常运转的网络应具有容忍故障和波动的能力，即鲁棒性。网络的鲁棒性对于保障社交网、万维网、交通网等网络系统的安全运行具有重要意义。以往的研究证明，网络结构往往与网络的性能紧密相关，对于一个社交网络来说，其网络结构的变化也会影响到该网络中成员的互动行为，而互动行为的改变很可能进一步对于影响力传播过程造成影响。因此，如何评估和优化网络系统的鲁棒性也是近几年来复杂网络领域研究的热点之一。
5.目前针对影响力最大化问题的工作存在一些不足。一方面，如前文所述，在实际应用中网络结构常会受到不可预知的攻击，无论是针对网络链路还是网络节点的攻击都有可能对网络结构造成严重的破坏。当前的工作或者没有考虑到网络结构改变的场景，或者仅考虑了网络在受链路攻击下的场景而没有考虑到网络受节点攻击的场景，存在着一定缺陷；另一方面，以往的遗传算法并没有很好地应用搜索过程中获得的种群信息，且种群多样性较差。在某些极端情况下，有可能会出现收敛效率慢、容易陷入局部最优解等问题。在遗传算法中，种群的多样性对计算结果和计算效率有重要的影响；要实现高效寻优，种群在解
空间应当尽量分散。另外，目前一些前沿工作初步探讨了如何选择同时满足鲁棒性和影响力最大化的种子节点，但是这些工作应用场景只限制在节点影响力传播概率、传播模型等系统参数不确定的情形，存在一定的局限性。因此，如何在网络受到节点攻击的条件下对于种子节点的影响力性能进行有效评估，以及如何设计一套行之有效的种子优化选择方案仍旧是目前研究没有解决的问题。
技术实现要素：6.本发明的目的是克服现有技术中的不足，提供一种用于解决网络上鲁棒信息传播问题的方法及系统。
7.为了达到上述目的，本发明是通过以下技术方案实现的：
8.一种用于解决网络上鲁棒信息传播问题的方法，包括如下步骤：
9.步骤s1、定义网络结构在节点攻击下种子节点的鲁棒影响力性能评估指标所述n表示当前网络的节点数，所述表示移除q个节点后种子节点集s的影响力估计值；
10.步骤s2、在基于影响力性能评价指标的指导下设计基于“多样性关注”原则的方法来的解决鲁棒影响力最大化问题的方法。
11.作为优选，所述基于“多样性关注”原则的方法包括如下步骤：(2a)、执行依托于优先策略初始化算子，产生一系列种子来初始化种群；
12.(2b)、执行交叉策略结合的交叉算子，然后交换基因信息和扩大种群数量，从而生成与原种群个体数目相同的临时种群；
13.(2c)、对原种群和临时种群执行变异算子，从而增加种群多样性，摆脱局部最优解；
14.(2d)、对原种群和临时种群执行局部搜索算子；
15.(2e)、执行选择算子，并根据适应度函数选取全局最佳的个体(节点集)；
16.(2f)、重复执行上述步骤，直至满足设定的终止条件，最后输出进化过程中出现过的最优解，即适应度最大的种子节点集合s及其适应度。
17.作为优选，优先策略包括节点度优先策略、pagerank优先策略、clustering优先策略。
18.交叉策略包括均匀交叉策略、二点交叉策略、单点交叉策略。
19.系统包括：
20.定义模块，用于定义种子节点集合s在遭受节点攻击下的影响力性能评价指标；
21.初始化算子模块，用于产生一系列种子来初始化种群；
22.临时种群产生模块，用于生成与原种群个体数目相同的临时种群；
23.变异算子模块，用于增加种群多样性，摆脱局部最优解；
24.搜索模块，用于对原种群和临时种群执行局部搜索算子；
25.执行算子模块，用于采用精英策略保存或尝试更新每次迭代获得最优解；
26.输出模块，用于输出进化过程中出现过的最优解，最优解就是适应度最大的种子节点集合s及其适应度。
27.本发明的有益效果如下：本发明在对于网络结构受到节点攻击的情况下，设计了一个针对网络节点攻击下衡量种子节点的鲁棒影响力性能指标，该评估指标在网络受到节点攻击的条件下，能够对于种子节点的影响力性能进行有效评估，具有计算代价小，结果在不同的网络规模下具有可比较性，能够为种子节点集的选取提供较为可靠的评价标准；
28.在针对网络节点攻击下衡量种子节点的鲁棒影响力性能指标的引导下设计了一个基于“多样性关注”原则的方法来解决鲁棒影响力最大化问题，利用该方法得到的种子节点集合可以在网络受损过程中取得保持较好的影响力传播效果。
附图说明
29.图1为本发明的流程图。
具体实施方式
30.下面结合说明书附图对本发明的技术方案作进一步说明：
31.如图1所示，
32.(1)、网络结构在节点攻击下种子节点的鲁棒影响力性能评估指标：
33.(1a)种子节点向外传播影响力的过程中，每次遭受攻击后，对种子节点集合s的影响力进行重新评估；
34.(1b)遵循公式中的加和、归一化操作来求取种子节点集合s在网络节点攻击下的综合影响力性能，这里s(q)为去掉q个节点后的网络最大连通簇，n为网络中的节点总数，1/n是归一化因子；
35.(1c)根据如上机制，将网络结构在节点攻击下种子节点的鲁棒影响力性能评估指标定义如下：
[0036][0037]
这里，n表示当前网络的节点数，表示移除q个节点后种子节点集s的影响力估计值。
[0038]
(2)、基于“多样性关注”原则的解决鲁棒影响力最大化问题的方法包括如下步骤：
[0039]
(2a)遵循“个体多样性”原则，结合节点度优先策略、pagerank优先策略、clustering优先策略执行初始化算子，产生可能的影响力最大的个体(节点集)种群。具体来说，分别对种群前1/3、中间1/3、剩余1/3的个体的初始化执行节点度优先策略、pagerank优先策略、clustering优先策略，即根据节点度、pagerank、clustering作为评判节点重要性的指标信息，使用轮盘赌的方法选出给定数量的节点作为个体的基因；
[0040]
(2b)遵循“基因多样性”原则，结合均匀交叉、二点交叉、单点交叉三种策略执行交叉算子然后交换基因信息和扩大种群数量，从而生成与原种群个体数目相同的临时种群，产生了规模为popsize的个体。需要注意的是，如果交叉后一个个体内出现重复节点，需要对个体执行修正操作。修正操作如下：随机选择初始网络中的一个节点替换个体中的重复节点，直到个体内无重复节点为止；
[0041]
(2c)遵循“概率多样性”原则，根据个体的适应度动态调整变异概率，对原种群和临时种群执行变异算子。具体如下，计算种群中所有个体的适应度值(即影响力性能指标rs)，并计算出所有个体的适应度总和。然后，对于种群中的每个个体，变异算子以pm*β(pm是变异概率，β＝1-该个体的适应度值/种群中所有个体的适应度值)的概率执行，将个体中随机一位基因节点替换为网络中的其他节点。注意，变异过程中同样遵循一个个体内无重复节点原则，如果出现重复节点，则执行上文所提到修正操作；
[0042]
(2d)遵循“搜索空间多样性原则”，将搜索范围由局部扩展至全局，即对原种群和临时种群部搜索变异算子，从而增加种群多样性，摆脱局部最优解。具体而言，将局部搜索算子设计为三个部分，根据迭代次数动态采用不同的搜索策略：第一部分的搜索空间是当前种子节点2-hop邻域，即考虑将节点随机替换为其邻居或其邻居的邻居；第二部分搜索空间是网络中适应度值最大的几个节点(占网络规模的10％)的集合，考虑将节点替换为其一；第三部分的搜索空间是随机从网络中选取一定数量的节点(占网络规模的10％)的集合,考虑将节点替换为其一。以上三种搜索策略，若产生替换后的种子集合具有更好的适应度，则接受替换操作；
[0043]
(2e)执行选择算子，并根据适应度函数选取全局最佳的个体(节点集)。具体而言，利用轮盘赌方法或算法将较优个体选择进入子代种群。这里一些性能较差的个体同样有被选择的机会，可以在一定程度上提升种群的多样性。另外，子代种群的第一个个体保存的是当前搜索过程找到的全局最优解，用来防止种群适应度退化；
[0044]
(2f)重复执行上述步骤，直至满足设定的终止条件。最后输出进化过程中出现过的最优解(即适应度最大的种子节点集合s及其适应度)。
[0045]
本发明在对于网络结构受到节点攻击的情况下，设计了一个针对网络节点攻击下衡量种子节点的鲁棒影响力性能指标，该评估指标在网络受到节点攻击的条件下，能够对于种子节点的影响力性能进行有效评估，具有计算代价小，结果在不同的网络规模下具有可比较性，能够为种子节点集的选取提供较为可靠的评价标准。
[0046]
在针对网络节点攻击下衡量种子节点的鲁棒影响力性能指标的指导下设计了一个基于“多样性关注”原则的解决鲁棒影响力最大化问题的方法，利用该方法得到的种子节点集合可以在网络受损过程中取得保持较好的影响力传播效果。
[0047]
需要注意的是，以上列举的仅是本发明的一种具体实施例。显然，本发明不限于以上实施例，还可以有许多变形，总之，本领域的普通技术人员能从本发明公开的内容直接导出或联想到的所有变形，均应认为是本发明的保护范围。
技术特征：1.一种用于解决网络上鲁棒信息传播问题的方法，其特征在于，包括如下步骤：步骤s1、定义网络结构在节点攻击下种子节点的鲁棒影响力性能评估指标：所述n表示当前网络的节点数，所述表示移除q个节点后种子节点集s的影响力估计值；步骤s2、在基于影响力性能评价指标的指导下设计基于“多样性关注”原则的方法来解决鲁棒影响力最大化问题。2.根据权利要求1所述用于解决网络上鲁棒信息传播问题的方法，其特征在于，所述基于“多样性关注”原则的方法包括如下步骤：(2a)、执行依托于优先策略的初始化算子，产生一系列种子来初始化种群；(2b)、执行交叉策略结合的交叉算子，然后交换基因信息和扩大种群数量，从而生成与原种群个体数目相同的临时种群；(2c)、对原种群和临时种群执行变异算子，从而增加种群多样性，摆脱局部最优解；(2d)、对原种群和临时种群执行局部搜索算子；(2e)、执行选择算子，并根据适应度函数选取全局最佳的个体(节点集)；(2f)、重复执行上述步骤，直至满足设定的终止条件，最后输出进化过程中出现过的最优解。3.根据权利要求2所述用于解决网络上鲁棒信息传播问题的方法，其特征在于，所述优先策略包括节点度优先策略、pagerank优先策略、clustering优先策略。4.根据权利要求2所述用于解决网络上鲁棒信息传播问题的方法，其特征在于，所述交叉策略包括均匀交叉策略、二点交叉策略、单点交叉策略。5.基于权利要求1-4任意一项用于解决网络上鲁棒信息传播问题的方法的系统，其特征在于，所述系统包括：定义模块，用于定义种子节点集合s在遭受节点攻击下的影响力性能评价指标；初始化算子模块，用于产生一系列种子来初始化种群；临时种群产生模块，用于生成与原种群个体数目相同的临时种群；变异算子模块，用于增加种群多样性，摆脱局部最优解；搜索模块，用于对原种群和临时种群执行局部搜索算子；执行算子模块，用于采用精英策略保存或尝试更新每次迭代获得最优解；输出模块，用于输出进化过程中出现过的最优解。
技术总结本发明公开了一种用于解决网络上鲁棒信息传播问题的方法及系统。一种用于解决网络上鲁棒信息传播问题的方法，包括如下步骤：步骤S1、定义网络结构在节点攻击下种子节点的鲁棒影响力性能评估指标；步骤S2、在基于影响力性能评价指标的指导下设计基于“多样性关注”原则的方法来解决鲁棒影响力最大化问题。本发明具有计算代价小、数值在不同的网络规模下具有可比较性等优点，能够为种子节点集的选取提供较为可靠的指导；得到的种子节点集合可以在网络受损过程中保持较好的影响力传播效果。络受损过程中保持较好的影响力传播效果。络受损过程中保持较好的影响力传播效果。
技术研发人员：王帅 张佳钟 陈明昊
受保护的技术使用者：中山大学
技术研发日：2022.07.06
技术公布日：2022/11/1
