顧秋陽，吳寶，孫兆洋，池仁勇

（1.浙江工業(yè)大學(xué)管理學(xué)院，浙江 杭州 310023；2.浙江工業(yè)大學(xué)中國(guó)中小企業(yè)研究院，浙江 杭州 310023；3.中國(guó)標(biāo)準(zhǔn)化研究院高新技術(shù)標(biāo)準(zhǔn)化研究所，北京 100191）

1 引言

隨著近年來信息技術(shù)的迅速發(fā)展，復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)間的交流、互動(dòng)形式日趨多樣化，由此產(chǎn)生海量的復(fù)雜網(wǎng)絡(luò)數(shù)據(jù)，其中存在大量節(jié)點(diǎn)間的信息交互集。對(duì)上述數(shù)據(jù)進(jìn)行挖掘，尋找具有影響力的節(jié)點(diǎn)，并基于此有效阻止負(fù)面信息傳播、宣傳正面信息、提升推薦效率已成為學(xué)術(shù)界關(guān)注的焦點(diǎn)之一。據(jù)中國(guó)互聯(lián)網(wǎng)絡(luò)信息中心（CNNIC）發(fā)布的第47 次《中國(guó)互聯(lián)網(wǎng)發(fā)展?fàn)顩r統(tǒng)計(jì)報(bào)告》，截至2020 年12 月，我國(guó)網(wǎng)民規(guī)模達(dá)9.89 億，互聯(lián)網(wǎng)普及率達(dá)70.4%，較2020 年3 月增長(zhǎng)5.9%；同期，我國(guó)網(wǎng)絡(luò)新聞?dòng)脩暨_(dá)7.42 億，占網(wǎng)民整體的75.1%，社交應(yīng)用使用率高達(dá)網(wǎng)民總量的85.5%。2019 年，國(guó)家互聯(lián)網(wǎng)信息辦公室發(fā)布的《數(shù)據(jù)安全管理辦法》中，對(duì)社交網(wǎng)絡(luò)平臺(tái)提出了新的要求。網(wǎng)絡(luò)運(yùn)營(yíng)者應(yīng)采取措施督促提醒用戶對(duì)自己的網(wǎng)絡(luò)行為負(fù)責(zé)、加強(qiáng)自律，對(duì)于節(jié)點(diǎn)通過網(wǎng)絡(luò)轉(zhuǎn)發(fā)給其他節(jié)點(diǎn)制作的信息，應(yīng)自動(dòng)標(biāo)注信息制作者在該社交網(wǎng)絡(luò)上的賬戶或節(jié)點(diǎn)標(biāo)識(shí)。這往往會(huì)選擇合適的節(jié)點(diǎn)群體進(jìn)行信息傳播，而社交網(wǎng)絡(luò)龐大的節(jié)點(diǎn)群體會(huì)使病毒式傳播成為在線社交網(wǎng)絡(luò)中的最大受益者[1-4]。由于進(jìn)行節(jié)點(diǎn)選取和控制的成本有限，因此只能在復(fù)雜網(wǎng)絡(luò)中選擇一組有限數(shù)量的種子節(jié)點(diǎn)，使其在復(fù)雜網(wǎng)絡(luò)中傳播信息，最終實(shí)現(xiàn)影響力最大化問題[5]。本文需解決的問題為如何有效識(shí)別最具影響力的節(jié)點(diǎn)，并將其加入種子節(jié)點(diǎn)集中，該問題又被稱為節(jié)點(diǎn)影響力最大化（IM,influence maximization）問題[6-8]。盡管如文獻(xiàn)[9-10]所示，在現(xiàn)有的節(jié)點(diǎn)影響力最大化算法中，節(jié)點(diǎn)的行為和興趣已被視為信息傳播過程的重要因素，但此類信息并非從真實(shí)復(fù)雜網(wǎng)絡(luò)中獲得的，故只有網(wǎng)絡(luò)結(jié)構(gòu)信息可用于識(shí)別影響力較大的節(jié)點(diǎn)。

目前，已有學(xué)者提出多種用于復(fù)雜網(wǎng)絡(luò)重要節(jié)點(diǎn)識(shí)別的擴(kuò)散模型[11-13]，可用于模擬信息擴(kuò)散過程建模及種子節(jié)點(diǎn)影響力。由于節(jié)點(diǎn)影響力最大化問題的搜索范圍往往很大，故評(píng)估所有可能的節(jié)點(diǎn)子集以定位最佳種子節(jié)點(diǎn)集為NP-hard 問題[14]。而真實(shí)復(fù)雜網(wǎng)絡(luò)的輻射范圍很廣，故利用影響力最大化模型來衡量節(jié)點(diǎn)影響力往往較費(fèi)時(shí)。常用于識(shí)別影響力最大的節(jié)點(diǎn)集的方法是選擇中心節(jié)點(diǎn)，可采用多種方法來度量復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)的中心度，如網(wǎng)絡(luò)度[15]、介數(shù)中間性[16]、緊密度[17]、k-shell[18]及改進(jìn)k-shell[19]。但通過測(cè)量網(wǎng)絡(luò)結(jié)構(gòu)的中心度對(duì)影響力最大化節(jié)點(diǎn)進(jìn)行識(shí)別通常不是解決此問題的最好方法。另外，有研究認(rèn)為節(jié)點(diǎn)影響力最大化問題屬于優(yōu)化問題，并采用貪婪算法、啟發(fā)式算法及元啟發(fā)式算法等來解決該問題。Wang 等[20]提出了改進(jìn)貪婪算法，以此求得擴(kuò)散模型的最優(yōu)解，盡管該算法的精度較高，但其計(jì)算過程十分復(fù)雜，故在大規(guī)模復(fù)雜網(wǎng)絡(luò)中并不實(shí)用[21]。而Bao 等[22]針對(duì)影響力最大化問題提出的啟發(fā)式算法的時(shí)間復(fù)雜度和精度較低，但啟發(fā)式算法得到的值在可達(dá)局部中最優(yōu)[23]。

為識(shí)別一組接近最優(yōu)的具有最大影響力的節(jié)點(diǎn)，首先需要對(duì)節(jié)點(diǎn)影響力進(jìn)行度量，然后找到最有影響力的節(jié)點(diǎn)集。本文首先使用基于Shannon 熵的指標(biāo)來衡量節(jié)點(diǎn)影響力，并將該問題轉(zhuǎn)化為優(yōu)化問題，采用一種改進(jìn)灰狼優(yōu)化算法解決該問題[24]，并利用真實(shí)復(fù)雜網(wǎng)絡(luò)數(shù)據(jù)集進(jìn)行數(shù)值計(jì)算。

2 相關(guān)工作

本文基于圖論對(duì)復(fù)雜網(wǎng)絡(luò)圖進(jìn)行建模，其中，節(jié)點(diǎn)代表復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)，邊代表節(jié)點(diǎn)間存在的關(guān)系。首先對(duì)一些經(jīng)典的擴(kuò)散模型以及用于影響力最大化問題的常見方法進(jìn)行回顧。擴(kuò)展模型常用于模擬真實(shí)世界中的傳播過程，常用的擴(kuò)散模型包括閾值模型[25]、級(jí)聯(lián)模型[26]和傳染病模型[27]。其中，獨(dú)立級(jí)聯(lián)模型（IC,independent cascading）為現(xiàn)今應(yīng)用最廣泛的擴(kuò)散模型之一[26]，其中每個(gè)節(jié)點(diǎn)都處于活躍或非活躍模式中。為度量種子節(jié)點(diǎn)集S的影響力，將最初放置在種子節(jié)點(diǎn)集S中的節(jié)點(diǎn)定義為活躍節(jié)點(diǎn)，并將所有其他節(jié)點(diǎn)定義為非活躍節(jié)點(diǎn)。在每個(gè)時(shí)間段t中，時(shí)間段t?1 中被激活的每個(gè)節(jié)點(diǎn)都有一次機(jī)會(huì)激活其非活躍的鄰節(jié)點(diǎn)（激活概率為p），該過程會(huì)一直持續(xù)到該時(shí)間段內(nèi)沒有新節(jié)點(diǎn)為止。最后，在此過程迭代多次后得到的激活節(jié)點(diǎn)數(shù)量即為節(jié)點(diǎn)集S的影響范圍。

有關(guān)節(jié)點(diǎn)影響力最大化問題，現(xiàn)有研究可分為兩大類。第一類為識(shí)別節(jié)點(diǎn)影響力并對(duì)其進(jìn)行排序。在多數(shù)相關(guān)研究中，根據(jù)網(wǎng)絡(luò)結(jié)構(gòu)和節(jié)點(diǎn)網(wǎng)絡(luò)位置，可使用中心性度量法來衡量節(jié)點(diǎn)影響力。雖然中心性方法計(jì)算較簡(jiǎn)單，也能較好地確定節(jié)點(diǎn)活躍度[28]，但這類方法在識(shí)別Top-k 影響力節(jié)點(diǎn)時(shí)精度不高。Bao 等[22]提出了一種優(yōu)化種子節(jié)點(diǎn)集的方法，使其總體影響范圍最大化，并在考慮節(jié)點(diǎn)影響力的同時(shí)，考慮了網(wǎng)絡(luò)中的節(jié)點(diǎn)距離，以進(jìn)一步提高重要節(jié)點(diǎn)識(shí)別算法的有效性。第二類節(jié)點(diǎn)影響力最大化方法在考慮網(wǎng)絡(luò)可達(dá)性的基礎(chǔ)上，將該問題轉(zhuǎn)化為優(yōu)化問題（如貪婪算法、啟發(fā)式算法、元啟發(fā)式算法等）。關(guān)于貪婪算法，Kempe 等[25]對(duì)含有k個(gè)最具影響力的種子節(jié)點(diǎn)集S進(jìn)行識(shí)別，并迭代k次，每次迭代時(shí)使用擴(kuò)散模型來估計(jì)該集合的影響力。

為改善節(jié)點(diǎn)影響力最大化問題優(yōu)化過程中存在的時(shí)間復(fù)雜度問題，研究者提出了一系列啟發(fā)式算法，用于選擇節(jié)點(diǎn)影響力最大化集合。啟發(fā)式算法通過使用遞歸法給每個(gè)節(jié)點(diǎn)分配一個(gè)分?jǐn)?shù)，并選擇分?jǐn)?shù)最高的top-k 節(jié)點(diǎn)作為種子節(jié)點(diǎn)集。Chen 等[29]提出了2 種方法用于選擇種子節(jié)點(diǎn)集，首先以每個(gè)節(jié)點(diǎn)度作為影響力指標(biāo)，并以k次迭代選擇種子節(jié)點(diǎn)集。在每個(gè)步驟中，都可將影響力最大的節(jié)點(diǎn)添加到種子節(jié)點(diǎn)集中。如節(jié)點(diǎn)v加入種子節(jié)點(diǎn)集，則其鄰節(jié)點(diǎn)影響力將會(huì)隨之降低，且被選為種子節(jié)點(diǎn)的概率也會(huì)降低。Wang 等[30]所提度懲罰法嘗試同樣方法來選擇種子節(jié)點(diǎn)集，將節(jié)點(diǎn)v選為種子節(jié)點(diǎn)，就需懲罰二跳內(nèi)的所有鄰節(jié)點(diǎn)，并降低被選為種子節(jié)點(diǎn)的概率。該方法可有效減少網(wǎng)絡(luò)中種子節(jié)點(diǎn)的重疊現(xiàn)象，并增加節(jié)點(diǎn)分散性。Guo 等[31]提出了基于距離圖對(duì)具有適當(dāng)距離的節(jié)點(diǎn)進(jìn)行識(shí)別和分類，以使各組中的節(jié)點(diǎn)對(duì)間距離都大于閾值。Bao 等[22]提出了啟發(fā)式聚類算法，確定每對(duì)節(jié)點(diǎn)間的相似度，并選擇各集群中影響力最大的節(jié)點(diǎn)作為種子節(jié)點(diǎn)，將節(jié)點(diǎn)影響最大化問題建模為多目標(biāo)優(yōu)化問題。

元啟發(fā)式算法通常首先定義適應(yīng)度函數(shù)，將節(jié)點(diǎn)影響力最大化問題建模為優(yōu)化問題，并應(yīng)用各種改進(jìn)優(yōu)化算法對(duì)該問題進(jìn)行解決。Jiang 等[32]將種子節(jié)點(diǎn)集S的影響定義為預(yù)期擴(kuò)散值（EDV,expected diffusion value）。Gong 等[21]引入改進(jìn)EDV值，并使用粒子群優(yōu)化（PSO,particle swarm optimization）算法來優(yōu)化目標(biāo)函數(shù)。Sun[33]用復(fù)制對(duì)稱平均場(chǎng)理論來解決節(jié)點(diǎn)影響力最大化問題。本文首先定義了適應(yīng)度函數(shù)，然后利用灰狼優(yōu)化算法提出了一種適應(yīng)度函數(shù)對(duì)重要節(jié)點(diǎn)識(shí)別方法進(jìn)行優(yōu)化。

3 算法設(shè)計(jì)

3.1 預(yù)備知識(shí)

本文首先利用熵的概念定義了適應(yīng)度函數(shù)，并將節(jié)點(diǎn)影響力最大化問題設(shè)計(jì)為優(yōu)化問題，隨后利用改進(jìn)灰狼優(yōu)化算法解決該問題。根據(jù)Shannon 熵值，如X∈{x1,x2,…,xn}，且pi為目標(biāo)xi被選擇的概率，其中，可根據(jù)式(1)計(jì)算X的熵。

灰狼優(yōu)化（GWO,gray wolf optimization）算法[24]是一種基于種群的演化算法，其靈感來源于灰狼的狩獵行為。如圖1 所示，灰狼遵循嚴(yán)格的社會(huì)等級(jí)制度，在社會(huì)中主要分為α、β、γ、δ這4 種。α狼、β狼及γ狼在狩獵過程中主要負(fù)責(zé)攻擊，而δ狼在團(tuán)隊(duì)中扮演替罪羊的角色。根據(jù)不同狼的特征，可將GWO 算法建模如下。首先，隨機(jī)生成一組解，使得每個(gè)解都與一頭狼相對(duì)應(yīng)，以表示其位置。其中，適應(yīng)性排名第一的為α狼，適應(yīng)性排名第二和第三的分別為β狼和γ狼，剩余則為δ狼。該算法根據(jù)α、β、γ狼的位置進(jìn)行空間搜索，以找到獵物的位置（即最優(yōu)解）。上述3 種狼可以預(yù)測(cè)獵物位置，而δ狼則根據(jù)另外3 種狼的位置來改變自身位置，從而找到離獵物更近的位置，該算法嘗試在迭代過程中找到最優(yōu)解。在每次迭代過程中，δ狼都會(huì)試圖根據(jù)其他狼群的位置來改變自身位置。在每次迭代t中，δ狼都會(huì)根據(jù)迭代次數(shù)t+1確定自身的新位置，即Xi(t+1)，具體如式(2)所示。

其中，每只δ狼都會(huì)試圖根據(jù)Y1、Y2、Y3來確定更優(yōu)位置，Y∈[Y1,Y2,Y3]值可根據(jù)狼的當(dāng)前位置和α狼的位置計(jì)算得到，具體如式(3)所示。

其中，Dα的計(jì)算式為

其中，t表示當(dāng)前迭代次數(shù)，Xi(t)表示本次迭代中狼i的位置，而Xα表示α狼的位置。結(jié)合β狼和γ狼的當(dāng)前位置，利用式(5)可計(jì)算得到Y(jié)2和Y3的值。

其中，Dβ和Dγ的值可由式(6)計(jì)算得到。

其中，Xβ和Xγ分別表示β狼和γ狼的位置，A和C分別表示如式(7)所示的系數(shù)向量。

其中，r1和r2表示區(qū)間[0,1]內(nèi)的隨機(jī)值，a值為迭代過程中從2 線性趨近于0 的控制參數(shù)。a值在時(shí)段t中的計(jì)算方法如式(8)所示。

其中，maxt表示重要節(jié)點(diǎn)識(shí)別算法的迭代次數(shù)。在迭代過程中，狼群間的位置矛盾減少，算法逐漸收斂，最后得到α狼最優(yōu)解，并將其作為最優(yōu)解決方案。經(jīng)典灰狼優(yōu)化算法的執(zhí)行過程如算法1 所示[25]，其中n表示種群規(guī)模。

算法1灰狼優(yōu)化算法

輸入狼α,β,,γ δ的位置

輸出集合{xα,xβ,xγ,xδ}

本文使用無向圖G=(V,E)對(duì)復(fù)雜網(wǎng)絡(luò)圖進(jìn)行建模，其中，V={v1,v2,…,v|V|}表示復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)集，E表示節(jié)點(diǎn)間的關(guān)系邊集。邊ei,j∈E表示2 個(gè)節(jié)點(diǎn)vi和vj間的距離，且這2 個(gè)節(jié)點(diǎn)為鄰節(jié)點(diǎn)。N i?V表示節(jié)點(diǎn)vi的鄰居，di=|Ni|表示節(jié)點(diǎn)vi的影響力。表示節(jié)點(diǎn)vi的二跳鄰節(jié)點(diǎn)（即鄰節(jié)點(diǎn)的鄰節(jié)點(diǎn)）。節(jié)點(diǎn)影響力最大化問題的目標(biāo)是識(shí)別具有k個(gè)節(jié)點(diǎn)的集合S，以啟動(dòng)傳播過程，從而使傳播影響最大化，即激活節(jié)點(diǎn)數(shù)量最大化。在本文的其余部分中，S′表示種子節(jié)點(diǎn)集S中節(jié)點(diǎn)的鄰節(jié)點(diǎn)或二跳鄰節(jié)點(diǎn)的節(jié)點(diǎn)集合。

3.2 適應(yīng)度函數(shù)

本文選擇節(jié)點(diǎn)作為種子節(jié)點(diǎn)集中的節(jié)點(diǎn)，其中每個(gè)節(jié)點(diǎn)都具有較高影響力，且選擇的集合盡可能地覆蓋整個(gè)網(wǎng)絡(luò)，以保證信息傳播最大化。在傳播過程中，節(jié)點(diǎn)vj S′∈ 被激活，即接受信息，可使用式(9)進(jìn)行計(jì)算。

其中，pi,j表示信息從vi傳播到vj的概率。式(9)可用來計(jì)算節(jié)點(diǎn)vj收到其鄰節(jié)點(diǎn)發(fā)送信息的概率，且其鄰節(jié)點(diǎn)都為S集成員。如果節(jié)點(diǎn)vj在S集中沒有鄰節(jié)點(diǎn)，則可將其視為零集合。而式(9)等號(hào)右邊第二項(xiàng)可用來計(jì)算節(jié)點(diǎn)vj收到其二跳鄰節(jié)點(diǎn)發(fā)送信息的概率，且其二跳鄰節(jié)點(diǎn)也為S集中的成員。這兩部分都根據(jù)概率規(guī)則進(jìn)行求和，在傳播過程中不同節(jié)點(diǎn)不會(huì)產(chǎn)生相同影響。如果影響力較大的節(jié)點(diǎn)接收到該信息，則其可能會(huì)傳播至復(fù)雜網(wǎng)絡(luò)的其他領(lǐng)域，各節(jié)點(diǎn)v j∈S′值。本文所提基于改進(jìn)灰狼優(yōu)化的重要節(jié)點(diǎn)識(shí)別算法中，適應(yīng)度函數(shù)為。使用本文所提IGW-CNI算法尋找種子節(jié)點(diǎn)，以使S′集中的節(jié)點(diǎn)數(shù)量最大化，且其中所有節(jié)點(diǎn)都具有較大影響力。在運(yùn)用求和運(yùn)算符后，將S′集中有限的具有較高價(jià)值的節(jié)點(diǎn)和無價(jià)值節(jié)點(diǎn)相組合，使適應(yīng)度函數(shù)計(jì)算得到的值實(shí)現(xiàn)最大化。在此情況下，如果無法將信息傳播給有影響力的節(jié)點(diǎn)，會(huì)導(dǎo)致所選節(jié)點(diǎn)的影響力大幅降低。在適應(yīng)度函數(shù)中使用熵來解決此問題，使節(jié)點(diǎn)在S′集中的均衡節(jié)點(diǎn)能更有效提升集S的影響力。另一方面，熵值隨著S值的增大而增大，故需進(jìn)行歸一化。集S的適應(yīng)度熵值可定義為

3.3 改進(jìn)灰狼優(yōu)化算法

參考文獻(xiàn)[34]的結(jié)論可知，度為1 的節(jié)點(diǎn)被選為種子節(jié)點(diǎn)的概率非常低。在許多真實(shí)復(fù)雜網(wǎng)絡(luò)中，大部分節(jié)點(diǎn)只存在一個(gè)鄰節(jié)點(diǎn)。為有效降低本文所提IGW-CNI 算法的時(shí)間復(fù)雜度，僅將影響力大于1 的節(jié)點(diǎn)選為候選種子節(jié)點(diǎn)，并將這些節(jié)點(diǎn)表示為。而每只狼（即每個(gè)解）都存在2 個(gè)屬性，即位置和對(duì)應(yīng)的種子節(jié)點(diǎn)集。狼i的位置可表示為帶有節(jié)點(diǎn)|V′| 的向量xi，其中第j個(gè)節(jié)點(diǎn)表示節(jié)點(diǎn)被選為種子節(jié)點(diǎn)的概率。狼i對(duì)應(yīng)的種子集為Si，其中包含k個(gè)節(jié)點(diǎn)，且其值在Xi中最高。

算法2 給出了本文所提IGW-CNI 算法的具體流程。首先，隨機(jī)生成n個(gè)主要解，并利用隨機(jī)位置函數(shù)生成每個(gè)隨機(jī)解；其次，利用式(10)來計(jì)算解的適應(yīng)度值，并根據(jù)解的適應(yīng)度值來選擇確定α、β、γ狼。進(jìn)行maxt次迭代操作，以最大化適應(yīng)度。在每次迭代過程中，更新δ的位置，并給出更新后的位置。為每只狼i確定種子集Si，而后計(jì)算每個(gè)子集Si的適應(yīng)度值，并根據(jù)適應(yīng)度值，將最佳解更新α、β、γ狼；隨機(jī)更新β、γ狼的位置，避免產(chǎn)生局部最優(yōu)解。

算法2本文所提IGW-CNI 算法

輸入圖G=(V,E)，種子集規(guī)模k，群體規(guī)模n，迭代周期maxt

輸出集合，不同參數(shù)下的種子集S

在本文所提IGW-CNI 算法中，利用隨機(jī)位置函數(shù)生成基本解i（狼i的基本位置Xi及其對(duì)應(yīng)的種子節(jié)點(diǎn)集Si），該函數(shù)的運(yùn)行機(jī)制如文獻(xiàn)[13]所提算法所示。其中，給每個(gè)節(jié)點(diǎn)vj V′∈ 賦隨機(jī)值Xi,j，并將該隨機(jī)值作為該節(jié)點(diǎn)被選為種子節(jié)點(diǎn)的概率，且該概率與節(jié)點(diǎn)的影響力成正比。在本文所提IGW-CNI 算法中，根據(jù)α、βγ、狼的位置來更新δ狼的位置，以期獲得更優(yōu)位置。故基于此設(shè)置了更新位置函數(shù)，該函數(shù)進(jìn)程如文獻(xiàn)[12]所提算法所示。其中，為更新節(jié)點(diǎn)vj在狼i，即Xi,j中的概率，參考了該節(jié)點(diǎn)為α、β、γ的位置Xi，可計(jì)算Y1、Y2、Y3的值，并相應(yīng)計(jì)算Xi,j(t+1)的值。通過計(jì)算每個(gè)節(jié)點(diǎn)v j∈V'的Xi,j(t+1)值，將迭代周期t+1內(nèi)狼i的位置更新為Xi(t+1)，并更新Xi中的Xi,j，以對(duì)每個(gè)Xi,j(j∈1,…,|V′|)，都在多次迭代中更新狼i的位置，重復(fù)此計(jì)算可更新每次迭代中狼的位置。

4 數(shù)值算例

4.1 數(shù)據(jù)說明與參數(shù)設(shè)置

為證明本文所提IGW-CNI 算法的有效性，本文使用4 個(gè)真實(shí)復(fù)雜網(wǎng)絡(luò)數(shù)據(jù)集進(jìn)行數(shù)值模擬，以便觀察算法對(duì)現(xiàn)實(shí)情況的適應(yīng)度（實(shí)驗(yàn)中使用的真實(shí)復(fù)雜網(wǎng)絡(luò)數(shù)據(jù)集特征如表1 所示）。其中，激活率為節(jié)點(diǎn)激活概率，根據(jù)網(wǎng)絡(luò)圖的稀疏性進(jìn)行設(shè)置，并基于網(wǎng)絡(luò)節(jié)點(diǎn)度和二階度的平均值進(jìn)行計(jì)算。本文使用Python 軟件以近期的熱點(diǎn)事件“HUAWEI event”和“華為事件”的30 個(gè)熱點(diǎn)評(píng)論節(jié)點(diǎn)作為初始節(jié)點(diǎn)，分別爬取Facebook、Twitter、新浪微博和豆瓣的復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)據(jù)集作為仿真實(shí)驗(yàn)的基礎(chǔ)數(shù)據(jù)集（爬取時(shí)間為2020 年4 月23 日至2020 年11 月16 日）。本文將每個(gè)節(jié)點(diǎn)作為一個(gè)節(jié)點(diǎn)，使用節(jié)點(diǎn)間的邊界表示節(jié)點(diǎn)間的關(guān)系。本文選擇了10 個(gè)具有較強(qiáng)影響力的節(jié)點(diǎn)及其鄰節(jié)點(diǎn)列表作為復(fù)雜網(wǎng)絡(luò)初始節(jié)點(diǎn)，以此生成了簡(jiǎn)單復(fù)雜網(wǎng)絡(luò)。實(shí)驗(yàn)在MATLAB 2017b 環(huán)境下實(shí)施，并在Windows10操作系統(tǒng)的服務(wù)器（Intel Xeon 處理器（34 GHz）和32 GB 內(nèi)存）上進(jìn)行。

表1 復(fù)雜網(wǎng)絡(luò)數(shù)據(jù)集說明

為評(píng)估本文所提IGW-CNI 重要節(jié)點(diǎn)識(shí)別算法的性能，將其結(jié)果與現(xiàn)有較成熟的重要節(jié)點(diǎn)識(shí)別算法進(jìn)行比較，其中包括 Node2vec[17]、PageRank 法[28]、度遞減搜索策略（DDSE,degree descending search strategy）[23]和模擬退火EDV 值（SADV,simulated annealing EDV）[35]。由于實(shí)驗(yàn)中IGW-CNI 重要節(jié)點(diǎn)識(shí)別算法預(yù)測(cè)列表在每次運(yùn)行時(shí)的結(jié)果都可能不同，故設(shè)置評(píng)估結(jié)果為迭代100 次運(yùn)行后的平均值，運(yùn)行的平均標(biāo)準(zhǔn)差為1.524。首先，本文對(duì)所提IGW-CNI 算法參數(shù)對(duì)適應(yīng)度函數(shù)值的影響進(jìn)行分析，得到了節(jié)點(diǎn)規(guī)模和迭代周期的最優(yōu)值。為分析迭代周期的影響，設(shè)迭代周期的取值范圍為[0,50]。在適應(yīng)度函數(shù)值為[10,20,30,40,50]的情況下，各網(wǎng)絡(luò)數(shù)據(jù)集中的實(shí)驗(yàn)結(jié)果如圖1 所示。由圖1 可知，當(dāng)?shù)芷诔^20 時(shí)，適應(yīng)度值沒有顯著增加，故在后續(xù)實(shí)驗(yàn)中將maxt設(shè)為20。

圖1 不同迭代周期下的適應(yīng)度值

本文還對(duì)節(jié)點(diǎn)規(guī)模與適應(yīng)度值間的關(guān)系進(jìn)行研究，設(shè)迭代周期的取值范圍為[0,50]，并計(jì)算當(dāng)種群適應(yīng)度函數(shù)值為{10,20,30,40,50}時(shí)不同節(jié)點(diǎn)規(guī)模下的適應(yīng)度值，結(jié)果如圖2 所示。由圖2 可知，適應(yīng)度值隨著節(jié)點(diǎn)規(guī)模的增大而增大，但當(dāng)節(jié)點(diǎn)規(guī)模大于20 時(shí)，適應(yīng)度值沒有顯著增加，故將節(jié)點(diǎn)規(guī)模固定為20。

圖2 不同節(jié)點(diǎn)規(guī)模下的適應(yīng)度值

4.2 實(shí)驗(yàn)結(jié)果

本節(jié)對(duì)所提算法的收斂速度進(jìn)行了研究，并研究了優(yōu)化過程中的狼群運(yùn)動(dòng)，計(jì)算了2 次連續(xù)迭代t和t+1 中狼i位置間的歐氏距離。而所有類似的狼在連續(xù)2 次迭代t和t+1 中的平均移動(dòng)（AM,average movement）為

其中，n表示節(jié)點(diǎn)規(guī)模。實(shí)驗(yàn)結(jié)果如圖3 所示。由圖3 可知，在初始迭代中的平均運(yùn)動(dòng)增加，隨著迭代次數(shù)的增加，平均移動(dòng)次數(shù)收斂。盡管在最終迭代中存在振蕩行為，避免了算法陷入局部最優(yōu)解，但所提算法最終會(huì)呈收斂趨勢(shì)。

圖3 不同復(fù)雜網(wǎng)絡(luò)中平均移動(dòng)分析結(jié)果

本文對(duì)所提IGW-CNI 算法與其他重要節(jié)點(diǎn)識(shí)別算法的性能進(jìn)行比較。為此，將種子節(jié)點(diǎn)集的規(guī)模定義為[0,50]，并對(duì)種子節(jié)點(diǎn)集的影響力進(jìn)行評(píng)價(jià)，相關(guān)結(jié)果如圖4 所示。由圖4 可知，與其他算法相比，本文所提IGW-CNI 算法具有較好表現(xiàn)，且在種子節(jié)點(diǎn)數(shù)量相同的情況下影響力較大，這是由于隨著種子節(jié)點(diǎn)集規(guī)模的增加，種子節(jié)點(diǎn)間的距離也發(fā)揮重要作用，故IGW-CNI 算法比其他算法所選擇的種子節(jié)點(diǎn)集具有更高的影響力，即本文所提算法在不同種子集規(guī)模下都優(yōu)于其他算法。隨著種子集規(guī)模的擴(kuò)大，本文所提算法得到的種子集影響力的增長(zhǎng)速度快于其他算法，這是由于IGW-CNI 算法利用改進(jìn)灰狼優(yōu)化算法來進(jìn)行種子集估計(jì)并利用隨機(jī)位置函數(shù)生成基本解，因此得到的種子集規(guī)模較其他經(jīng)典算法會(huì)具有更快的增長(zhǎng)速度。

圖4 不同復(fù)雜網(wǎng)絡(luò)中種子集規(guī)模對(duì)影響力的算法比較結(jié)果

本文進(jìn)一步改變IC 模型的激活率以分析其對(duì)算法性能的影響。為此，將k值設(shè)為30，激活率值設(shè)置為區(qū)間[0,0.2]，間隔為0.005。結(jié)果如圖5 所示，隨著p值的增大，節(jié)點(diǎn)集的影響力也隨之增加。本文所提IGW-CNI 算法的性能在大多數(shù)情形下較其他算法為最優(yōu)，且隨著p值的增大，其優(yōu)勢(shì)更加突出。這是由于節(jié)點(diǎn)影響力隨著p值的增大而增大，而在適應(yīng)度函數(shù)中應(yīng)用熵函數(shù)可使IGW-CNI 算法選擇重疊較少的種子集，故本文所提IGW-CNI 算法在激活率較高時(shí)方面優(yōu)于其他算法，即本文所提IGW-CNI 算法在不同p值下都優(yōu)于其他算法，且隨著激活率p值的增大，本文所提算法得到種子集的影響力的增長(zhǎng)速度快于其他算法。

圖5 不同復(fù)雜網(wǎng)絡(luò)中激活率對(duì)影響力的算法比較結(jié)果

本文使用如式(12)所示精度計(jì)算方法進(jìn)一步進(jìn)行算法比較。

其中，真正例（TP,true positive）表示正確預(yù)測(cè)鏈接的數(shù)量，真負(fù)例（TN,true negative）表示正確的未預(yù)測(cè)鏈接的數(shù)量，假正例（FP,false positive）表示錯(cuò)誤預(yù)測(cè)鏈接的數(shù)量，假負(fù)例（FN,false negative）表示錯(cuò)誤的未預(yù)測(cè)鏈接的數(shù)量。

算法精度比較結(jié)果如表2 所示。由表2 可知，本文所提IGW-CNI 算法在不同數(shù)據(jù)集中都優(yōu)于其他重要節(jié)點(diǎn)識(shí)別算法，這是由于本文將影響最大化問題建模為具有成本函數(shù)的優(yōu)化問題，并采用改進(jìn)灰狼優(yōu)化算法加以解決，有效提升了算法精度。在Facebook 數(shù)據(jù)集中，PageRank 與DDSE法的性能僅次于本文所提IGW-CNI 法，這是由于在聚類系數(shù)較高、激活率較低的情況下，PageRank 與DDSE 法都考慮了入鏈數(shù)量的變化，故計(jì)算精度相對(duì)較高；在 Twitter 數(shù)據(jù)集中，SADV 法的性能僅次于本文所提IGW-CNI 法，這是由于在平均度與激活率較高的情況下模擬退火算法可更好地加速收斂過程，因此可以得到相對(duì)較優(yōu)的計(jì)算精度結(jié)果；在新浪微博數(shù)據(jù)集中，N2V 和 CN 法的性能僅次于本文所提IGW-CNI 法，這是由于在平均路徑較大的情況下，基于網(wǎng)絡(luò)圖最短路徑進(jìn)行鄰節(jié)點(diǎn)度計(jì)算可有效提升算法計(jì)算精度。

4.3 統(tǒng)計(jì)檢驗(yàn)

本文在此對(duì)測(cè)試算法性能的統(tǒng)計(jì)顯著性差異進(jìn)行進(jìn)一步分析。為取得統(tǒng)計(jì)顯著性，進(jìn)行了Friedman檢驗(yàn)，使用Bonferroni法來校正實(shí)驗(yàn)結(jié)果[36]，并設(shè)置可信度分?jǐn)?shù)為α=0.05，這表明如果p<0.05，則存在差異顯著。表3 中，本文所提IGW-CNI 算法將成本函數(shù)表示為節(jié)點(diǎn)影響力及其間的距離，并使用Shannon 熵對(duì)節(jié)點(diǎn)影響力進(jìn)行度量的優(yōu)勢(shì)較其他經(jīng)典算法會(huì)充分體現(xiàn)。Friedman 檢驗(yàn)對(duì)AUC 的觀察檢驗(yàn)值Ff為54.142，均大于相應(yīng)的χ2值（即χ2(αc,Df)）。當(dāng)置信區(qū)間α=0.05、自由度Df=8時(shí)，χ2值為15.51，故拒絕零假設(shè)。

表3 對(duì)AUROC 值的Friedman 統(tǒng)計(jì)檢驗(yàn)結(jié)果

4.4 大數(shù)據(jù)集實(shí)驗(yàn)

為檢驗(yàn)本文所提IGW-CNI 算法在極限條件下的適用性，本節(jié)使用規(guī)模更大的 MovieLens 20M、DatingT 和Netflix 等復(fù)雜網(wǎng)絡(luò)數(shù)據(jù)集對(duì)上述重要節(jié)點(diǎn)識(shí)別算法進(jìn)行對(duì)比實(shí)驗(yàn)，以進(jìn)一步分析本文所提算法在大數(shù)據(jù)集中的適用性（其中MovieLens 20M 和Netflix 數(shù)據(jù)集常用于推薦算法研究，且呈現(xiàn)包含節(jié)點(diǎn)和目標(biāo)2 種節(jié)點(diǎn)的二部圖網(wǎng)絡(luò)結(jié)構(gòu)，但本文所提算法更加重視在網(wǎng)絡(luò)環(huán)境下的應(yīng)用，故在上述2 種數(shù)據(jù)集中只采用節(jié)點(diǎn)以進(jìn)行大數(shù)據(jù)集實(shí)驗(yàn)。這也從另一角度對(duì)本文所提IGW-CNI 重要節(jié)點(diǎn)識(shí)別算法在二部網(wǎng)絡(luò)圖中的適用性進(jìn)行分析，進(jìn)一步證實(shí)了本文所提算法的普適性）。其中，MovieLens20M 被國(guó)內(nèi)外學(xué)者認(rèn)為是最穩(wěn)定的基準(zhǔn)數(shù)據(jù)集之一，其包含139 428 個(gè)節(jié)點(diǎn)對(duì)27 493 部影片的20 351 902 條評(píng)分；DatingT 數(shù)據(jù)集包括136 739 名男性和179 332 名女性組成的18 293 016 條交友記錄；Netflix 數(shù)據(jù)集中包括480 189 個(gè)節(jié)點(diǎn)對(duì)17 770 部電影的100 480 507 條評(píng)分記錄。圖6 給出了同等參數(shù)條件下上述3 種大數(shù)據(jù)集中的算法比較結(jié)果。由圖6 可知，在體量更大的數(shù)據(jù)集中的實(shí)驗(yàn)結(jié)果基本與圖5 中的實(shí)驗(yàn)結(jié)果一致。此外，本文還使用上述3 種大數(shù)據(jù)集作為對(duì)照組重復(fù)進(jìn)行了精度與效率等方面的實(shí)驗(yàn)，結(jié)論與前文一致，故在此不再贅述。

圖6 不同大規(guī)模復(fù)雜網(wǎng)絡(luò)中激活率對(duì)影響力的算法比較結(jié)果

4.5 時(shí)間復(fù)雜度

最后，本文對(duì)所提IGW-CNI 算法的計(jì)算時(shí)間復(fù)雜度效率進(jìn)行了分析，并對(duì)算法的平均運(yùn)行時(shí)間進(jìn)行了比較，結(jié)果如表4 所示。由表4 可知，本文所提IGW-CNI 法的效率高于其他算法，且獲得的種子節(jié)點(diǎn)集的影響力性能更優(yōu)。

表4 時(shí)間復(fù)雜度實(shí)驗(yàn)結(jié)果

5 結(jié)束語

復(fù)雜網(wǎng)絡(luò)中的重要節(jié)點(diǎn)識(shí)別對(duì)電子商務(wù)、網(wǎng)絡(luò)營(yíng)銷等多個(gè)領(lǐng)域都有很大影響。在預(yù)算有限的情況下，網(wǎng)絡(luò)營(yíng)銷所面臨的一個(gè)主要挑戰(zhàn)是識(shí)別少數(shù)具有影響力的重要節(jié)點(diǎn)集，即種子節(jié)點(diǎn)集，以期通過將信息傳遞給種子節(jié)點(diǎn)集在復(fù)雜網(wǎng)絡(luò)中獲得較大影響力，故可將此問題轉(zhuǎn)化為節(jié)點(diǎn)影響最大化問題。本文將影響最大化問題建模為具有成本函數(shù)的優(yōu)化問題，并采用改進(jìn)灰狼優(yōu)化算法解決此問題。最后基于真實(shí)復(fù)雜網(wǎng)絡(luò)數(shù)據(jù)集進(jìn)行比較實(shí)驗(yàn)，結(jié)果表明，本文所提IGW-CNI 算法優(yōu)于其他影響力最大化算法，不僅效率更高，計(jì)算時(shí)間也短。

盡管本文已提出了上述具有重要意義的發(fā)現(xiàn)，但還具有一定局限性，其中一些可能會(huì)為未來的進(jìn)一步研究指明方向。首先，本文所提改進(jìn)灰狼優(yōu)化算法為基于種群的優(yōu)化算法，仍可能存在局部最小值，可考慮引入隨機(jī)梯度等方法避免出現(xiàn)局部最小值。其次，可結(jié)合社會(huì)化調(diào)查法和計(jì)算實(shí)驗(yàn)等研究框架對(duì)所提重要節(jié)點(diǎn)識(shí)別算法進(jìn)行進(jìn)一步佐證。最后，可嘗試使用如自編碼器等深度學(xué)習(xí)方法進(jìn)一步提升重要節(jié)點(diǎn)識(shí)別算法的效率和精度。