錢(qián)付蘭，徐 濤，趙 姝，張燕平

1.安徽大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，合肥 230601

2.安徽大學(xué) 信息保障技術(shù)研究中心，合肥 230601

1 引言

在線(xiàn)社交網(wǎng)絡(luò)的流行引起人們對(duì)信息傳播的極大關(guān)注。例如Facebook、Twitter、Microblog 和其他一些社交媒體。通過(guò)網(wǎng)絡(luò)中朋友之間的“口碑傳播”，一條信息很快就會(huì)傳播整個(gè)網(wǎng)絡(luò)。這種擴(kuò)散現(xiàn)象已被證明很有應(yīng)用前景，例如網(wǎng)絡(luò)競(jìng)選。2016 年美國(guó)總統(tǒng)競(jìng)選活動(dòng)，其中Twitter 幾乎每天都被用作拉票競(jìng)選工具。社會(huì)網(wǎng)絡(luò)的蓬勃發(fā)展，對(duì)其研究分析也顯得越來(lái)越重要。社會(huì)網(wǎng)絡(luò)研究有許多不同的研究方向，包括影響力最大化[1]、社團(tuán)發(fā)現(xiàn)[2]和鏈路預(yù)測(cè)[3]等方向。

影響力最大化問(wèn)題因其潛在商業(yè)價(jià)值而近來(lái)被廣泛研究。該問(wèn)題的形式化描述是在社會(huì)網(wǎng)絡(luò)中尋找K個(gè)初始種子節(jié)點(diǎn)，使其通過(guò)社會(huì)網(wǎng)絡(luò)關(guān)系的影響傳播最終所產(chǎn)生的影響力延展度最大。Domingos 和Richardson 將該營(yíng)銷(xiāo)問(wèn)題抽象定義成算法問(wèn)題去求解[4]。Kempe 等人[5]首次將影響力最大化問(wèn)題形式化為離散組合優(yōu)化問(wèn)題。他們證明該問(wèn)題在獨(dú)立級(jí)聯(lián)（independent cascade model，IC）和線(xiàn)性閾值（linear threshold model，LT）傳播模型下是一個(gè)NP 難優(yōu)化問(wèn)題，并提出爬山貪心算法。因?yàn)樵撍惴ㄐ枰獢?shù)萬(wàn)次蒙特卡洛（Monte Carlo，MC）模擬[6]，計(jì)算量非常巨大，不適用于大型復(fù)雜網(wǎng)絡(luò)。

因此，本文提出IC 傳播模型下有效的節(jié)點(diǎn)集影響力評(píng)估策略并且利用免疫遺傳算法[7]處理復(fù)雜組合優(yōu)化問(wèn)題的優(yōu)秀效果，提出基于免疫遺傳的影響力最大化算法（immune genetic algorithm based influence maximization，IGIM），本文主要貢獻(xiàn)如下：

（1）提出一種新穎有效的基于免疫遺傳影響力最大化算法，該算法可以快速在大型復(fù)雜網(wǎng)絡(luò)尋找到有影響力的種子節(jié)點(diǎn)。

（2）考慮到算法的運(yùn)行效率，提出局部概率解節(jié)點(diǎn)集影響力評(píng)價(jià)函數(shù)作為IGIM 算法的適應(yīng)值函數(shù)。

（3）為進(jìn)一步加速算法的收斂，本文設(shè)計(jì)基于局部概率解適應(yīng)值函數(shù)的啟發(fā)式策略，加速算法的進(jìn)化過(guò)程。

2 相關(guān)工作

近年來(lái)，很多研究者提出對(duì)影響力最大化問(wèn)題算法效率的改進(jìn)，可以分為兩大類(lèi)：（1）改進(jìn)的Monte Carlo貪心算法。Leskovec 等人[8]提出CELF（cost-effective lazy forward）算法，該算法主要思想是利用子模性質(zhì)來(lái)減少M(fèi)C 模擬次數(shù)，降低時(shí)間復(fù)雜度。CELF 算法比傳統(tǒng)貪心算法快大約700 倍。Wang 等人[9]提出貪婪算法與社會(huì)網(wǎng)絡(luò)社團(tuán)屬性相結(jié)合的CGA（community based greedy algorithm）算法。CGA 算法思想是將網(wǎng)絡(luò)劃分成多個(gè)社團(tuán)，從社團(tuán)中利用貪婪策略選擇種子節(jié)點(diǎn)降低模擬的復(fù)雜性。然而這些算法在大型復(fù)雜網(wǎng)絡(luò)，時(shí)間復(fù)雜度依然很高。（2）基于啟發(fā)式策略的影響力最大化算法。Chen 等人[10]基于度中心性提出DegreeDiscountIC 算法，該算法主要思想是當(dāng)一個(gè)節(jié)點(diǎn)被選為種子節(jié)點(diǎn)后，考慮到影響重疊，計(jì)算此節(jié)點(diǎn)的鄰居影響力時(shí)就要進(jìn)行度折扣計(jì)算。Liu等人基于PageRank 算法拓展提出Group-PageRank算法[11]，與僅能用于計(jì)算單個(gè)節(jié)點(diǎn)影響的傳統(tǒng)Page-Rank 算法不同，Group-PageRank 可以在幾乎恒定的時(shí)間內(nèi)估計(jì)任何節(jié)點(diǎn)集之間的影響強(qiáng)度。Jung等人[12]提出IRIE（influence ranking influence estimation）算法，該算法使用少量的迭代來(lái)生成節(jié)點(diǎn)的全局影響力排名并結(jié)合簡(jiǎn)單的影響估計(jì)不斷迭代調(diào)整種子節(jié)點(diǎn)集。這些算法忽略了擴(kuò)散模型的性質(zhì)，因此影響范圍與擴(kuò)散模型下的實(shí)際影響有明顯差距。在IC 模型下，Kimura等人[13]第一個(gè)提出最短路徑估計(jì)影響擴(kuò)散SPM（shortest-path model）模型。SPM 通過(guò)Dijkstra算法獲得從節(jié)點(diǎn)集S到任何節(jié)點(diǎn)v的最短路徑，從而得到種子集的擴(kuò)展，可以精確而有效地計(jì)算。同樣的，Chen 等人[14]提出MIA（maximum influence arborescence）模型，該模型思路是影響力只沿節(jié)點(diǎn)間最大影響路徑傳播，并將節(jié)點(diǎn)影響范圍局限在以節(jié)點(diǎn)為根的樹(shù)狀結(jié)構(gòu)中。最近，有些工作是基于網(wǎng)絡(luò)社區(qū)特征解決影響力最大化問(wèn)題。Shang 等人提出CoFIM（community-based framework for influence maximization）算法[15]，該算法分為兩個(gè)階段：種子擴(kuò)展和社區(qū)內(nèi)傳播?；趥鞑ミ^(guò)程，簡(jiǎn)化影響擴(kuò)散估計(jì)，采用貪婪算法來(lái)選擇種子節(jié)點(diǎn)。此外，許多工作利用智能優(yōu)化算法解決影響力最大化問(wèn)題。Jiang 等人[16]提出期望傳播值（expected diffusion value，EDV）來(lái)近似計(jì)算節(jié)點(diǎn)組合的影響范圍，并且提出基于模擬退火的影響力最大化算法SAEDV（simulated annealing expected diffusion value），從而可以更有效地解決影響力最大化問(wèn)題。Gong 等人[17]提出離散粒子群影響力最大化算法DPSO（discrete particle swarm optimization）。該算法使用粒子群算法并結(jié)合度最大啟發(fā)式策略和局部搜索方式加速算法收斂。Cui等人[18]使用度下降策略進(jìn)行節(jié)點(diǎn)選擇產(chǎn)生新節(jié)點(diǎn)集，并基于差分進(jìn)化算法提出度下降的差分進(jìn)化影響力最大化算法DDSE（degree-descending search evolution）。??m?ek 等人[19]提出聯(lián)合啟發(fā)式策略重塑網(wǎng)絡(luò)節(jié)點(diǎn)，以便群體智能優(yōu)化算法在其目標(biāo)函數(shù)狀態(tài)空間上獲得一般斜率，實(shí)驗(yàn)利用群體智能優(yōu)化算法獲得了很好的效果。除了以上的一些影響力最大化算法，Zhang 等人[20]提出采用精確概率解加策略計(jì)算影響力，并利用容斥定理證明精確概率解的計(jì)算，給出增量搜索策略來(lái)解決影響力最大化問(wèn)題，極大地提高了算法的運(yùn)行效率。以上方法在時(shí)間效率上和傳播精度上并不能得到一個(gè)很好的平衡，也有些策略不適用于大型網(wǎng)絡(luò)。

通過(guò)以上影響力最大化算法的研究與分析，現(xiàn)有算法并不能解決時(shí)間復(fù)雜度和傳播影響范圍之間的平衡問(wèn)題。受到Zhang 等人和Jiang 等人工作啟發(fā)，本文提出新穎的局部概率解影響力近似估計(jì)并采用免疫遺傳優(yōu)化算法尋找種子節(jié)點(diǎn)。

3 影響力最大化問(wèn)題

本章將會(huì)給出影響力最大化問(wèn)題形式化定義，并且介紹相關(guān)傳播模型和影響力近似計(jì)算。

3.1 基本定義

在影響力最大化研究中，社交網(wǎng)絡(luò)G=(V,E)，其中V代表社交網(wǎng)絡(luò)中的用戶(hù)，E是對(duì)用戶(hù)社交關(guān)系集合的建模。影響力最大化問(wèn)題是在社會(huì)網(wǎng)絡(luò)中找到一組大小為K的影響力最大的種子節(jié)點(diǎn)集S。σ(S)表示給定種子節(jié)點(diǎn)集S最終激活的期望節(jié)點(diǎn)數(shù)，即S的影響力。在特定傳播模型M下，任意種子節(jié)點(diǎn)集S*的影響力可以表示為σG,M(S*)。通過(guò)以上對(duì)影響力的定義，影響力最大化問(wèn)題形式化為：

3.2 傳播模型

本文使用的傳播模型為研究最為廣泛的獨(dú)立級(jí)聯(lián)模型。IC 模型是以離散過(guò)程擴(kuò)散，在此模型下用戶(hù)只有兩種狀態(tài)：激活和未激活。在時(shí)間步驟t=0，給定初始種子集S0，每一個(gè)激活用戶(hù)u∈St，將會(huì)以傳播概率p嘗試激活直接鄰居v（未激活）并且只有一次機(jī)會(huì)，如果激活失敗節(jié)點(diǎn)u將不會(huì)再影響節(jié)點(diǎn)v。在t+1 時(shí)刻，v∈St+1的概率為(1-p)l，l為節(jié)點(diǎn)v所有激活鄰居的數(shù)量。該過(guò)程持續(xù)到?jīng)]有新的用戶(hù)被激活為止。

3.3 影響力近似估計(jì)

Zhang 等人從傳播概率角度出發(fā)提出精確概率解加影響力估計(jì)策略，并證明該策略影響力計(jì)算遵循容斥定理（inclusion-exclusion，IE）。如圖1 所示，假設(shè)節(jié)點(diǎn)1 為種子節(jié)點(diǎn)，節(jié)點(diǎn)5 被影響的路徑有兩條，分別是P1→2→5和P1→3→5。根據(jù)容斥定理計(jì)算節(jié)點(diǎn)5 激活概率為：

因此得出節(jié)點(diǎn)1 的影響力評(píng)估為：

Fig.1 Small network圖1 小型網(wǎng)絡(luò)

在復(fù)雜大型網(wǎng)絡(luò)中，給定單個(gè)節(jié)點(diǎn)v所有入度鄰居{ui|ui→v} 和傳播概率pu,v，計(jì)算節(jié)點(diǎn)v的激活概率，可根據(jù)式（4）計(jì)算。Zhang 等人工作雖然極大地提高節(jié)點(diǎn)集影響力評(píng)估效率，但是該方法在全網(wǎng)絡(luò)進(jìn)行計(jì)算，仍然耗費(fèi)許多時(shí)間。為了高效評(píng)估節(jié)點(diǎn)集的影響力，本文提出局部容斥概率解適應(yīng)值函數(shù)，將會(huì)在4.2 節(jié)介紹。

其中，k表示節(jié)點(diǎn)v入度節(jié)點(diǎn)數(shù)量。

4 免疫遺傳影響力最大化算法

本章將詳細(xì)介紹本文提出的免疫遺傳影響力最大化算法。如圖2，算法主要利用免疫算法框架快速地迭代出網(wǎng)絡(luò)中最具有影響力的節(jié)點(diǎn)。對(duì)記憶庫(kù)采用啟發(fā)式策略加速算法的進(jìn)化。

Fig.2 Framework of IGIM algorithm圖2 免疫遺傳影響力最大化算法框架

4.1 編碼方式

在IGIM 算法中，群體中每一個(gè)抗體Xi采用實(shí)數(shù)值編碼?？贵wXi=(xi1,xi2,…,xiK)表示由K個(gè)節(jié)點(diǎn)組成一個(gè)集合，每一個(gè)抗體也代表著影響力最大化問(wèn)題的可行解。舉個(gè)例子，假設(shè)給定影響力節(jié)點(diǎn)集數(shù)目K=3，那么抗體Xi=(33,100,1)代表抗體由節(jié)點(diǎn)編號(hào)33、100 和1 的節(jié)點(diǎn)組成的集合，這里需要注意的是每一個(gè)抗體不能出現(xiàn)重復(fù)節(jié)點(diǎn)編號(hào)。

4.2 適應(yīng)值函數(shù)

受到Zhang 等人工作啟發(fā)，發(fā)現(xiàn)在計(jì)算節(jié)點(diǎn)集影響力概率，隨著階級(jí)增大而逐漸呈現(xiàn)收斂狀態(tài)。如圖1，根據(jù)容斥定理計(jì)算節(jié)點(diǎn)5 被激活概率為π5=0.064 7，評(píng)估節(jié)點(diǎn)1 的影響力可以忽略不計(jì)二階鄰居節(jié)點(diǎn)5 的激活概率，而只關(guān)注節(jié)點(diǎn)1 直接鄰居節(jié)點(diǎn)2、4 和3。因此在IC 傳播模型下，本文提出有效的局部容斥（local inclusion exclusion，LIE）概率解適應(yīng)值函數(shù)，通過(guò)計(jì)算節(jié)點(diǎn)集的一階鄰居節(jié)點(diǎn)的激活概率，近似估計(jì)節(jié)點(diǎn)集的影響力。給定一個(gè)網(wǎng)絡(luò)G=(V,E)和種子節(jié)點(diǎn)集S，每一個(gè)節(jié)點(diǎn)的激活概率πv，局部容斥概率解影響力評(píng)價(jià)函數(shù)LIE 可以定義為：

其中，v∈表示種子節(jié)點(diǎn)集的一階非激活鄰居節(jié)點(diǎn)，π表示激活概率向量，其元素是節(jié)點(diǎn)激活概率。適應(yīng)值函數(shù)偽代碼在算法1 中給出。

算法1局部容斥概率解LIE

4.3 抗體期望繁殖概率

在免疫遺傳算法中，引入抗體期望繁殖概率是為了鼓勵(lì)與抗原具有高親和力的抗體，并且對(duì)高濃度抗體進(jìn)行抑制。在本文中，與抗原的親和力函數(shù)采用適應(yīng)值函數(shù)。抗體濃度與抗體之間的相似度有關(guān)?？贵w之間相似度計(jì)算，采用R 位連續(xù)匹配算法。由于抗體編碼在影響力評(píng)估與編碼之間的順序無(wú)關(guān)，因此抗體之間相似度可表示為：

其中，li,j表示抗體i與抗體j相同的編碼個(gè)數(shù)；K表示抗體的長(zhǎng)度。因此抗體濃度ci即與抗體i相似的抗體所占群體的比例，可定義為：

其中，n為抗體的總數(shù)，，T為一個(gè)閾值。

抗體的期望繁殖概率是由抗體的適應(yīng)值和抗體濃度共同決定的，因此抗體的期望繁殖率可定義為：

通過(guò)免疫機(jī)制進(jìn)行個(gè)體選擇作為父本與群體中其他個(gè)體做兩點(diǎn)交叉操作，變異進(jìn)化出優(yōu)質(zhì)可行解并更新種群。

4.4 IGIM 算法

IGIM 算法基本思想是利用免疫機(jī)制融入傳統(tǒng)遺傳算法，并集成局部容斥概率解適應(yīng)值函數(shù)進(jìn)行優(yōu)化，尋找網(wǎng)絡(luò)中最具有影響力的節(jié)點(diǎn)集。如圖2，IGIM 算法主要包括抗體編碼初始化和進(jìn)化兩個(gè)階段。具體描述如算法2 所示。

算法2IGIM 算法

算法初始化階段（行3），為獲得較好的種群多樣性，對(duì)每個(gè)抗體采用隨機(jī)策略從記憶庫(kù)當(dāng)中選取K個(gè)節(jié)點(diǎn)進(jìn)行抗體編碼。算法進(jìn)化階段（行4～行16），采用傳統(tǒng)兩點(diǎn)交叉算子和變異算子。在兩種操作中，均使用記憶庫(kù)提供高質(zhì)量節(jié)點(diǎn)進(jìn)行抗體中元素替換，加速算法快速尋優(yōu)到最優(yōu)可行解。

根據(jù)算法2，對(duì)IGIM 算法進(jìn)行時(shí)間復(fù)雜度分析。在算法中需要對(duì)產(chǎn)生的新節(jié)點(diǎn)集進(jìn)行局部容斥概率解的影響力評(píng)估，根據(jù)算法1 得出影響力評(píng)估函數(shù)時(shí)間復(fù)雜度為。算法初始化階段（行1、行2）時(shí)間復(fù)雜度為。算法的迭代進(jìn)化階段（行4～行16）時(shí)間復(fù)雜度為O(n2KImax)+O(2nmKImax)+O(mnK2Imax)。因此算法IGIM 在最差情況下，時(shí)間復(fù)雜度為Imax)。其中n表示種群的大小，K為種子節(jié)點(diǎn)集的數(shù)量，Imax表示算法的迭代進(jìn)化次數(shù)，表示為網(wǎng)絡(luò)節(jié)點(diǎn)的平均度。

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

為驗(yàn)證提出的IGIM 算法性能，本文選取4 個(gè)真實(shí)的數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)結(jié)果對(duì)比和分析，并驗(yàn)證所提出局部容斥概率解影響力評(píng)估性能。下面是對(duì)實(shí)驗(yàn)的詳細(xì)設(shè)置。

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

本文選擇4 個(gè)真實(shí)學(xué)術(shù)合作網(wǎng)絡(luò)數(shù)據(jù)集Net-Science[21]、NetGRQC[22]、NetHEPT 和NetPHY[10]。這4個(gè)數(shù)據(jù)集描述的是不同領(lǐng)域科學(xué)家之間科研合作網(wǎng)絡(luò)，節(jié)點(diǎn)表示科研人員，邊表示科研合作人員之間的學(xué)術(shù)成果或出版刊物，均為無(wú)向圖。4 個(gè)數(shù)據(jù)集的詳細(xì)信息如表1 所示。

Table 1 4 real-world social networks表1 4 個(gè)真實(shí)社會(huì)網(wǎng)絡(luò)

5.2 對(duì)比算法與實(shí)驗(yàn)設(shè)置

在對(duì)比實(shí)驗(yàn)中，選擇CELF、SAEDV、DPSO、DDSE和Random 共5 個(gè)算法進(jìn)行對(duì)比。其中CELF 算法是基于子模性質(zhì)對(duì)貪心算法的改進(jìn)，在傳播影響范圍上與貪心算法的性能一致。SAEDV、DPSO 和DDSE算法都采用智能優(yōu)化算法解決影響力最大化問(wèn)題，在時(shí)間效率上都是非常先進(jìn)的算法。Random 算法是基線(xiàn)對(duì)比算法。

本文是在IC模型下運(yùn)行10 000次Monte-Carlo模擬評(píng)估每個(gè)算法的種子節(jié)點(diǎn)集影響擴(kuò)展。除CELF算法以外，其他所有算法均獨(dú)立運(yùn)行30 次取平均結(jié)果。SAEDV 算法參數(shù)設(shè)定：初始溫度T0=500 000，最終溫度Tf=8 000，內(nèi)循環(huán)q=200，溫度下降梯度ΔT=2 000。IGIM 算法實(shí)驗(yàn)參數(shù)是根據(jù)實(shí)驗(yàn)優(yōu)化所得，如表2 所示。其他對(duì)比算法實(shí)驗(yàn)參數(shù)均使用各自論文中實(shí)驗(yàn)參數(shù)。

為了方便實(shí)驗(yàn)分析，傳播概率p設(shè)置為0.01，與先前的研究一致[19]。所有算法都使用Java 語(yǔ)言編寫(xiě)。所有實(shí)驗(yàn)均在2.3 GHz Intel Core i5 和16.0 GB內(nèi)存的PC 上運(yùn)行。

Table 2 Parameters in IGIM algorithm表2 IGIM 算法參數(shù)

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

評(píng)價(jià)影響力最大化算法通常使用影響傳播范圍和運(yùn)行時(shí)間這兩個(gè)常規(guī)指標(biāo)。傳播影響范圍為影響力最大化算法尋找到的種子節(jié)點(diǎn)集在特定傳播模型下的影響節(jié)點(diǎn)數(shù)目；運(yùn)行時(shí)間即算法尋找到種子節(jié)點(diǎn)集所花費(fèi)的時(shí)間。

5.3.1 影響力評(píng)估函數(shù)對(duì)比

本文提出了局部容斥概率解影響力評(píng)估函數(shù)，為了驗(yàn)證該函數(shù)的性能，取IGIM 算法在4 個(gè)數(shù)據(jù)集上分別尋找到的30 個(gè)種子節(jié)點(diǎn)，使用局部容斥LIE、容斥IE 和蒙特卡洛MC 模擬分別計(jì)算種子節(jié)點(diǎn)集影響力估計(jì)和運(yùn)行時(shí)間。

如圖3（a）實(shí)驗(yàn)結(jié)果，在4 個(gè)數(shù)據(jù)集上，局部容斥概率解非常逼近MC 模擬的性能。在NetPHY 數(shù)據(jù)集上，LIE 的評(píng)估性能稍遜于MC 模擬，這可解釋為在大型的復(fù)雜網(wǎng)絡(luò)上，局部的影響力估計(jì)會(huì)丟失一部分傳播信息。如圖3（b）實(shí)驗(yàn)結(jié)果，在大數(shù)據(jù)集NetPHY上LIE 運(yùn)行時(shí)間比其他兩種方法快大約3 個(gè)數(shù)量級(jí)。因此，本文所提出的局部容斥概率解影響力評(píng)價(jià)函數(shù)能夠高效準(zhǔn)確地對(duì)節(jié)點(diǎn)集影響力作出近似估計(jì)。

5.3.2 傳播影響范圍對(duì)比

圖4 實(shí)驗(yàn)結(jié)果顯示6 個(gè)算法在不同種子節(jié)點(diǎn)集大小、4個(gè)數(shù)據(jù)集上影響傳播范圍的變化情況。根據(jù)圖4實(shí)驗(yàn)結(jié)果得知，IGIM 算法和CELF 算法在4 個(gè)數(shù)據(jù)集上具有極其相近的性能，超過(guò)其他對(duì)比算法。其中，SAEDV 僅次于本文算法IGIM。數(shù)據(jù)集NetScience和NetHEPT 相對(duì)于其他兩個(gè)數(shù)據(jù)集較為稀疏，因此在傳播范圍上，CELF、IGIM、SAEDV 和DDSE 之間的性能差距不是很大。

Fig.3 Comparison of performance of influence evaluation functions on 4 datasets圖3 影響力評(píng)估函數(shù)在4 個(gè)數(shù)據(jù)集上的性能對(duì)比

在種子集大小K=30 的情況下，IGIM在NetGRQC數(shù)據(jù)集上傳播精度分別優(yōu)于SAEDV、DDSE 和DPSO算法2.18%、4.13%和11.09%，在NetPHY 數(shù)據(jù)集中分別是1.5%、7.87%和9.92%。DPSO 在4 個(gè)數(shù)據(jù)集上表現(xiàn)僅次于DDSE 算法，尤其在NetPHY 數(shù)據(jù)集上，隨著K值不斷增大，DPSO 和DDSE 算法的性能在不斷下降?？梢苑治龅贸?，在大型復(fù)雜網(wǎng)絡(luò)上度中心性啟發(fā)式策略存在一定的局限性，僅有節(jié)點(diǎn)的局部拓?fù)浣Y(jié)構(gòu)信息。Random 算法隨機(jī)組合網(wǎng)絡(luò)中的節(jié)點(diǎn)，在4 個(gè)數(shù)據(jù)集上表現(xiàn)是最差的。

5.3.3 運(yùn)行時(shí)間對(duì)比

為驗(yàn)證IGIM 算法的時(shí)間效率，圖5給出種子節(jié)點(diǎn)集大小為30的各個(gè)算法運(yùn)行時(shí)間。在4個(gè)數(shù)據(jù)集上，IGIM 算法時(shí)間效率優(yōu)于DDSE、DPSO 和SAEDV 算法。在數(shù)據(jù)集NetPHY 上，IGIM 算法比DDSE、DPSO和SAEDV 算法快大約20.38%、74.62%和79.71%。SAEDV 算法因?yàn)橐f(wàn)次的迭代進(jìn)化，因此運(yùn)行時(shí)間要差于利用啟發(fā)式策略加速的DDSE 和DPSO 算法。DPSO 和DDSE 算法分別使用了度中心性和度下降啟發(fā)式策略，但是收斂速度要次于算法IGIM。

Fig.4 Influence spread on 4 datasets under independent cascade model圖4 獨(dú)立級(jí)聯(lián)模型下4 個(gè)數(shù)據(jù)集上的傳播影響范圍

Fig.5 Comparisons of running time of different algorithms圖5 不同算法之間運(yùn)行時(shí)間對(duì)比

在4 個(gè)數(shù)據(jù)集上，CELF 算法運(yùn)行需要通過(guò)MC模擬尋找到最具有邊際影響力的節(jié)點(diǎn)，時(shí)間開(kāi)銷(xiāo)很大，因此效果最差。Random 算法隨機(jī)組合生成種子節(jié)點(diǎn)集，時(shí)間效率雖然是最好的，但在傳播影響力范圍上的性能是最差的。

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

本文提出局部容斥概率解評(píng)價(jià)函數(shù)，可以有效快速地估計(jì)節(jié)點(diǎn)集的近似影響擴(kuò)散。在IGIM 算法中，采用LIE 函數(shù)進(jìn)行單個(gè)節(jié)點(diǎn)影響力計(jì)算并選擇優(yōu)秀節(jié)點(diǎn)構(gòu)造記憶庫(kù)，用來(lái)加速算法進(jìn)化過(guò)程。在傳播影響范圍和運(yùn)行時(shí)間兩個(gè)指標(biāo)上，算法在4 個(gè)真實(shí)數(shù)據(jù)集上對(duì)比實(shí)驗(yàn)數(shù)據(jù)表明，IGIM 算法都有優(yōu)秀的表現(xiàn)，在傳播范圍和時(shí)間復(fù)雜度取得良好的平衡。在未來(lái)工作中，將繼續(xù)探究IGIM 算法在結(jié)合文本語(yǔ)意信息的傳播模型上的應(yīng)用。