基于飛蛾撲火算法的關(guān)鍵節(jié)點(diǎn)挖掘方法

許欽鈞 徐龍琴 劉雙印 趙學(xué)華

摘 要：關(guān)鍵節(jié)點(diǎn)挖掘在理解和控制復(fù)雜網(wǎng)絡(luò)系統(tǒng)方面具有重要作用和巨大潛力。提出了一種基于飛蛾撲火優(yōu)化算法的關(guān)鍵節(jié)點(diǎn)挖掘算法，解決關(guān)鍵節(jié)點(diǎn)問題。該算法引入了反向?qū)W習(xí)等策略，以提高解集的質(zhì)量和加快收斂。同時(shí)，設(shè)計(jì)了快速種群演化和復(fù)合高斯進(jìn)化等方法，以優(yōu)化解集并增強(qiáng)解空間探索能力，從而克服局部最優(yōu)陷阱。在多個(gè)合成網(wǎng)絡(luò)和真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上進(jìn)行的對(duì)比實(shí)驗(yàn)結(jié)果表明，提出的算法相較以于其他先進(jìn)的對(duì)比算法具有更高的魯棒性，并驗(yàn)證了該算法部件的有效性。

關(guān)鍵詞：關(guān)鍵節(jié)點(diǎn)； 網(wǎng)絡(luò)連通性； 群智能算法； 飛蛾撲火優(yōu)化算法

中圖分類號(hào)：TP393.02?? 文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：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

近年來(lái)，由于關(guān)鍵節(jié)點(diǎn)挖掘在計(jì)算生物學(xué)［1］、網(wǎng)絡(luò)脆弱性評(píng)估［2］、社交網(wǎng)絡(luò)分析［3］、傳染病傳播控制［4］、精準(zhǔn)營(yíng)銷等領(lǐng)域中的廣泛應(yīng)用潛力，該問題備受關(guān)注。例如，在流行病傳播網(wǎng)絡(luò)中，發(fā)現(xiàn)關(guān)鍵節(jié)點(diǎn)并采取適當(dāng)措施能夠大大減少疾病傳播，這使得關(guān)鍵節(jié)點(diǎn)挖掘研究和調(diào)節(jié)復(fù)雜網(wǎng)絡(luò)的功能具有重要意義。然而，經(jīng)典關(guān)鍵節(jié)點(diǎn)挖掘問題是NP-難問題［5］，這意味著其精確解法需要承擔(dān)呈指數(shù)增長(zhǎng)的計(jì)算復(fù)雜度，難以在大型網(wǎng)絡(luò)中被接受。為了解決這個(gè)問題，本文提出了一種基于飛蛾撲火優(yōu)化算法的關(guān)鍵節(jié)點(diǎn)挖掘算法（moth flame optimization for critical node problem，MFOCNP）。該算法包含一個(gè)快速種群進(jìn)化（fast population evolution，F(xiàn)PE）機(jī)制，結(jié)合了相反學(xué)習(xí)（opposition-based learning，OBL）策略以挖掘具有高質(zhì)量和多樣性的初始種群；一種被稱為飛蛾撲火優(yōu)化算法（MFO）的群智能優(yōu)化算法，通過探索新解決方案并克服局部最優(yōu)陷阱實(shí)現(xiàn)優(yōu)化；以及一種復(fù)合高斯進(jìn)化（HGE）機(jī)制，用于加強(qiáng)探索能力和加速收斂。為了驗(yàn)證本文方法的有效性，在合成網(wǎng)絡(luò)和真實(shí)網(wǎng)絡(luò)上進(jìn)行了實(shí)驗(yàn)，并與其他一流算法進(jìn)行了比較。實(shí)驗(yàn)結(jié)果表明，該算法的性能優(yōu)于其他算法。

1 相關(guān)工作

1.1 關(guān)鍵節(jié)點(diǎn)問題進(jìn)展

經(jīng)典關(guān)鍵節(jié)點(diǎn)挖掘問題（critical node detection problem，CNDP）的定義是：對(duì)于一個(gè)有n=|V|個(gè)點(diǎn)、m= |E|條邊的網(wǎng)絡(luò)N=（V，E）和一個(gè)正整數(shù)K，CNDP問題求一個(gè)規(guī)模不大于K的子集SV，且刪除它能最大限度地降低剩余網(wǎng)絡(luò)N［V＼S］的成對(duì)連通性（連接節(jié)點(diǎn)對(duì)的總和），求得的點(diǎn)集S就是網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)的集合。

由于該問題的理論意義和實(shí)用潛力，文獻(xiàn)中提出大量算法，它們主要分為精確方法和啟發(fā)式方法。

精確方法主要利用整數(shù)線性規(guī)劃（integer linear programming，ILP）將特定網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)挖掘問題轉(zhuǎn)換為可解的目標(biāo)函數(shù)方程式。文獻(xiàn)［5］提出了一個(gè)簡(jiǎn)化的函數(shù)方程和算法（HDCN）。文獻(xiàn)［6］則提出了一種基于Benders分解的方法以精確識(shí)別隨機(jī)網(wǎng)絡(luò)上的關(guān)鍵節(jié)點(diǎn)。文獻(xiàn)［7］使用分支切割算法解決一般網(wǎng)絡(luò)上的關(guān)鍵節(jié)點(diǎn)挖掘，然而，由于該問題的NP難特性［5］，在一般網(wǎng)絡(luò)和大型網(wǎng)絡(luò)中，精確算法的計(jì)算成本較高。所以，啟發(fā)式算法，特別是貪婪算法是一個(gè)性價(jià)比高且必要的替代選擇，其能在有限時(shí)間內(nèi)找出高質(zhì)量的近似解，如BCB［8］、LRBG［9］、KSBG［10］等算法。以下介紹兩種常見的貪婪算法程序。

第一種貪婪算法程序［5］是對(duì)網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)進(jìn)行計(jì)算，找出一個(gè)刪除它后降低網(wǎng)絡(luò)連通性最多的點(diǎn)，并將其從網(wǎng)絡(luò)移入點(diǎn)集S；重復(fù)上述步驟直到點(diǎn)集大小達(dá)到預(yù)設(shè)要求。第二種程序是逐一移除有邊的點(diǎn)并將其加入到點(diǎn)集中，直到網(wǎng)絡(luò)中沒有邊存在。隨后，貪心地將點(diǎn)集中的點(diǎn)逐一放回網(wǎng)絡(luò)，使得每次放回的節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)增加的連通節(jié)點(diǎn)數(shù)最少，直到點(diǎn)集大小達(dá)到預(yù)設(shè)要求。這兩種貪婪算法比較快速、高效，能夠找出近似最優(yōu)解，但結(jié)果缺乏準(zhǔn)確性。為了改善貪婪算法的缺陷，研究者提出了很多其他啟發(fā)式和元啟發(fā)式算法。NSGACNP［11］和復(fù)合啟發(fā)式算法（Greedy3D/Greedy4D）［12］使用貪婪算法作為基礎(chǔ)，通過交換部分節(jié)點(diǎn)來(lái)改進(jìn)解的質(zhì)量。朱華等人［13］通過增強(qiáng)貪婪算法，設(shè)計(jì)一種新的級(jí)聯(lián)概率計(jì)算模型挖掘關(guān)鍵節(jié)點(diǎn)集。周麗娜等人［14］利用超圖中的鄰接結(jié)構(gòu)熵識(shí)別超網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)。孫百兵等人［15］根據(jù)網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)提出一種節(jié)點(diǎn)重要性評(píng)估函數(shù)。劉子彤等人［16］提出一種基于加權(quán)集體影響力模型，用于識(shí)別加權(quán)通信網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)。此外，元啟發(fā)式算法也提供了一些新穎的思路，如Ventresca［17］提出了退火算法（simulated annealing，SA）和基于增量學(xué)習(xí)的群體算法（incremental learning based on population，PBIL），并驗(yàn)證了其有效性。

1.2 飛蛾撲火優(yōu)化算法簡(jiǎn)介

飛蛾撲火優(yōu)化算法（moth-flame optimization algorithm，MFO）是一種基于橫向定位和螺線運(yùn)動(dòng)的群智能優(yōu)化算法，它最初的靈感來(lái)源于飛蛾的行為模式。飛蛾以月亮為參照點(diǎn)，其飛行的方向與它跟月亮的連線保持固定角度，這種導(dǎo)航方法可以使飛蛾在夜間保持直線飛行。然而，人造光源會(huì)誤導(dǎo)飛蛾繞著它飛行，甚至飛進(jìn)光源，這就是“飛蛾撲火”現(xiàn)象（圖1）。Mirjalili［18］對(duì)飛蛾的行為模式進(jìn)行了數(shù)學(xué)模擬，并提出了一種基于橫向定位和螺線運(yùn)動(dòng)的優(yōu)化算法，即飛蛾撲火優(yōu)化算法。該算法結(jié)合了飛蛾的行為模式和螺旋運(yùn)動(dòng)，具有較好的全局搜索能力和收斂速度。在近年來(lái)的群智能優(yōu)化領(lǐng)域，它被認(rèn)為是一種較為流行的優(yōu)化算法。飛蛾的螺線運(yùn)動(dòng)如圖1所示。

2.3 計(jì)算復(fù)雜度

為證明MFOCNP算法的效率，對(duì)算法復(fù)雜度進(jìn)行分析。MFOCNP算法主要有三個(gè)步驟：a）種群初始化和快速演化；b）飛蛾螺線運(yùn)動(dòng)；c）復(fù)合高斯進(jìn)化方法。第一階段，相反學(xué)習(xí)和快速種群演化方法的復(fù)雜度分別不超過O（n×|E|）和O（k×|E|），其中n為蛾的數(shù)量，|E|為網(wǎng)絡(luò)邊的數(shù)量，k為關(guān)鍵節(jié)點(diǎn)的數(shù)量。在第二階段，火焰的更新和分配的極限為O（tm×n×（|E|+n）），其中tm是迭代的最大次數(shù)。螺旋運(yùn)動(dòng)的計(jì)算復(fù)雜度為O（tm×n×k）。最后，復(fù)合高斯進(jìn)化操作的復(fù)雜度為O（tm×n×|E|×k），因此，MFOCNP算法的總計(jì)算復(fù)雜度為O（tm×n×（|E|×k+n）），跟傳統(tǒng)算法相比低很多。

3 實(shí)驗(yàn)設(shè)計(jì)

為了評(píng)估MFOCNP算法的性能，在多個(gè)數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)。使用了多種對(duì)比算法，這些對(duì)比算法在各自的領(lǐng)域內(nèi)具有較高的性能表現(xiàn)，能夠提供一個(gè)有意義的比較標(biāo)準(zhǔn)。在實(shí)驗(yàn)中，分別使用了人工構(gòu)造和真實(shí)的網(wǎng)絡(luò)數(shù)據(jù)集。其中，人工數(shù)據(jù)集針對(duì)不同的網(wǎng)絡(luò)拓?fù)涮卣鬟M(jìn)行構(gòu)建，并加入了一定的噪聲以模擬現(xiàn)實(shí)場(chǎng)景；真實(shí)數(shù)據(jù)集則來(lái)自于網(wǎng)絡(luò)運(yùn)營(yíng)商和互聯(lián)網(wǎng)公司的監(jiān)測(cè)數(shù)據(jù)，包括傳輸數(shù)據(jù)的源地址、目的地址、時(shí)間戳等信息。為了更好地評(píng)估算法的效率，還對(duì)計(jì)算復(fù)雜度進(jìn)行了分析。采用了事前分析法，通過對(duì)算法步驟的時(shí)間復(fù)雜度進(jìn)行計(jì)算，得出了在不同數(shù)據(jù)規(guī)模下的算法復(fù)雜度及其增長(zhǎng)趨勢(shì)。這一分析為評(píng)估算法性能提供了理論支持。

實(shí)驗(yàn)運(yùn)行在一臺(tái)裝有AMD Ryzen 5 4600H處理器，3.00 GHz clock和16 GB RAM的電腦上，系統(tǒng)運(yùn)行Windows，代碼使用Python編寫（源代碼已發(fā)布在https：//github.com/Axuqj/Enhanced-Moth-Flame-Optimization-Algorithm-for-Critical-Node-Detection.git上）。

3.1 對(duì)比算法

為了克服CNP這個(gè)NP-難問題，許多啟發(fā)式算法被提出。在驗(yàn)證MFOCNP算法的性能時(shí)，使用了一些常見的對(duì)比算法，并對(duì)它們的性能進(jìn)行了比較。使用了簡(jiǎn)潔高效的關(guān)鍵節(jié)點(diǎn)挖掘算法（HDCN）［7］，利用貪婪策略初始化極大獨(dú)立點(diǎn)集（MIS），并通過刪除節(jié)點(diǎn)來(lái)達(dá)到目標(biāo)點(diǎn)集大小。

基于介數(shù)中心性的貪婪算法（BCB）［8］利用全局中心性來(lái)優(yōu)化解集。復(fù)合啟發(fā)式算法（Greedy3D）及其改進(jìn)版本（Greedy4D）［12］結(jié)合貪心算法和迭代局部搜索來(lái)解決局部最優(yōu)解問題，而基于K-Shell的貪心算法（KSBG）［10］則使用快速有效的節(jié)點(diǎn)中心性模型進(jìn)行節(jié)點(diǎn)重要性評(píng)估，以提高算法性能。

GCNP算法［24］利用局部節(jié)點(diǎn)中心性和貪婪策略快速有效地找出近似最優(yōu)解，而基于LocalRank的貪婪算法（LRBG）［9］使用廣泛應(yīng)用的節(jié)點(diǎn)度量模型加速搜索最優(yōu)解過程。

此外，還利用了一種基于非支配的多目標(biāo)優(yōu)化遺傳算法NSGA-Ⅱ，該算法具有高效的排序算法和機(jī)制，無(wú)須事先輸入?yún)?shù)［15］。NSGA-Ⅱ算法在關(guān)鍵節(jié)點(diǎn)挖掘問題中被應(yīng)用（即NSGACNP），將該問題劃分為剩余網(wǎng)絡(luò)中連通圖的數(shù)量和連通圖之間的基數(shù)方差兩個(gè)獨(dú)立的目標(biāo)函數(shù)。

3.2 數(shù)據(jù)集

為了更好地驗(yàn)證算法的效果和魯棒性，采用了各種復(fù)雜網(wǎng)絡(luò)生成模型和真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。

1）合成網(wǎng)絡(luò)的生成模型

為評(píng)估MFOCNP算法的效果，選擇了五種經(jīng)典的復(fù)雜網(wǎng)絡(luò)生成模型來(lái)構(gòu)建人工復(fù)雜網(wǎng)絡(luò)數(shù)據(jù)集，并使用這些數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。下面介紹這些網(wǎng)絡(luò)生成模型：

a）Erdos-Renyi（ER）模型［25］。它是一種重要的網(wǎng)絡(luò)生成模型，然而其合成的網(wǎng)絡(luò)缺乏現(xiàn)實(shí)中常見的社區(qū)結(jié)構(gòu)。參考文獻(xiàn)后設(shè)定了參數(shù)［25］，并分別合成三組網(wǎng)絡(luò)（每組包含10個(gè)相似網(wǎng)絡(luò)，保存平均值），如表1所示。

b）Barabasi-Albert （BA）模型［26］。其生成的網(wǎng)絡(luò)又被稱為無(wú)標(biāo)度網(wǎng)絡(luò)，其中節(jié)點(diǎn)的度遵循冪律分布（指數(shù)分布）。參考文獻(xiàn)后設(shè)定參數(shù)［26］，生成三組網(wǎng)絡(luò)（每組包含10個(gè)相似網(wǎng)絡(luò)，保存平均值），如表2所示。

c）Watts-Strogatz（WS）小世界模型［27］。其生成的網(wǎng)絡(luò)中多數(shù)節(jié)點(diǎn)幾步內(nèi)就能到達(dá)其他任一節(jié)點(diǎn)，所以被稱為小世界網(wǎng)絡(luò)。參考文獻(xiàn)后設(shè)定參數(shù)［27］，生成三組網(wǎng)絡(luò)，如表3所示。

2）真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集

為更好地研究MFOCNP算法的性能，從文獻(xiàn)和互聯(lián)網(wǎng)選擇真實(shí)復(fù)雜網(wǎng)絡(luò)數(shù)據(jù)集用于實(shí)驗(yàn)，其參數(shù)如表4所示。其中Electronic-circuits網(wǎng)絡(luò)被存儲(chǔ)在https：//www.weizmann.ac.il/mcb/UriAlon/download/collection-complex-networks；Yeast網(wǎng)絡(luò)由https：//www.weizmann.ac.il/mcb/UriAlon/download/collection-complex-networks提供；Polbooks網(wǎng)絡(luò)由V.Krebs在http：//www.orgnet.com/上編譯。

3.3 性能評(píng)價(jià)指標(biāo)

采用不同性能指標(biāo)對(duì)算法的性能進(jìn)行綜合驗(yàn)證，其中包括：

a）成對(duì)連通性（pairwise connectivity）。該指標(biāo)是關(guān)鍵節(jié)點(diǎn)問題的一個(gè)主要指標(biāo)，它反映了剩余網(wǎng)絡(luò)的連通程度和關(guān)鍵節(jié)點(diǎn)集的質(zhì)量。具體來(lái)說(shuō)，成對(duì)連通性指的是剩余網(wǎng)絡(luò)N［V＼S］中連通節(jié)點(diǎn)對(duì)的數(shù)量，該指標(biāo)數(shù)值越小，意味著點(diǎn)集質(zhì)量越高，算法性能越好。

b）隨機(jī)水平相對(duì)差值。將算法處理后剩余網(wǎng)絡(luò)的成對(duì)連通性標(biāo)記為solution，將隨機(jī)刪除節(jié)點(diǎn)后的成對(duì)連通性標(biāo)記為random。采用隨機(jī)水平相對(duì)差值來(lái)歸一化，便于比較算法性能。隨機(jī)選擇策略是隨機(jī)移除與算法相同數(shù)量的節(jié)點(diǎn)。Er值越大，說(shuō)明算法性能越好。相對(duì)差值Er用百分?jǐn)?shù)表示為

Er=100×random-solutionrandom（14）

c）性能概況指標(biāo)（performance profiles） ［28］。對(duì)于算法A，它在實(shí)例集合T上進(jìn)行各項(xiàng)實(shí)驗(yàn)并在部分實(shí)例中提供了優(yōu)秀解，性能概況指標(biāo)pA（n）表示算法A提供了優(yōu)秀解的實(shí)例數(shù)占總數(shù)的比例。其中，優(yōu)秀解指在某實(shí)例中與最佳解的相對(duì)差值（相對(duì)差值表示為E=[A（I）-best（I）]/best（I）不大于2n-1的解，當(dāng)n=0時(shí)，優(yōu)秀解即為某實(shí)例中出現(xiàn)的最佳解，pA（0）表示算法A提供最優(yōu)解的實(shí)例數(shù)占所有實(shí)例的比例。pA（n）表示為

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

其中：I∈T是T的一個(gè)實(shí)例；A（I）是剩余網(wǎng)絡(luò)的連通節(jié)點(diǎn)對(duì)；best（I）是在實(shí)例I上出現(xiàn)的最佳解（成對(duì)連通性越小，解越好）。

4 實(shí)驗(yàn)結(jié)果與分析

本章實(shí)驗(yàn)主要在不同合成網(wǎng)絡(luò)和真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上，比較了本文算法與其他算法的有效性。采用了多種評(píng)價(jià)指標(biāo)，包括連通節(jié)點(diǎn)對(duì)指標(biāo)、隨機(jī)水平相對(duì)差值和性能概況指標(biāo)等，以深入分析和比較各算法的性能表現(xiàn)。

4.1 在人工網(wǎng)絡(luò)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果與分析

a）連通節(jié)點(diǎn)對(duì)指標(biāo)。表5中算法的結(jié)果是剩余網(wǎng)絡(luò)的連通節(jié)點(diǎn)對(duì)指標(biāo)，其值越小說(shuō)明方法性能越好。

在表5中，第1列表示生成網(wǎng)絡(luò)的類型和大小，k為被移除的節(jié)點(diǎn)數(shù)，第3～10列表示所有算法的連通節(jié)點(diǎn)對(duì)指標(biāo)，每個(gè)實(shí)驗(yàn)中的最優(yōu)解用黑體標(biāo)出。表5數(shù)據(jù)表示MFOCNP算法生成了最優(yōu)的一批解。

b）隨機(jī)水平相對(duì)誤差。將該算法與隨機(jī)抽樣策略進(jìn)行比較。隨機(jī)選擇策略中，隨機(jī)選擇與算法相同數(shù)量的節(jié)點(diǎn)作為解。在圖5中，結(jié)果以百分比表示，數(shù)值越大，性能越好。在BA網(wǎng)絡(luò)中，結(jié)果接近100%，表明MFOCNP算法的性能是隨機(jī)策略的近兩倍。x軸表示相對(duì)誤差，y軸表示實(shí)驗(yàn)名稱。從圖5可以看出，性能最好的是MFOCNP算法。

c）性能概況指標(biāo)。圖6可以直觀地比較各算法的性能表現(xiàn)。圖6表示在一系列實(shí)驗(yàn)中，算法提供合格解的比率，n越大，需要達(dá)到的優(yōu)秀解的要求越高。曲線位置越靠近左上角，算法性能越好。從圖6可以看出，MFOCNP和Greedy3D、Greedy4D在ER、BA和WS網(wǎng)絡(luò)中性能最好；n=0處，MFOCNP在近100%的實(shí)例上提供了最佳解，充分說(shuō)明了算法的魯棒性，Greedy3D和Greedy4D則表現(xiàn)出比其他算法更穩(wěn)定的效果。

4.2 在真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果與分析

為進(jìn)一步驗(yàn)證算法的性能，在真實(shí)網(wǎng)絡(luò)上進(jìn)行了實(shí)驗(yàn)。實(shí)驗(yàn)中采用不同的K值。

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

其中：|V|為節(jié)點(diǎn)總數(shù)；z為關(guān)鍵節(jié)點(diǎn)所占比率。共生成8×7=56個(gè)關(guān)鍵節(jié)點(diǎn)挖掘問題實(shí)例。表6表明MFOCNP算法在大多數(shù)實(shí)驗(yàn)中提供了最佳解。

a）隨機(jī)水平相對(duì)誤差。x軸表示相對(duì)誤差，y軸表示網(wǎng)絡(luò)類型。例如，lesmis1表示z=0.01的lesmis網(wǎng)絡(luò)實(shí)例。

從圖7中可以看出，MFOCNP在大多數(shù)情況下比其他算法表現(xiàn)得更好。

b）性能概況指標(biāo)（performance profiles）。從圖8可以看出，MFOCNP算法提供了一系列較好的解，幾乎所有的最佳解都來(lái)自MFOCNP算法。

4.3 算法組件驗(yàn)證

將MFOCNP算法與MFOCNP0和MFOCNP1兩個(gè)修改版本進(jìn)行比較。兩個(gè)版本分別去掉了兩個(gè)關(guān)鍵組件。對(duì)于MFOCNP0算法，初始種群是隨機(jī)生成的，且缺少了原算法所提出的FPE優(yōu)化策略。對(duì)于MFOCNP1，其解更新過程相對(duì)簡(jiǎn)單，而MFOCNP的更新過程則通過HGE復(fù)合高斯進(jìn)化策略，得到了很大的改進(jìn)。

a）連通節(jié)點(diǎn)對(duì)指標(biāo)。對(duì)比結(jié)果如表7所示。表中：z為被移除節(jié)點(diǎn)的百分比；fbest為最佳目標(biāo)值；favg為平均適應(yīng)度值；tavg為找到最優(yōu)解的平均時(shí)間。

b）隨機(jī)水平相對(duì)誤差。如圖9所示，在大多數(shù)實(shí)驗(yàn)中，MFOCNP算法的性能更好。并且MFOCNP的性能略好于MFOCNP1。數(shù)據(jù)結(jié)果說(shuō)明兩種算法組件在MFOCNP算法中都發(fā)揮著重要的作用。

5 結(jié)束語(yǔ)

針對(duì)經(jīng)典關(guān)鍵節(jié)點(diǎn)挖掘問題，提出一種基于飛蛾撲火優(yōu)化的關(guān)鍵節(jié)點(diǎn)挖掘算法（MFOCNP）。該算法結(jié)合快速種群進(jìn)化（FPE）機(jī)制來(lái)獲得高質(zhì)量的初始種群，采用飛蛾撲火優(yōu)化算法（MFO）和復(fù)合高斯進(jìn)化算法（HGE）來(lái)更新優(yōu)化種群。為加快收斂速度，F(xiàn)PE機(jī)制采用相反學(xué)習(xí)機(jī)制（OBL）和快速種群演化策略來(lái)優(yōu)化初始化。本文算法實(shí)現(xiàn)了利用飛蛾撲火優(yōu)化算法和復(fù)合高斯進(jìn)化算法探索更大的解空間，克服了局部最優(yōu)陷阱。為了證明MFOCNP算法的性能，在各種合成網(wǎng)絡(luò)和真實(shí)網(wǎng)絡(luò)上進(jìn)行了大量實(shí)驗(yàn)。計(jì)算結(jié)果表明，MFOCNP算法在關(guān)鍵節(jié)點(diǎn)挖掘問題上優(yōu)于其他算法，并驗(yàn)證了算法各個(gè)組件的性能。如何將機(jī)器學(xué)習(xí)與關(guān)鍵節(jié)點(diǎn)挖掘相結(jié)合，從而解決動(dòng)態(tài)的大規(guī)模的網(wǎng)絡(luò)問題，是復(fù)雜網(wǎng)絡(luò)中一個(gè)重大挑戰(zhàn)，后期也將對(duì)這一問題進(jìn)行深入探索。

參考文獻(xiàn)：

［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的重要節(jié)點(diǎn)集挖掘算法［J］. 重慶郵電大學(xué)學(xué)報(bào)： 自然科學(xué)版， 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］周麗娜， 常笑， 胡楓. 利用鄰接結(jié)構(gòu)熵確定超網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)［J］. 計(jì)算機(jī)工程與應(yīng)用， 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］孫百兵， 孫家政， 何泉， 等. 融入社區(qū)評(píng)估的節(jié)點(diǎn)重要性分析［J］. 計(jì)算機(jī)工程與應(yīng)用， 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］劉子彤， 王威， 丁國(guó)如， 等. 一種面向有權(quán)重通信網(wǎng)絡(luò)的關(guān)鍵節(jié)點(diǎn)識(shí)別方法［J］. 數(shù)據(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? 基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目（61871475）；廣東省自然科學(xué)基金資助項(xiàng)目（2021A1515011994）；廣州市重點(diǎn)研發(fā)計(jì)劃資助項(xiàng)目（202103000033，201903010043）；廣東省科技計(jì)劃資助項(xiàng)目（2020A1414050060，2020B0202080002，2016A020210122，2015A040405014）；廣東省普通高校創(chuàng)新團(tuán)隊(duì)項(xiàng)目（2021KCXTD019，2020KCXTD040，2022KCXTD057）；廣東省普通高校特色創(chuàng)新項(xiàng)目（KA190578826）；梅州市科技計(jì)劃資助項(xiàng)目（2021A0305010）；廣州市增城區(qū)農(nóng)村科技特派員資助項(xiàng)目（2021B42121631）；廣東省教育科學(xué)規(guī)劃課題（2020GXJK102，2018GXJK072）；廣東省研究生教育創(chuàng)新計(jì)劃資助項(xiàng)目（2022XSLT056，2022JGXM115）

作者簡(jiǎn)介：許欽鈞（1998-），男，湖北黃岡人，碩士，主要研究方向?yàn)閺?fù)雜網(wǎng)絡(luò)；徐龍琴（1977-），女（通信作者），教授，碩士，主要研究方向?yàn)橹悄苄畔⑻幚怼⑥r(nóng)業(yè)物聯(lián)網(wǎng)、數(shù)據(jù)挖掘（xlqlw@126.com）；劉雙?。?977-），男，教授，博士，主要研究方向?yàn)橹悄苄畔⑻幚怼⑽锫?lián)網(wǎng)、大數(shù)據(jù)；趙學(xué)華（1977-），男，副教授，博士，主要研究方向?yàn)閺?fù)雜網(wǎng)絡(luò)、數(shù)據(jù)挖掘、大數(shù)據(jù)．