基于BP神經(jīng)網(wǎng)絡(luò)的LT模型影響力最大化研究

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

（①安徽工業(yè)大學(xué)，馬鞍山 243002；②安徽工程大學(xué)，蕪湖 241000）

0 引言

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

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

本文結(jié)合數(shù)據(jù)驅(qū)動方法構(gòu)建了基于BP神經(jīng)網(wǎng)絡(luò)的影響力最大化算法求解模式，首先以網(wǎng)絡(luò)結(jié)構(gòu)特性作為選擇樣本節(jié)點的標準，挖掘出具有樣本代表性的部分節(jié)點，構(gòu)造數(shù)據(jù)樣本，用于訓(xùn)練模型，然后在改進的SSA算法框架下進行計算。

1 相關(guān)知識

1.1 影響力最大化問題

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

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

1.2 目標函數(shù)

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

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

1.3 BP神經(jīng)網(wǎng)絡(luò)

BP神經(jīng)網(wǎng)絡(luò)作為一種被廣泛應(yīng)用的多層前饋式神經(jīng)網(wǎng)絡(luò)，又被稱為誤差逆?zhèn)鞑ニ惴?，基本模型由輸入層、隱藏層和輸出層組成。傳播方式分為以下兩個階段：

式中，f為激活函數(shù)，w代表節(jié)點之間的權(quán)值，b代表節(jié)點閾值。tansig函數(shù)表達式為：

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

式中，E（w，b）為誤差函數(shù)。

2 算法框架

2.1 優(yōu)化算法

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

salps初始化信息為：

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

領(lǐng)導(dǎo)者初始化的方式為：

跟隨者更新的方式為：

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

2.2 種子集更新

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

Sigmoid函數(shù)公式如下所示：

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

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

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

3 算法仿真

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

為了驗證該算法的有效性，本文構(gòu)造了一個規(guī)模為500節(jié)點的BA網(wǎng)絡(luò)，節(jié)點度分布與基本信息如圖1和表1所示。

圖1 BA網(wǎng)絡(luò)的節(jié)點度分布

表1 BA網(wǎng)絡(luò)數(shù)據(jù)的基本信息

3.2 實驗設(shè)置與結(jié)果分析

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

圖2 BP神經(jīng)網(wǎng)絡(luò)的訓(xùn)練精度

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

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

表2 IM-SSA算法與幾種結(jié)構(gòu)中心性算法的效果對比

4 結(jié)語

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