基于飞蛾扑火算法的关键节点挖掘方法

许钦钧 徐龙琴 刘双印 赵学华

摘 要：关键节点挖掘在理解和控制复杂网络系统方面具有重要作用和巨大潜力。提出了一种基于飞蛾扑火优化算法的关键节点挖掘算法，解决关键节点问题。该算法引入了反向学习等策略，以提高解集的质量和加快收敛。同时，设计了快速种群演化和复合高斯进化等方法，以优化解集并增强解空间探索能力，从而克服局部最优陷阱。在多个合成网络和真实网络数据集上进行的对比实验结果表明，提出的算法相较以于其他先进的对比算法具有更高的鲁棒性，并验证了该算法部件的有效性。

关键词：关键节点； 网络连通性； 群智能算法； 飞蛾扑火优化算法

中图分类号：TP393.02   文献标志码：A

文章编号：1001-3695（2023）09-023-2713-07

doi：10.19734/j.issn.1001-3695.2023.02.0032

Enhanced moth-flame optimization algorithm for critical node detection

Xu Qinjun1，2，3， Xu Longqin1，2，3， Liu Shuangyin1，2，3， Zhao Xuehua4

（1.College of Information Science & Technology， Zhongkai University of Agriculture & Engineering， Guangzhou 510225， China; 2. Intelligent Agriculture Engineering Research Center of Guangdong Higher Education Institutes， Guangzhou 510225， China; 3. Guangzhou Key Laboratory of Agricultural Products Quality & Safety Traceability Information Technology， Guangzhou 510225， China; 4. School of Digital Media， Shen-zhen Institute of Information Technology， Shenzhen Guangdong 518172， China）

Abstract：The detection of critical nodes plays an important role with significant potential in understanding and controlling complex network systems. This paper proposed critical node mining algorithm based on the moth-flame optimization to address the critical node problem. It introduced strategies such as opposition-based learning to improve the quality of the solution set and accelerate convergence. Additionally， it designed fast population evolution and hybrid Gaussian evolution methods to optimize the solution set and enhance the exploration capability of the solution space， overcoming local optima traps. Comparative experimental results conducted on multiple synthetic and real network datasets demonstrate that the proposed algorithm exhibits higher robustness compared to other advanced comparative algorithms. Furthermore， the effectiveness of the algorithm components is validated.

Key words：critical nodes; network connectivity; swarm intelligence algorithm; moth-flame optimization

近年來，由于关键节点挖掘在计算生物学［1］、网络脆弱性评估［2］、社交网络分析［3］、传染病传播控制［4］、精准营销等领域中的广泛应用潜力，该问题备受关注。例如，在流行病传播网络中，发现关键节点并采取适当措施能够大大减少疾病传播，这使得关键节点挖掘研究和调节复杂网络的功能具有重要意义。然而，经典关键节点挖掘问题是NP-难问题［5］，这意味着其精确解法需要承担呈指数增长的计算复杂度，难以在大型网络中被接受。为了解决这个问题，本文提出了一种基于飞蛾扑火优化算法的关键节点挖掘算法（moth flame optimization for critical node problem，MFOCNP）。该算法包含一个快速种群进化（fast population evolution，FPE）机制，结合了相反学习（opposition-based learning，OBL）策略以挖掘具有高质量和多样性的初始种群；一种被称为飞蛾扑火优化算法（MFO）的群智能优化算法，通过探索新解决方案并克服局部最优陷阱实现优化；以及一种复合高斯进化（HGE）机制，用于加强探索能力和加速收敛。为了验证本文方法的有效性，在合成网络和真实网络上进行了实验，并与其他一流算法进行了比较。实验结果表明，该算法的性能优于其他算法。

1 相关工作

1.1 关键节点问题进展

经典关键节点挖掘问题（critical node detection problem，CNDP）的定义是：对于一个有n=|V|个点、m= |E|条边的网络N=（V，E）和一个正整数K，CNDP问题求一个规模不大于K的子集SV，且删除它能最大限度地降低剩余网络N［V＼S］的成对连通性（连接节点对的总和），求得的点集S就是网络关键节点的集合。

由于该问题的理论意义和实用潜力，文献中提出大量算法，它们主要分为精确方法和启发式方法。

精确方法主要利用整数线性规划（integer linear programming，ILP）将特定网络中的关键节点挖掘问题转换为可解的目标函数方程式。文献［5］提出了一个简化的函数方程和算法（HDCN）。文献［6］则提出了一种基于Benders分解的方法以精确识别随机网络上的关键节点。文献［7］使用分支切割算法解决一般网络上的关键节点挖掘，然而，由于该问题的NP难特性［5］，在一般网络和大型网络中，精确算法的计算成本较高。所以，启发式算法，特别是贪婪算法是一个性价比高且必要的替代选择，其能在有限时间内找出高质量的近似解，如BCB［8］、LRBG［9］、KSBG［10］等算法。以下介绍两种常见的贪婪算法程序。

第一种贪婪算法程序［5］是对网络中每个节点进行计算，找出一个删除它后降低网络连通性最多的点，并将其从网络移入点集S；重复上述步骤直到点集大小达到预设要求。第二种程序是逐一移除有边的点并将其加入到点集中，直到网络中没有边存在。随后，贪心地将点集中的点逐一放回网络，使得每次放回的节点对网络增加的连通节点数最少，直到点集大小达到预设要求。这两种贪婪算法比较快速、高效，能够找出近似最优解，但结果缺乏准确性。为了改善贪婪算法的缺陷，研究者提出了很多其他启发式和元启发式算法。NSGACNP［11］和复合启发式算法（Greedy3D/Greedy4D）［12］使用贪婪算法作为基础，通过交换部分节点来改进解的质量。朱华等人［13］通过增强贪婪算法，设计一种新的级联概率计算模型挖掘关键节点集。周丽娜等人［14］利用超图中的邻接结构熵识别超网络中的关键节点。孙百兵等人［15］根据网络社区结构提出一种节点重要性评估函数。刘子彤等人［16］提出一种基于加权集体影响力模型，用于识别加权通信网络中的关键节点。此外，元启发式算法也提供了一些新颖的思路，如Ventresca［17］提出了退火算法（simulated annealing，SA）和基于增量学习的群体算法（incremental learning based on population，PBIL），并验证了其有效性。

1.2 飞蛾扑火优化算法简介

飞蛾扑火优化算法（moth-flame optimization algorithm，MFO）是一种基于横向定位和螺线运动的群智能优化算法，它最初的灵感来源于飞蛾的行为模式。飞蛾以月亮为参照点，其飞行的方向与它跟月亮的连线保持固定角度，这种导航方法可以使飛蛾在夜间保持直线飞行。然而，人造光源会误导飞蛾绕着它飞行，甚至飞进光源，这就是“飞蛾扑火”现象（图1）。Mirjalili［18］对飞蛾的行为模式进行了数学模拟，并提出了一种基于横向定位和螺线运动的优化算法，即飞蛾扑火优化算法。该算法结合了飞蛾的行为模式和螺旋运动，具有较好的全局搜索能力和收敛速度。在近年来的群智能优化领域，它被认为是一种较为流行的优化算法。飞蛾的螺线运动如图1所示。

2.3 计算复杂度

为证明MFOCNP算法的效率，对算法复杂度进行分析。MFOCNP算法主要有三个步骤：a）种群初始化和快速演化；b）飞蛾螺线运动；c）复合高斯进化方法。第一阶段，相反学习和快速种群演化方法的复杂度分别不超过O（n×|E|）和O（k×|E|），其中n为蛾的数量，|E|为网络边的数量，k为关键节点的数量。在第二阶段，火焰的更新和分配的极限为O（tm×n×（|E|+n）），其中tm是迭代的最大次数。螺旋运动的计算复杂度为O（tm×n×k）。最后，复合高斯进化操作的复杂度为O（tm×n×|E|×k），因此，MFOCNP算法的总计算复杂度为O（tm×n×（|E|×k+n）），跟传统算法相比低很多。

3 实验设计

为了评估MFOCNP算法的性能，在多个数据集上进行了实验。使用了多种对比算法，这些对比算法在各自的领域内具有较高的性能表现，能够提供一个有意义的比较标准。在实验中，分别使用了人工构造和真实的网络数据集。其中，人工数据集针对不同的网络拓扑特征进行构建，并加入了一定的噪声以模拟现实场景；真实数据集则来自于网络运营商和互联网公司的监测数据，包括传输数据的源地址、目的地址、时间戳等信息。为了更好地评估算法的效率，还对计算复杂度进行了分析。采用了事前分析法，通过对算法步骤的时间复杂度进行计算，得出了在不同数据规模下的算法复杂度及其增长趋势。这一分析为评估算法性能提供了理论支持。

实验运行在一台装有AMD Ryzen 5 4600H处理器，3.00 GHz clock和16 GB RAM的电脑上，系统运行Windows，代码使用Python编写（源代码已发布在https：//github.com/Axuqj/Enhanced-Moth-Flame-Optimization-Algorithm-for-Critical-Node-Detection.git上）。

3.1 对比算法

为了克服CNP这个NP-难问题，许多启发式算法被提出。在验证MFOCNP算法的性能时，使用了一些常见的对比算法，并对它们的性能进行了比较。使用了简洁高效的关键节点挖掘算法（HDCN）［7］，利用贪婪策略初始化极大独立点集（MIS），并通过删除节点来达到目标点集大小。

基于介数中心性的贪婪算法（BCB）［8］利用全局中心性来优化解集。复合启发式算法（Greedy3D）及其改进版本（Greedy4D）［12］结合贪心算法和迭代局部搜索来解决局部最优解问题，而基于K-Shell的贪心算法（KSBG）［10］则使用快速有效的节点中心性模型进行节点重要性评估，以提高算法性能。

GCNP算法［24］利用局部节点中心性和贪婪策略快速有效地找出近似最优解，而基于LocalRank的贪婪算法（LRBG）［9］使用广泛应用的节点度量模型加速搜索最优解过程。

此外，还利用了一种基于非支配的多目标优化遗传算法NSGA-Ⅱ，该算法具有高效的排序算法和机制，无须事先输入参数［15］。NSGA-Ⅱ算法在关键节点挖掘问题中被应用（即NSGACNP），将该问题划分为剩余网络中连通图的数量和连通图之间的基数方差两个独立的目标函数。

3.2 数据集

为了更好地验证算法的效果和鲁棒性，采用了各种复杂网络生成模型和真实网络数据集进行实验。

1）合成网络的生成模型

为评估MFOCNP算法的效果，选择了五种经典的复杂网络生成模型来构建人工复杂网络数据集，并使用这些数据集进行实验。下面介绍这些网络生成模型：

a）Erdos-Renyi（ER）模型［25］。它是一种重要的网络生成模型，然而其合成的网络缺乏现实中常见的社区结构。参考文献后设定了参数［25］，并分别合成三组网络（每组包含10个相似网络，保存平均值），如表1所示。

b）Barabasi-Albert （BA）模型［26］。其生成的网络又被称为无标度网络，其中节点的度遵循幂律分布（指数分布）。参考文献后设定参数［26］，生成三组网络（每组包含10个相似网络，保存平均值），如表2所示。

c）Watts-Strogatz（WS）小世界模型［27］。其生成的网络中多数节点几步内就能到达其他任一节点，所以被称为小世界网络。参考文献后设定参数［27］，生成三组网络，如表3所示。

2）真实网络数据集

为更好地研究MFOCNP算法的性能，从文献和互联网选择真实复杂网络数据集用于实验，其参数如表4所示。其中Electronic-circuits网络被存储在https：//www.weizmann.ac.il/mcb/UriAlon/download/collection-complex-networks；Yeast网络由https：//www.weizmann.ac.il/mcb/UriAlon/download/collection-complex-networks提供；Polbooks网络由V.Krebs在http：//www.orgnet.com/上编译。

3.3 性能评价指标

采用不同性能指标对算法的性能进行综合验证，其中包括：

a）成对连通性（pairwise connectivity）。该指标是关键节点问题的一个主要指标，它反映了剩余网络的连通程度和关键节点集的质量。具体来说，成对连通性指的是剩余网络N［V＼S］中连通节点对的数量，该指标数值越小，意味着点集质量越高，算法性能越好。

b）随机水平相对差值。将算法处理后剩余网络的成对连通性标记为solution，将随机删除节点后的成对连通性标记为random。采用随机水平相对差值来归一化，便于比较算法性能。随机选择策略是随机移除与算法相同数量的节点。Er值越大，说明算法性能越好。相对差值Er用百分数表示为

Er=100×random-solutionrandom（14）

c）性能概况指标（performance profiles） ［28］。对于算法A，它在实例集合T上进行各项实验并在部分实例中提供了优秀解，性能概况指标pA（n）表示算法A提供了优秀解的实例数占总数的比例。其中，优秀解指在某实例中与最佳解的相对差值（相对差值表示为E=[A（I）-best（I）]/best（I）不大于2n-1的解，当n=0时，优秀解即为某实例中出现的最佳解，pA（0）表示算法A提供最优解的实例数占所有实例的比例。pA（n）表示为

pA（n）=|{I∈T：A（I）≤2nbest（I）}||T|（15）

其中：I∈T是T的一个实例；A（I）是剩余网络的连通节点对；best（I）是在实例I上出现的最佳解（成对连通性越小，解越好）。

4 实验结果与分析

本章实验主要在不同合成网络和真实网络数据集上，比较了本文算法与其他算法的有效性。采用了多种评价指标，包括连通节点对指标、随机水平相对差值和性能概况指标等，以深入分析和比较各算法的性能表现。

4.1 在人工网络数据集上的实验结果与分析

a）连通节点对指标。表5中算法的结果是剩余网络的连通节点对指标，其值越小说明方法性能越好。

在表5中，第1列表示生成网络的类型和大小，k为被移除的节点数，第3～10列表示所有算法的连通节点对指标，每个实验中的最优解用黑体标出。表5数据表示MFOCNP算法生成了最优的一批解。

b）随机水平相对误差。将该算法与随机抽样策略进行比较。随机选择策略中，随机选择与算法相同数量的节点作为解。在图5中，结果以百分比表示，数值越大，性能越好。在BA網络中，结果接近100%，表明MFOCNP算法的性能是随机策略的近两倍。x轴表示相对误差，y轴表示实验名称。从图5可以看出，性能最好的是MFOCNP算法。

c）性能概况指标。图6可以直观地比较各算法的性能表现。图6表示在一系列实验中，算法提供合格解的比率，n越大，需要达到的优秀解的要求越高。曲线位置越靠近左上角，算法性能越好。从图6可以看出，MFOCNP和Greedy3D、Greedy4D在ER、BA和WS网络中性能最好；n=0处，MFOCNP在近100%的实例上提供了最佳解，充分说明了算法的鲁棒性，Greedy3D和Greedy4D则表现出比其他算法更稳定的效果。

4.2 在真實网络数据集上的实验结果与分析

为进一步验证算法的性能，在真实网络上进行了实验。实验中采用不同的K值。

K = z|V| z∈［0.01，0.05，0.1，0.15，0.2，0.25，0.3］

其中：|V|为节点总数；z为关键节点所占比率。共生成8×7=56个关键节点挖掘问题实例。表6表明MFOCNP算法在大多数实验中提供了最佳解。

a）随机水平相对误差。x轴表示相对误差，y轴表示网络类型。例如，lesmis1表示z=0.01的lesmis网络实例。

从图7中可以看出，MFOCNP在大多数情况下比其他算法表现得更好。

b）性能概况指标（performance profiles）。从图8可以看出，MFOCNP算法提供了一系列较好的解，几乎所有的最佳解都来自MFOCNP算法。

4.3 算法组件验证

将MFOCNP算法与MFOCNP0和MFOCNP1两个修改版本进行比较。两个版本分别去掉了两个关键组件。对于MFOCNP0算法，初始种群是随机生成的，且缺少了原算法所提出的FPE优化策略。对于MFOCNP1，其解更新过程相对简单，而MFOCNP的更新过程则通过HGE复合高斯进化策略，得到了很大的改进。

a）连通节点对指标。对比结果如表7所示。表中：z为被移除节点的百分比；fbest为最佳目标值；favg为平均适应度值；tavg为找到最优解的平均时间。

b）随机水平相对误差。如图9所示，在大多数实验中，MFOCNP算法的性能更好。并且MFOCNP的性能略好于MFOCNP1。数据结果说明两种算法组件在MFOCNP算法中都发挥着重要的作用。

5 结束语

针对经典关键节点挖掘问题，提出一种基于飞蛾扑火优化的关键节点挖掘算法（MFOCNP）。该算法结合快速种群进化（FPE）机制来获得高质量的初始种群，采用飞蛾扑火优化算法（MFO）和复合高斯进化算法（HGE）来更新优化种群。为加快收敛速度，FPE机制采用相反学习机制（OBL）和快速种群演化策略来优化初始化。本文算法实现了利用飞蛾扑火优化算法和复合高斯进化算法探索更大的解空间，克服了局部最优陷阱。为了证明MFOCNP算法的性能，在各种合成网络和真实网络上进行了大量实验。计算结果表明，MFOCNP算法在关键节点挖掘问题上优于其他算法，并验证了算法各个组件的性能。如何将机器学习与关键节点挖掘相结合，从而解决动态的大规模的网络问题，是复杂网络中一个重大挑战，后期也将对这一问题进行深入探索。

参考文献：

［1］Tomaino V， Arulselvan A， Veltri P， et al. Studying connectivity pro-perties in human protein-protein interaction network in cancer pathway［M］//Pardalos P， Xanthopoulos P， Zervakis M. Data Mining for Biomarker Discovery. Boston， MA： Springer， 2012： 187-197.

［2］Dinh T N， Thai M T. Precise structural vulnerability assessment via mathematical programming［C］//Proc of Military Communications Conference. Piscataway， NJ： IEEE Press， 2011：1351-1356.

［3］Borgatti S P. Identifying sets of key players in a network［C］//Proc of Managing Technologically Driven Organizations： The Human Side of Innovation and Change. Piscataway， NJ： IEEE Press， 2003： 127-131.

［4］Ventresca M， Aleman D. A derandomized approximation algorithm for the critical node detection problem［J］. Computers and Operations Research， 2014，43： 261-270.

［5］Arulselvan A， Commander C W， Elefteriadou L， et al. Detecting critical nodes in sparse graphs［J］. Computers and Operations Research， 2009，36（7）： 2193-2200.

［6］Hosteins P， Scatamacchia R. The stochastic critical node problem over trees［J］. Networks， 2020，76（3）： 381-401.

［7］Summa M D， Grosso A， Locatelli M. Branch and cut algorithms for detecting critical nodes in undirected graphs［J］. Computational Optimization and Applications， 2012，53： 649-680.

［8］Freeman L C. A set of measures of centrality based on betweenness［J］. Sociometry， 1977，40（1）： 35-41.

［9］Chen Duanbing， Lyu Linyuan， Shang Mingsheng， et al. Identifying influential nodes in complex networks［J］. Physica A： Statistical Mechanics and Its Applications， 2012，391（4）： 1777-1787.

［10］Kitsak M，Gallos L K，Havlin S，et al. Identification of influential sprea-ders in complex networks［J］. Nature Physics， 2010，6： 888-893.

［11］Deb K， Pratap A， Agarwal S， et al. A fast and elitist multiobjective genetic algorithm： NSGA-Ⅱ［J］. IEEE Trans on Evolutionary Computation， 2002，6（2）：182-197.

［12］Addis B， Aringhieri R， Grosso A， et al. Hybrid constructive heuristics for the critical node problem［J］. Annals of Operations Research， 2016，238（1）： 637-649.

［13］朱華， 潘侃， 王磊， 等. 基于DynamicRank的重要节点集挖掘算法［J］. 重庆邮电大学学报： 自然科学版， 2022，34（5）： 869-876. （Zhu Hua， Pan Kan， Wang Lei， et al. Critical nodes mining algorithm based on DynamicRank［J］. Journal of Chongqing University of Posts and Telecommunications： Natural Science Edition， 2022，34（5）： 869-876.）

［14］周丽娜， 常笑， 胡枫. 利用邻接结构熵确定超网络关键节点［J］. 计算机工程与应用， 2022，58（8）： 76-82. （Zhou Lina， Chang Xiao， Hu Feng. Using adjacent structure entropy to determine vital nodes of hypernetwork［J］. Computer Engineering and Applications， 2022，58（8）： 76-82.）

［15］孙百兵， 孙家政， 何泉， 等. 融入社区评估的节点重要性分析［J］. 计算机工程与应用， 2023，59（3）： 226-233. （Sun Baibing， Sun Jiazheng， He Quan， et al. Node importance analysis integrated with community assessment［J］. Computer Engineering and Applications， 2023，59（3）： 226-233.）

［16］刘子彤， 王威， 丁国如， 等. 一种面向有权重通信网络的关键节点识别方法［J］. 数据采集与处理， 2023，38（1）：51-62. （Liu Zitong， Wang Wei， Ding Guoru， et al. A key node identification approach for weighted communication networks［J］. Journal of Data Acquisition and Processing， 2023，38（1）： 51-62.）

［17］Ventresca M. Global search algorithms using a combinatorial unran-king-based problem representation for the critical node detection problem［J］. Computers & Operations Research， 2012，39（11）： 2763-2775.

［18］Mirjalili S.Moth-flame optimization algorithm：a novel nature-inspired heuristic paradigm［J］.Knowledge-Based Systems，2015，89：228-249.

［19］Allam D， Yousri D A， Eteiba M B. Parameters extraction of the three diode model for the multi-crystalline solar cell/module using moth-flame optimization algorithm［J］. Energy Conversion and Mana-gement， 2016，123： 535-548.

［20］Zhao Huiru， Zhao Haoran， Guo Sen. Using GM（1，1） optimized by MFO with rolling mechanism to forecast the electricity consumption of Inner Mongolia［J］. Applied Sciences， 2016，6（1）：20.

［21］Barczak T M， Oyler D C. A model of shield-strata interaction and its implications for active shield setting requirements， RI-9394［R/OL］. （1991-12-01）. https：//www.osti.gov/biblio/5290205.

［22］Hassanien A E， Gaber T， Mokhtar U， et al. An improved moth flame optimization algorithm based on rough sets for tomato diseases detection［J］. Computers and Electronics in Agriculture， 2017，136： 86-96.

［23］Tizhoosh H R. Opposition-based learning： a new scheme for machine intelligence［C］//Proc of International Conference on Computational Intelligence for Modelling， Control and Automation and International Conference on Intelligent Agents， Web Technologies and Internet Commerce. Piscataway， NJ： IEEE Press， 2005： 695-701.

［24］Zheng Wenping， Wu Zhikang， Yang Gui. A novel algorithm for identifying critical nodes in networks based on local centrality［J］. Journal of Computer Research and Development， 2019，56： 1872-1880.

［25］Erdos P， Rényi A. On random graphs［J］. Publications Mathema-ticae， 1959， 6： 290-297.

［26］Barabási A L， Albert R. Emergence of scaling in random networks［J］. Science， 1999，286（5439）： 509-512.

［27］Watts D J， Strogatz S H. Collective dynamics of ‘small-world networks［J］. Nature， 1998， 393： 440-442.

［28］Dolan E D， Mor E J J. Benchmarking optimization software with performance profiles［J］. Mathematical Programming， 2002，91： 201-213.

［29］Guimera R， Danon L， Díaz-Guilera A， et al. Self-similar community structure in organisations［J］. Physical Review E， 2003，68： 065103.

［30］Zachary W W. An information flow model for conflict and fission in small groups［J］. Journal of Anthropological Research， 1977，33（4）： 452-473.

［31］Knuth D E. The Stanford GraphBase： a platform for combinatorial computing［M］. New York： ACM Press， 1993.

收稿日期：2023-02-02；修回日期：2023-04-04  基金項目：国家自然科学基金资助项目（61871475）；广东省自然科学基金资助项目（2021A1515011994）；广州市重点研发计划资助项目（202103000033，201903010043）；广东省科技计划资助项目（2020A1414050060，2020B0202080002，2016A020210122，2015A040405014）；广东省普通高校创新团队项目（2021KCXTD019，2020KCXTD040，2022KCXTD057）；广东省普通高校特色创新项目（KA190578826）；梅州市科技计划资助项目（2021A0305010）；广州市增城区农村科技特派员资助项目（2021B42121631）；广东省教育科学规划课题（2020GXJK102，2018GXJK072）；广东省研究生教育创新计划资助项目（2022XSLT056，2022JGXM115）

作者简介：许钦钧（1998-），男，湖北黄冈人，硕士，主要研究方向为复杂网络；徐龙琴（1977-），女（通信作者），教授，硕士，主要研究方向为智能信息处理、农业物联网、数据挖掘（xlqlw@126.com）；刘双印（1977-），男，教授，博士，主要研究方向为智能信息处理、物联网、大数据；赵学华（1977-），男，副教授，博士，主要研究方向为复杂网络、数据挖掘、大数据．