论文部分内容阅读
关键节点检测作为分析网络脆弱性的重要手段,吸引了越来越多研究人员的关注。传统的关键节点检测研究侧重于网络的静态属性(网络拓扑结构),忽略了节点与节点间的相互依赖关系(级联效应),然而在现实世界许多复杂网络中,节点与节点之间存在明显的级联关系,所以本文展开基于级联模型的复杂网络关键节点检测问题研究。然而,目前大部分的级联关键节点检测算法注重于设计出有效的攻击策略(攻击效果),忽视了攻击的代价,而攻击效果与攻击代价之间存在显然的冲突性,所以本文将基于级联模型的关键节点检测问题转化为一个多目标优化问题,同时考虑攻击代价与攻击效果。由于级联关键节点检测分为面向同步攻击的方法和面向时序攻击的方法,因此本文针对同步攻击提出了基于多目标优化的复杂网络级联关键节点检测算法,针对于时序攻击提出了面向时序攻击的多目标级联关键节点检测算法。本文的主要研究工作如下:(1)本文从多目标的角度出发解决级联关键节点检测问题,并提出了基于多目标优化的复杂网络级联关键节点检测算法(MO-BCVND)。在级联关键节点检测领域中,目前大部分的研究工作注重于设计出有效的攻击策略,使关键节点的失效对网络的破坏程度最大,而忽视了攻击的代价。但在许多实际应用中,决策者通常想要的是花费最小的代价达到最好的攻击效果,基于此,本文将级联关键节点检测问题转化为一个多目标优化问题(BCVND),同时考虑攻击的代价与攻击的效果(破坏性)。为了解决这个多目标优化问题,提出了基于多目标优化的复杂网络级联关键节点检测算法,简称为MOBCVND。此外,在MO-BCVND中,为了增加种群的多样性,本文提出了基于代价归减的初始化策略;为了提高种群的收敛速度,本文提出了自适应局部搜索策略。最后在12个真实复杂网络数据集上的实验结果验证了MO-BCVND算法及所提策略的有效性,同时MO-BCVND一次运行可以得到一组不同层次的解,能够为网络的脆弱性分析提供全局的视角。(2)本文提出了面向时序攻击的多目标级联关键节点检测算法(MO-BCVNDSeq)。从第一个研究工作中可以发现,从多目标优化的角度出发来解决级联关键节点检测问题是一种行之有效的方式。但在第一个研究工作中主要关注的是同步攻击场景下的级联关键节点检测,而忽略了攻击的时序性,基于此,本文提出了一种面向时序攻击的多目标级联关键节点检测算法(MO-BCVNDSeq)用以解决时序攻击下的级联关键节点检测问题。此外,为了有效考虑时序特征,本文设计了针对于时序情况下的个体编码及对应的交叉、变异操作;加快种群收敛,本文提出了基于时序矩阵的局部搜索策略;为了去除个体编码中的冗余节点,本文提出了个体修正策略。最后,在12个真实数据集上的实验结果验证了MO-BCVNDSeq算法及所提策略的有效性。