基于自適應混沌遺傳算法的影響力最大化研究

張 萌，李維華

(云南大學 信息學院，云南 昆明 650500)

隨著Facebook、Instagram和微博的不斷發展，社交網絡逐漸成為信息傳播、商業宣傳的絕佳平臺，一些研究者通過用戶的行為模式進行數據分析，挖掘社交網絡作為信息擴散平臺的潛力. 影響力最大化問題作為社交數據分析下的新興領域，利用最少的資源獲得最大影響，在病毒營銷、信息擴散、輿論監測和醫療保健中發揮著重要作用.

社交網絡影響最大化問題是如何選取K個初始節點進行傳播，從而最大程度地影響整個網絡的問題[1]. 2002年，Richardson等[2]首先提出影響力最大化問題并將其定義為一個算法問題. 隨后Kempe等[3]證明了在特定傳播模型下的影響力最大化問題是NP難問題，利用離散優化思想發現K個影響增益最大的節點使得最終的影響范圍最大，并提出貪心爬山近似算法. 針對傳統貪心算法耗時過多的缺點，Leskovec等[4]利用函數的子模性，提出了CELF(Cost-Effctive Lazy Forward)優化算法, 大大提高時間效率的同時也達到了和傳統貪心算法一樣的影響范圍. Ding等[5]引入一個現實獨立級聯模型(Realistic Independent Cascade，RIC)，基于該模型提出了3種新的傳播算法R-greedy，Mgreedy和D-greedy. 這些改進的貪心算法可以在簡單網絡上顯示出良好的性能，但每次迭代都需要進行上萬次的蒙特卡洛（Monte Carlo，MC）模擬才能得到近似解，在中大規模的復雜網絡中計算量很大. 為了降低影響最大化問題的時間開銷，高效的智能算法為解決影響力最大化的問題開辟了新方向. Jiang等[6]提出了一種預期擴散值度量(Expect Diffusion Value，EDV)近似估計潛在節點的影響力，結合模擬退火算法(Simulated Annealing，SA)可識別有影響力的節點. 該算法比貪心算法在時間花費上節約了近3個數量級. Cui等[7]提出了一種節點度遞減搜索策略并基于差分進化與遺傳算法提出影響力最大化算法(Degree-Descending Search Evolution，DDSE). 錢付蘭等[8]利用免疫選擇優化遺傳算法，再根據局部概率解評估影響力. 實驗表明遺傳算法在影響力最大化的求解中比模擬退火算法在性能和時間上更具有優越性. Gong等[9]等將改進的粒子群算法與二跳局部影響估計器相結合提出DPSO (Discrete Paticle Swarm Optimization)算法. Liu等[10]通過搜索空間劃分機制來增強搜索，提出了基于模擬退火的高效算法SASP(Simulated Annealing with Search Partition). Sankar等[11]通過探索蜂群的搖擺舞行為，提出了一種用于最大化影響力的蜂算法，并在Twitter數據集上驗證了該算法的性能. 此外，Zhang等[12]根據信息傳播的概率性，提出精確概率解影響力估計，利用增量式搜索解決影響力最大化問題. 以上方法雖然大大提高了算法的運行效率，但除了SASP算法，其余算法只是在簡單網絡中驗證了算法性能，沒有運用到中大型網絡中，而且一些智能算法存在參數設置困難，使得節點影響估計不足導致算法性能明顯下降. 如何能在合理的時間消耗內很好地平衡求解精度，使得算法在不同規模的網絡中仍然能保持穩定搜索，是影響力最大化問題面臨的一個挑戰.

本文采用一階容斥激活集（the First-order Inclusion-Exclusion Activation set，FIEA）作為適應度函數評估節點集的預期影響，利用Logistic混沌序列的均勻搜索能力和自適應變異穩定而高效的局部尋優特點，提出一種自適應混沌遺傳算法（Self-Adapting Chaos Genetic Algorithm，SACGA）迭代出最優種子集，然后再將該種子集經過特定的模型傳播后得到最終的影響范圍.

1 影響力最大化問題

1.1 問題定義在求解影響力最大化問題時一般將網絡定義為圖G=(V,E)，其中V代表節點，E代表邊即節點間的聯系. 從網絡中選出K(1≤K≤|V|)個不重復節點組合成一個種子集S，讓S在特定的模型下進行影響傳播，得到的影響擴散范圍δ(S)要達到最大，S*為最佳種子集. 影響力最大化問題的形式化定義為

1.2 影響力傳播模型在影響力最大化問題中，影響傳播模型通常使用獨立級聯（Independent Cascade，IC）模型和線性閾值（Linear Threshold，LT）模型. 這里詳細介紹本文使用的IC模型.

IC模型是一種概率模型，當節點a被激活后，以一定概率去嘗試激活它的鄰居節點b，并且a對b的激活過程獨立，不受任何節點影響. 該模型的傳播過程如下：

（1）在某個時刻給定一個種子集S（S中的節點均為活躍狀態，S以外的節點均為非活躍狀態），在該時刻節點a被激活后，它就獲得了一次以概率P去激活節點b的機會.

（2）若節點b有多個鄰居均處于活躍狀態，這些鄰居會以任意順序去嘗試激活節點b. 如果節點b被成功激活，那么在下一時刻，節點b的狀態變為活躍，可以去激活其他未被激活的節點.

（3）重復過程（1）和（2），直到網絡中沒有可以激活的節點. 當整個過程結束時，得到的是網絡中被激活的節點數.

1.3 預期影響評估Zhang等[12]基于IC模型，從概率角度出發提出精確概率解評估節點影響，同時證明了該方法遵循容斥原理（Principle of Inclusion-Exclusion, IE）. 利用容斥原理能夠在較少的時間成本內在網絡中找到具有影響潛力的種子集. 在復雜網絡中，給定一個節點v所有處于活躍狀態的入度鄰居節點Iv={w1,w2,...,wk} 和邊概率Pwkv，利用容斥原理計算節點v的被激活概率為

簡化后可得

其中 ，k為v的活躍入度鄰居數，Rv(0≤Rv≤1) 是為v的被激活概率，表示節點v被激活的程度.

具體實例如圖1所示，有一個種子集S={2,3},種子集中節點均為活躍狀態，其余節點均不活躍.節點4有兩個活躍入度鄰居，由式（3）計算可得節點4的被激活概率

圖1 一個小型網絡Fig. 1 A simple network

2 自適應混沌遺傳算法

利用遺傳算法求解影響力最大化問題的可行性已被驗證[13-14]. 遺傳算法擅長在全局范圍內搜索，使得算法不陷入局部最優且收斂快. 但遺傳算法的局部搜索能力差，特別是進化后期搜索能力的降低容易導致早熟收斂. 針對這些不足，提出一種自適應混沌遺傳算法.

2.1 編碼方式選擇實數編碼方式. 任意一個種子集S={s1,s2,···,sK}表示由K個不重復節點組成的集合，S中的每個元素表示網絡中的節點編號，每個編號都是唯一的.

2.2 適應度函數適應度函數在遺傳算法中表示個體適應環境的能力，可以用此衡量種群中個體的優劣. 適應度高的個體有更大的概率在種群中生存下去，而適應度低的個體則會在進化過程中被逐漸淘汰. 在提出的算法中，適應度用于在迭代過程中評估種子集的預期影響. 在Zhang等[12]研究工作的啟發下，給定G=(V,E) 和任意種子集S，S中的節點均為活躍狀態，某個節點的被激活概率為Rv，利用容斥激活集（Inclusion-Exclusion Activation set，IEA）可計算種子集的預期影響

其中，M表示在集合中而不在S的節點，表示S中節點的n階鄰域內的所有非激活鄰居節點. 當n取值為 ∞ 時，得到的是種子集S的全局網絡預期影響評估，但根據影響力的傳播動力學研究顯示，由于影響衰減，最近鄰域范圍內的影響評估往往是最可靠的[15]. 因此，本文采用FIEA作為適應度函數評估種子集的預期影響

2.3 產生初始種群實際上在真實的網絡中存在大量影響力極低的節點，這些節點并不能作為影響候選節點. 為了提高搜索效率，首先將單個節點看作一個種子集，利用適應度函數計算圖G中每個節點的預期影響σ1(vi)，并將這些節點按預期影響的大小進行降序排列 σ1(v1)＞σ1(v2)＞···＞σ1(v|V|)，從前L個節點中隨機產生初始種群，同時選擇前K個節點構造關鍵節點集Q.

2.4 混沌順序交叉混沌的基本思想是根據一定規則讓未知變量從原有混沌空間變換到求解空間，利用混沌本身的隨機性、遍歷性和規律性等特點對解空間進行混沌搜索，從而求得全局最優解[16].由一個確定性方程得到，但具有隨機性的活動狀態稱為混沌. 當前的混沌優化大多采用Logistic映射混沌序列，定義如下：

其中，μ 為控制參數，當μ∈(3.5 699 456,4] 時系統進入混沌狀態；當μ=4 時，Logistic映射為滿映射，整個系統處于完全混沌狀態，生成的混沌序列具有良好的隨機性. 因此在本文中 μ 的取值為4，初始xm為0到1之間的隨機數.

采用混沌順序交叉，既能均勻地增加種群的多樣性，也避免了個體基因位上的沖突. 選擇種群內的個體進行配對，兩兩組成父代，然后具體交叉過程如圖2所示.

步驟1從種群中依次選取父代個體X1和X2，隨機產生混沌初始值，利用式（8）產生一個混沌值，把該混沌值作為混沌序列的初值生成另一個混沌值，再將這兩個混沌值分別與K-2 相乘得到兩個正整數g和h(0≤g≤h≤K-1) 作為父代截取基因的起始位置和終止位置，截取出的基因稱作交叉基因段.

步驟2生成一對個體X1′和X2′，并保證個體中被選中的基因位置與父代X1和X2的相同.

步驟3找出父代X1中與X2′交叉基因段中不相同的基因，按順序放入X2′的空位中，生成新子代Y1.X2與X1′重復同樣的操作得到另一個新子代Y2，交叉過程結束.

2.5 自適應混沌變異自適應混沌變異的思想是指當種群中個體的適應度差距逐漸縮小并趨于收斂時，需要增大變異概率以破壞當前種群的穩定性. 在變異時，同樣利用式（8）迭代生成兩個混沌值xm+1和xm+2，再與K-2相乘得到兩個正整數a和b(1≤a≤b≤K)，表示個體基因位. 從關鍵節點集Q中隨機選取一個節點替換基因位上的基因，生成新的子代，跳出當前最優，避免算法早熟. 而當種群中個體的適應度差距較大時，應降低變異概率，使算法趨于收斂.{S1,S2,···,SN} 表示一個種群，N為種群大小，S j表示種群中當前待獲取變異概率的個體，該個體變異概率為

圖2 順序交叉過程Fig. 2 The process of sequential crossover

算法1描述計算節點集的預期影響函數σ1(S)

輸入：G=(V,E)，邊概率P，種子集S.

輸出：種子集S的預期影響.

步驟1種子集中節點的激活概率初始化為1，網絡中其余節點的激活概率初始化為0.

步驟2找出種子集S中節點的n個一階鄰居節點.

步驟3利用式（3）計算得到每個鄰居節點的激活概率.

步驟4由式（7）得到種子集S的預期影響.

算法2描述自適應混沌遺傳算法SACGA

輸入：G=(V,E)，邊概率P，種群大小N，種子集大小K，交叉概率 γ，迭代次數Imax.

輸出：最佳種子集Sbest.

步驟1利用適應度函數 σ1計算G中所有節點的影響分數. 從前L個節點中隨機生成N個大小為K的個體組成初始種群S={S1,S2,···,SN}，同時選取前K個節點構造關鍵節點集Q.

步驟2從初始種群中選出初始最優解Sbest.

步驟3開始進行種群迭代.

步驟4依次從當前種群中選取兩個個體作為父代. 如果當前父代的 γ 滿足交叉條件就隨機產生混沌初始值xm，由式（8）計算得到兩個混沌隨機數xm+1和xm+2，將兩個隨機數分別與（K-2）相乘得到g和h，根據g、h進行基因位順序交叉. 如果不滿足交叉條件，則直接進入新種群.

步驟5得到交叉后的新種群N′.

步驟6在新種群N′中的個體j. 根據式（9）產生變異概率 λ，如果 λ 滿足變異條件，隨機產生初始混沌值xm，由式（8）迭代生成xm+1和xm+2，將兩個隨機數分別與（K-2）相乘得到a和b. 從Q中隨機選擇節點與a和b上的基因進行交換，如果λ不滿足變異條件，則進入下一階段.

步驟7如果 σ1(S j)＞σ1(Sbest)Sbest=S j.

步驟8得到變異后的種群.

步驟9更新種群，如果迭代次數小于Imax，跳至步驟3，否則跳至下一階段.

步驟10迭代完成后輸出最佳種子集Sbest.

D(-)為節點平均度，Imax為最大迭代次數，K為種子集大小. 算法1的時間復雜度為O(nKD(-)).算法2產生初始種群的時間復雜度為O(nKD(-))+O(NnKD(-))，迭代過程的時間復雜度為2O(NKImax)+O(NImax)+O(NnKD(-)Imax). 因此，最壞情況下SACGA算法的時間復雜度為O(NnKD(-)Imax).

3 實驗與結果分析

本文利用4個真實的網絡數據集（數據來源：http://snap.stanford.edu/data）進行實驗結果的對比和分析，驗證所提一階容斥激活集FIEA和自適應混沌遺傳算法SACGA的有效性.

3.1 數據集網絡數據集如表1所示.

表1 社交網絡數據集Tab. 1 The data sets of social network

3.2 對比算法與實驗設置為了驗證SACGA的有效性，本文選取4個具有代表性的算法與SACGA進行對比，邊概率P統一設置為0.01. 其中SAEDV算法的參數為初始溫度Ti=500 000，結束溫度Tf=100 000， 降溫系數 ΔT=2 000 和外循環q=10；DDSE算法參數為種群大小N=10，種群多樣性d=0.6 ，交叉概率 γ=0.4 ，變異概率 λ=0.1，迭代次數為200次；GA算法的參數設置為種群大小N=10， 交叉概率 γ=0.4 ，變異概率 λ=0.1，迭代次數180次；SACGA-N是在SACGA下利用n=∞ 時的IEA函數尋找種子集的算法，其參數設置與SACGA相同. 上述算法的結果均由運行10次的平均結果得出. 所有代碼使用Python3編寫，實驗在Windows（Intel Corei5.2.3 GHz,8 GB內存）下進行.

關鍵節點集Q的設置使得算法能夠跳出當前最優，以便尋得更優秀的個體，從而加速算法收斂.如圖3所示，在4個數據集中，當Q取值為K時，影響范圍達到最大，隨著Q取值不斷增大，影響范圍呈下降趨勢，在FaceBook和E-mail數據集上尤為明顯. 因此，本文關鍵節點集Q的取值為K. 此外，為了提高時間效率，將種群大小設置為10，SACGA算法的具體參數設置如表2所示.

圖3 關鍵節點集 Q 取值與影響范圍的變化Fig. 3 The variations of influence spread with differet values of Q

表2 SACGA算法參數設置Tab. 2 The parameter setting of SACGA

3.3 實驗結果與分析評價影響力最大化算法的性能通常使用影響傳播范圍和運行時間這兩個常規指標. 影響傳播范圍指利用影響力最大化算法尋找到的種子集在特定傳播模型下的影響范圍大??；運行時間即算法尋找到最優種子集所花費的時間.

3.3.1 預期影響評估方法對比 本文利用FIEA評估種子集的預期影響以便選出最優種子集. 為了驗證該方法的有效性，選取K為50的種子集在FIEA和IEA上進行影響范圍和運行時間的對比. 如表3所示，除了在FaceBook數據集上利用IEA進行評估選出的種子集在影響范圍上比FIEA多了0.34%，在其它3個數據集上，利用FIEA評估出的種子集產生的影響范圍均比IEA分別擴大了0.24%、0.069%和7.22%. 說明利用FIEA評估種子集的預期影響是一種可靠的方法. 同時本文給出了利用FIEA和IEA計算一個種子集預期影響的運行時間對比，如表4所示，在4個數據集上FIEA只需要不到1 s的時間就能計算出大小為50的種子集的預期影響，而IEA則需要幾十秒最長103.671 s才能計算出一個種子集的預期影響，相比起IEA，FIEA節省了很多時間，是提高算法效率的一個有效途徑. 因此，利用FIEA評估種子集的預期影響是合理且高效的.

表3 FIEA和IEA的影響范圍對比Tab. 3 Comparison of influence spread about FIEA and IEA

表4 FIEA和IEA的運行時間對比(單位：s)Tab. 4 Comparison of running time about FIEA and IEA(Unit: s)

3.3.2 影響范圍對比 本文的影響范圍是指種子集經過IC模型傳播后得到的種子集在一個網絡中激活的節點數目，激活的節點數越多，影響范圍越大，算法性能也越好. 由于傳播過程中的隨機性，將各算法選出的最優種子集以固定傳播概率P=0.01在IC模型下進行10 000次的蒙特卡洛模擬，并在圖4中給出了5個算法在不同種子集大小下的平均影響范圍.

如圖4所示，整體來看，SACGA在4個數據集中的表現最好，性能也最穩定，而GA的表現最差. 在FaceBook和E-mail這兩個數據集中SACGA明顯領先其它算法，當K=50 時，在E-mail數據集中SACGA的影響范圍比DDSE、SAEDV、GA和SACGA-N分別擴大了22.76%，5.06%，280.09%和7.79%. 需要注意的是，根據全局預期影響選擇種子集的算法SACGA-N的性能并沒有想象中的好，雖然在FaceBook和Slashdot數據集中，SACGA-N的性能僅次于SACGA，但在AstroPh數據集上，當種子集大小為20和30時，SACGA-N的影響范圍比SAEVD和DDSE分別低了0.67%和0.3%，0.5%和0.26%. 此外，同樣在FaceBook和Slashdot數據集中，當K＜30 時，SAEDV的性能落后于DDSE，在FaceBook數據集中尤為明顯，但隨著K＞30，SAEDV的性能逐漸優于DDSE，并且在AstroPh和E-mail數據集上，SAEDV的性能明顯優于DDSE. 在4個數據集中可以看到，DDSE后期搜索能力明顯不足，說明基于度的方法在搜索過程中還是存在一定的局限性，特別是在稀疏網絡中. GA算法性能相比其它算法性能差的原因可能是算法沒有跳出全局最優導致搜索能力不足，不能尋找到優秀的種子集. 綜上所述，相比起其它算法，SACGA在搜索時能跳出當前最優，并且表現良好，性能也較穩定.

圖4 算法在不同數據集上的影響范圍Fig. 4 Influence spread with different data sets

3.3.3 運行時間對比 為了驗證算法的高效性，本文給出5個算法在4個數據集中尋找到50個最佳種子節點的運行時間對比，如圖5所示，GA的時間效率最高，但GA性能最差. DDSE的運行時間也較短，但算法性能也不穩定. 而SAEDV由于要進行數萬次的迭代，所以網絡規模越大，耗時也越多. 雖然SACGA的運行時間比GA和DDSE的多，但其產生的影響范圍均比這兩個算法大，可以彌補在時間上的不足. 相比起SAEDV，SACGA在4個數據集中的時間效率分別提高了52.01%，49.75%，55.88%和50.16%，節省了大量時間成本.而SACGA-N要對種子集中的每一個節點進行全局預期影響估計，所以非常耗時，在規模較小的FaceBook數據集中找到K=50 的種子集都需要5 433.014 673 s，高額的時間成本在數據量較大的網絡中并不能成為一個合理的解決方案. 因此，實驗結果表明，本文提出的SACGA能在影響范圍和時間成本上有較好的平衡.

圖5 不同數據集上的算法運行時間對比Fig. 5 Comparison of algorithms’ running time on different data sets

4 結束語

本文利用一階容斥激活集作為適應度函數評估種子集的預期影響，提出一種自適應混沌遺傳算法SACGA. 通過單個節點的影響力構造關鍵節點集，利用Logistic混沌序列均勻搜索和自適應變異來增強算法的局部尋優能力，加快收斂. 在4個真實數據集上的實驗表明，SACGA在影響范圍和運行時間兩個指標上都有良好表現，驗證了該算法的穩定性和高效性. 現有智能算法求解影響力最大化問題的方法還有很大的改進空間，如何合理設置初始種群和更好地改進算法設計，使得算法更加高效，也是需要進一步探究的問題.