基于局部概率解的免疫遺傳影響力最大化算法*

錢付蘭，徐 濤，趙 姝，張燕平

1.安徽大學 計算機科學與技術學院，合肥 230601

2.安徽大學 信息保障技術研究中心，合肥 230601

1 引言

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

影響力最大化問題因其潛在商業價值而近來被廣泛研究。該問題的形式化描述是在社會網絡中尋找K個初始種子節點，使其通過社會網絡關系的影響傳播最終所產生的影響力延展度最大。Domingos 和Richardson 將該營銷問題抽象定義成算法問題去求解[4]。Kempe 等人[5]首次將影響力最大化問題形式化為離散組合優化問題。他們證明該問題在獨立級聯（independent cascade model，IC）和線性閾值（linear threshold model，LT）傳播模型下是一個NP 難優化問題，并提出爬山貪心算法。因為該算法需要數萬次蒙特卡洛（Monte Carlo，MC）模擬[6]，計算量非常巨大，不適用于大型復雜網絡。

因此，本文提出IC 傳播模型下有效的節點集影響力評估策略并且利用免疫遺傳算法[7]處理復雜組合優化問題的優秀效果，提出基于免疫遺傳的影響力最大化算法（immune genetic algorithm based influence maximization，IGIM），本文主要貢獻如下：

（1）提出一種新穎有效的基于免疫遺傳影響力最大化算法，該算法可以快速在大型復雜網絡尋找到有影響力的種子節點。

（2）考慮到算法的運行效率，提出局部概率解節點集影響力評價函數作為IGIM 算法的適應值函數。

（3）為進一步加速算法的收斂，本文設計基于局部概率解適應值函數的啟發式策略，加速算法的進化過程。

2 相關工作

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

通過以上影響力最大化算法的研究與分析，現有算法并不能解決時間復雜度和傳播影響范圍之間的平衡問題。受到Zhang 等人和Jiang 等人工作啟發，本文提出新穎的局部概率解影響力近似估計并采用免疫遺傳優化算法尋找種子節點。

3 影響力最大化問題

本章將會給出影響力最大化問題形式化定義，并且介紹相關傳播模型和影響力近似計算。

3.1 基本定義

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

3.2 傳播模型

本文使用的傳播模型為研究最為廣泛的獨立級聯模型。IC 模型是以離散過程擴散，在此模型下用戶只有兩種狀態：激活和未激活。在時間步驟t=0，給定初始種子集S0，每一個激活用戶u∈St，將會以傳播概率p嘗試激活直接鄰居v（未激活）并且只有一次機會，如果激活失敗節點u將不會再影響節點v。在t+1 時刻，v∈St+1的概率為(1-p)l，l為節點v所有激活鄰居的數量。該過程持續到沒有新的用戶被激活為止。

3.3 影響力近似估計

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

因此得出節點1 的影響力評估為：

Fig.1 Small network圖1 小型網絡

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

其中，k表示節點v入度節點數量。

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

本章將詳細介紹本文提出的免疫遺傳影響力最大化算法。如圖2，算法主要利用免疫算法框架快速地迭代出網絡中最具有影響力的節點。對記憶庫采用啟發式策略加速算法的進化。

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

4.1 編碼方式

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

4.2 適應值函數

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

其中，v∈表示種子節點集的一階非激活鄰居節點，π表示激活概率向量，其元素是節點激活概率。適應值函數偽代碼在算法1 中給出。

算法1局部容斥概率解LIE

4.3 抗體期望繁殖概率

在免疫遺傳算法中，引入抗體期望繁殖概率是為了鼓勵與抗原具有高親和力的抗體，并且對高濃度抗體進行抑制。在本文中，與抗原的親和力函數采用適應值函數。抗體濃度與抗體之間的相似度有關。抗體之間相似度計算，采用R 位連續匹配算法。由于抗體編碼在影響力評估與編碼之間的順序無關，因此抗體之間相似度可表示為：

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

其中，n為抗體的總數，，T為一個閾值。

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

通過免疫機制進行個體選擇作為父本與群體中其他個體做兩點交叉操作，變異進化出優質可行解并更新種群。

4.4 IGIM 算法

IGIM 算法基本思想是利用免疫機制融入傳統遺傳算法，并集成局部容斥概率解適應值函數進行優化，尋找網絡中最具有影響力的節點集。如圖2，IGIM 算法主要包括抗體編碼初始化和進化兩個階段。具體描述如算法2 所示。

算法2IGIM 算法

算法初始化階段（行3），為獲得較好的種群多樣性，對每個抗體采用隨機策略從記憶庫當中選取K個節點進行抗體編碼。算法進化階段（行4～行16），采用傳統兩點交叉算子和變異算子。在兩種操作中，均使用記憶庫提供高質量節點進行抗體中元素替換，加速算法快速尋優到最優可行解。

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

5 實驗與結果

為驗證提出的IGIM 算法性能，本文選取4 個真實的數據集進行實驗結果對比和分析，并驗證所提出局部容斥概率解影響力評估性能。下面是對實驗的詳細設置。

5.1 數據集

本文選擇4 個真實學術合作網絡數據集Net-Science[21]、NetGRQC[22]、NetHEPT 和NetPHY[10]。這4個數據集描述的是不同領域科學家之間科研合作網絡，節點表示科研人員，邊表示科研合作人員之間的學術成果或出版刊物，均為無向圖。4 個數據集的詳細信息如表1 所示。

Table 1 4 real-world social networks表1 4 個真實社會網絡

5.2 對比算法與實驗設置

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

本文是在IC模型下運行10 000次Monte-Carlo模擬評估每個算法的種子節點集影響擴展。除CELF算法以外，其他所有算法均獨立運行30 次取平均結果。SAEDV 算法參數設定：初始溫度T0=500 000，最終溫度Tf=8 000，內循環q=200，溫度下降梯度ΔT=2 000。IGIM 算法實驗參數是根據實驗優化所得，如表2 所示。其他對比算法實驗參數均使用各自論文中實驗參數。

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

Table 2 Parameters in IGIM algorithm表2 IGIM 算法參數

5.3 實驗結果與分析

評價影響力最大化算法通常使用影響傳播范圍和運行時間這兩個常規指標。傳播影響范圍為影響力最大化算法尋找到的種子節點集在特定傳播模型下的影響節點數目；運行時間即算法尋找到種子節點集所花費的時間。

5.3.1 影響力評估函數對比

本文提出了局部容斥概率解影響力評估函數，為了驗證該函數的性能，取IGIM 算法在4 個數據集上分別尋找到的30 個種子節點，使用局部容斥LIE、容斥IE 和蒙特卡洛MC 模擬分別計算種子節點集影響力估計和運行時間。

如圖3（a）實驗結果，在4 個數據集上，局部容斥概率解非常逼近MC 模擬的性能。在NetPHY 數據集上，LIE 的評估性能稍遜于MC 模擬，這可解釋為在大型的復雜網絡上，局部的影響力估計會丟失一部分傳播信息。如圖3（b）實驗結果，在大數據集NetPHY上LIE 運行時間比其他兩種方法快大約3 個數量級。因此，本文所提出的局部容斥概率解影響力評價函數能夠高效準確地對節點集影響力作出近似估計。

5.3.2 傳播影響范圍對比

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

Fig.3 Comparison of performance of influence evaluation functions on 4 datasets圖3 影響力評估函數在4 個數據集上的性能對比

在種子集大小K=30 的情況下，IGIM在NetGRQC數據集上傳播精度分別優于SAEDV、DDSE 和DPSO算法2.18%、4.13%和11.09%，在NetPHY 數據集中分別是1.5%、7.87%和9.92%。DPSO 在4 個數據集上表現僅次于DDSE 算法，尤其在NetPHY 數據集上，隨著K值不斷增大，DPSO 和DDSE 算法的性能在不斷下降。可以分析得出，在大型復雜網絡上度中心性啟發式策略存在一定的局限性，僅有節點的局部拓撲結構信息。Random 算法隨機組合網絡中的節點，在4 個數據集上表現是最差的。

5.3.3 運行時間對比

為驗證IGIM 算法的時間效率，圖5給出種子節點集大小為30的各個算法運行時間。在4個數據集上，IGIM 算法時間效率優于DDSE、DPSO 和SAEDV 算法。在數據集NetPHY 上，IGIM 算法比DDSE、DPSO和SAEDV 算法快大約20.38%、74.62%和79.71%。SAEDV 算法因為要萬次的迭代進化，因此運行時間要差于利用啟發式策略加速的DDSE 和DPSO 算法。DPSO 和DDSE 算法分別使用了度中心性和度下降啟發式策略，但是收斂速度要次于算法IGIM。

Fig.4 Influence spread on 4 datasets under independent cascade model圖4 獨立級聯模型下4 個數據集上的傳播影響范圍

Fig.5 Comparisons of running time of different algorithms圖5 不同算法之間運行時間對比

在4 個數據集上，CELF 算法運行需要通過MC模擬尋找到最具有邊際影響力的節點，時間開銷很大，因此效果最差。Random 算法隨機組合生成種子節點集，時間效率雖然是最好的，但在傳播影響力范圍上的性能是最差的。

6 結束語

本文提出局部容斥概率解評價函數，可以有效快速地估計節點集的近似影響擴散。在IGIM 算法中，采用LIE 函數進行單個節點影響力計算并選擇優秀節點構造記憶庫，用來加速算法進化過程。在傳播影響范圍和運行時間兩個指標上，算法在4 個真實數據集上對比實驗數據表明，IGIM 算法都有優秀的表現，在傳播范圍和時間復雜度取得良好的平衡。在未來工作中，將繼續探究IGIM 算法在結合文本語意信息的傳播模型上的應用。