基于BP神經網絡的LT模型影響力最大化研究

張凱倫 ZHANG Kai-lun；汪超 WANG Chao；王璐 WANG Lu

（①安徽工業大學，馬鞍山 243002；②安徽工程大學，蕪湖 241000）

0 引言

隨著互聯網的高速發展，越來越多的人習慣在線上社交平臺獲取信息，社交網絡中的影響力最大化問題（IMP）成為熱點研究問題。影響力最大化問題，一般是指在網絡中篩選出k個具有強大影響力的用戶，通過給定的離散信息傳播模型將信息傳播至最大范圍。Domingos和Richard[1]最早將IM問題數學化，隨后，Kempe等[2]在此基礎上，首次提出可以用離散優化的方式解決IM問題，并證明了影響力最大化問題的性質是NP難的。文獻也分析了兩種應用廣泛的信息傳播模型，分別是獨立級聯模型（IC model）和線性閾值模型（LT model）。IC模型由于傳播概率的隨機性，不穩定性偏高，而LT模型屬于一種價值累計模型，能夠刻畫個體與個體、個體與集體之間相互影響的情形，可以避免這種情況。

在Kempe等[2]提出貪婪算法后，研究學者在貪婪算法的基礎上提出了眾多解決IM問題的方法。傳統優化算法包括模擬退火算法[3]，禁忌搜索算法[4]等，然而傳統算法總是需要遍歷網絡中所有節點，對于規模稍大的網絡不具有適用性。為了提高計算精度和效率，一些智能優化算法被相繼提出，例如常用的粒子群優化算法[5]，人工蜂群優化算法[6]等。近幾年，Mirjalili等[7]提出的樽海鞘優化算法（SSA）也被應用于各種優化問題。在如今的信息化時代，復雜網絡數據驟增，僅依賴智能優化算法不再能妥善處理該問題。為了盡可能多地擴散影響，數據驅動方法被應用[8]。由于數據驅動技術善于發現數據中的復雜關系，促使模型適應數據，并能夠根據不同的數據而改變，在各研究領域得到廣泛應用。另外，由于BP神經網絡具有結構簡單、易訓練且預測效果良好等優點[9]，因此，本文選擇經典的BP神經網絡來優化預測模型。

本文結合數據驅動方法構建了基于BP神經網絡的影響力最大化算法求解模式，首先以網絡結構特性作為選擇樣本節點的標準，挖掘出具有樣本代表性的部分節點，構造數據樣本，用于訓練模型，然后在改進的SSA算法框架下進行計算。

1 相關知識

1.1 影響力最大化問題

影響力最大化一般被定義為：給定一個圖G=（V，E）及其上的一個離散時間遞進性傳播模型，即線性閾值模型，其中V定義為網絡中所有節點的集合，E表示任意節點之間的鄰邊。給定一個預算k，要找到一個最多k個點的種子集合S0*，使得該種子集合的影響力擴展度達到最大。其數學公式如下：

LT模型作為一種價值累計模型，首先給網絡G中每個節點分配一個閾值θv（θv≤1），節點之間的邊權重由節點入度Lin(v)決定，邊權重計算方式為。若活躍節點u對鄰居節點v的影響力滿足，則稱節點u成功激活了節點v，反之激活失敗。

1.2 目標函數

本文基于LT傳播模型定義了目標函數：

式中，σ（S0）記錄了種子集在傳播中激活的所有節點，m是平衡參數。

1.3 BP神經網絡

BP神經網絡作為一種被廣泛應用的多層前饋式神經網絡，又被稱為誤差逆傳播算法，基本模型由輸入層、隱藏層和輸出層組成。傳播方式分為以下兩個階段：

式中，f為激活函數，w代表節點之間的權值，b代表節點閾值。tansig函數表達式為：

反向傳播子過程如下式所示：

式中，E（w，b）為誤差函數。

2 算法框架

2.1 優化算法

2017年，Seyedali Mirjalili等[7]提出了一種模擬樽海鞘生物的鏈式群行為的新型群智能優化方法（salp swarm algorithm，SSA）。在鏈式群中分為領導者和追隨者兩部分，領導者負責指揮追隨者前往食物存在的方向。由于結構的特殊性，追隨者只受前一個樽海鞘的影響，這使SSA算法具有很強的全局探索能力。

salps初始化信息為：

式中，D為空間維數，N為種群數量，搜索空間的上界為ub，下界為l b。

領導者初始化的方式為：

跟隨者更新的方式為：

式中，Fj表示食物在第j維空間中的位置，l為當前迭代次數，L為最大迭代次數。其中sa l pij（l）為在l次迭代時，第i只salp在第j維空間中的坐標。c2和c3為區間[0，1]內的隨機數，c2決定移動長度，c3決定移動方向。c1用于控制整個群體的探索和開發能力，表達式如下：

2.2 種子集更新

由于SSA算法不適用于離散型優化問題，本文使用Sigmoid函數對算法中的變量進行離散化。為了避免讓算法在搜索過程中陷入局部最優，本文利用交叉變異操作來增強種群多樣性。首先，從結構中心性指標排名前百分之30的節點中產生初代種子集。在產生第一個種子集后，本章節使用交叉變異[10]來確定新的種子集成員，并將SSA算法中的位置更新公式作為確定個體選擇交叉位置的依據。

Sigmoid函數公式如下所示：

種子交叉位置由下式確定：

式中，Si表示經過映射之后的樽海鞘位置向量。系數w1，w2無固定數值，文中假設給定系數分別為1.4和0.8。

在交叉過程中，確定當前最優的一組個體和第二組個體中的交叉位置，將兩組個體相應位置的索引進行互換，形成兩組新的個體。小范圍變異行為如下：若rand<0.1，則種子集將再次進行更新，然后進行新一輪的迭代計算。

3 算法仿真

3.1 數據集

為了驗證該算法的有效性，本文構造了一個規模為500節點的BA網絡，節點度分布與基本信息如圖1和表1所示。

圖1 BA網絡的節點度分布

表1 BA網絡數據的基本信息

3.2 實驗設置與結果分析

本文首先以度中心性、介數中心性和Pagerank等網絡結構特性作為選擇樣本節點的標準，挖掘出前百分之30具有樣本代表性的節點，形成產生初始種群的節點候選池，每次從中挑選百分之20的節點，構造10000組數據樣本。其次，在BP訓練數據階段，設置三層神經網絡，隱藏層神經元個數設為10，兩級網絡的權重均設為（-1，1）之間的隨機數。以節點特征作為輸入變量，以節點影響力作為輸出變量，其中9000組樣本用于訓練，1000組樣本用于預測。步長設為10，迭代次數設為50000。在得到良好的預測效果后保存訓練網絡，利用增加了交叉變異操作的SSA算法進行計算。圖2為BP神經網絡對數據樣本的訓練效果，可以看到，訓練精度達到百分之93。

圖2 BP神經網絡的訓練精度

另外，本文羅列了幾種經典的結構中心性算法與本文算法進行對比，分別是BC[2]、DC[11]、CC[11]以及Pagerank算法[12]。表2記錄了幾種不同的優化算法得到的種子節點影響力，可以看出，本文算法的影響力結果略高于其余算法。圖3顯示，本文算法獲取的節點傳播能力高于其余幾種算法，并在計算迭代18次時呈現上升趨勢。因此，在其他條件保持一致的情況下，能夠看出本文算法挖掘出的節點傳播性能更強。

圖3 IM-SSA與其他算法的傳播對比

表2 IM-SSA算法與幾種結構中心性算法的效果對比

4 結語

隨著大數據時代的發展，數據驅動被用于各種優化問題，顯示了數據驅動優化方法的優越性，因此，本文基于數據驅動思想建立代理模型，提出了一種BP神經網絡下的影響力傳播最大化算法。該算法基于網絡結構特性生成樣本數據，利用BP神經網絡訓練樣本數據，優化預測模型，最后利用SSA算法進一步優化，并在SSA算法框架中使用交叉變異以增強樣本多樣性。相比于幾種經典的結構中心性算法，本文算法獲取了傳播性能更好的節點。在以后的優化問題研究中，數據驅動或許能夠發揮更重要的作用。