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

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

0 引言

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

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

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

1 相關(guān)知識(shí)

1.1 影響力最大化問題

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

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

1.2 目標(biāo)函數(shù)

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

式中，σ（S0）記錄了種子集在傳播中激活的所有節(jié)點(diǎn)，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)鞑ニ惴ǎ灸Ｐ陀奢斎雽?、隱藏層和輸出層組成。傳播方式分為以下兩個(gè)階段：

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

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

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

2 算法框架

2.1 優(yōu)化算法

2017年，Seyedali Mirjalili等[7]提出了一種模擬樽海鞘生物的鏈?zhǔn)饺盒袨榈男滦腿褐悄軆?yōu)化方法（salp swarm algorithm，SSA）。在鏈?zhǔn)饺褐蟹譃轭I(lǐng)導(dǎo)者和追隨者兩部分，領(lǐng)導(dǎo)者負(fù)責(zé)指揮追隨者前往食物存在的方向。由于結(jié)構(gòu)的特殊性，追隨者只受前一個(gè)樽海鞘的影響，這使SSA算法具有很強(qiáng)的全局探索能力。

salps初始化信息為：

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

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

跟隨者更新的方式為：

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

2.2 種子集更新

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

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

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

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

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

3 算法仿真

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

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

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

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

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

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

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

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

圖3 IM-SSA與其他算法的傳播對(duì)比

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

4 結(jié)語

隨著大數(shù)據(jù)時(shí)代的發(fā)展，數(shù)據(jù)驅(qū)動(dòng)被用于各種優(yōu)化問題，顯示了數(shù)據(jù)驅(qū)動(dòng)優(yōu)化方法的優(yōu)越性，因此，本文基于數(shù)據(jù)驅(qū)動(dòng)思想建立代理模型，提出了一種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ù)測(cè)模型，最后利用SSA算法進(jìn)一步優(yōu)化，并在SSA算法框架中使用交叉變異以增強(qiáng)樣本多樣性。相比于幾種經(jīng)典的結(jié)構(gòu)中心性算法，本文算法獲取了傳播性能更好的節(jié)點(diǎn)。在以后的優(yōu)化問題研究中，數(shù)據(jù)驅(qū)動(dòng)或許能夠發(fā)揮更重要的作用。