基于學(xué)習(xí)自動機(jī)與螢火蟲算法的鏈路預(yù)測

舒 堅(jiān)，李睿瑞，熊 濤，劉琳嵐，孫利民

(1.南昌航空大學(xué)軟件學(xué)院，江西南昌330063；2.南昌航空大學(xué)信息工程學(xué)院，江西南昌330063)

便攜交換網(wǎng)絡(luò)（pocket switched network,PSN）是一類特殊的機(jī)會網(wǎng)絡(luò)，內(nèi)部節(jié)點(diǎn)由攜帶便攜式手持設(shè)備的人員組成[1]，不需要源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)之間存在完整鏈路，利用節(jié)點(diǎn)移動帶來相遇機(jī)會實(shí)現(xiàn)數(shù)據(jù)交換，以“存儲—攜帶—轉(zhuǎn)發(fā)”形式進(jìn)行通信[2]。目前針對PSN網(wǎng)絡(luò)的研究面臨以下挑戰(zhàn)：網(wǎng)絡(luò)行為預(yù)測、消息轉(zhuǎn)發(fā)[3]、命名的動態(tài)性等[4]。

研究PSN網(wǎng)絡(luò)行為預(yù)測中的鏈路預(yù)測問題，為PSN的網(wǎng)絡(luò)演化機(jī)制研究及路由、拓?fù)淇刂坪鸵苿庸芾淼壬蠈訁f(xié)議提供支撐，推動PSN在商品推薦[5]、災(zāi)難救援、公共安全領(lǐng)域的事件檢測、軍事領(lǐng)域等方面的應(yīng)用[6]。近年來，隨著對機(jī)會網(wǎng)絡(luò)研究的深入，研究者提出了多種鏈路預(yù)測方法，但針對PSN網(wǎng)絡(luò)的鏈路預(yù)測研究較少。與本研究相關(guān)的鏈路預(yù)測方法是基于相似性指標(biāo)的預(yù)測方法和基于機(jī)器學(xué)習(xí)的預(yù)測方法。

基于相似性指標(biāo)的預(yù)測方法利用網(wǎng)絡(luò)信息計(jì)算節(jié)點(diǎn)間的相似性，連接概率與相似性呈正相關(guān)。共同鄰居[7]（common neighbor,CN）指標(biāo)認(rèn)為節(jié)點(diǎn)的共同鄰居越多，相近程度越高，呂琳媛等[8]對CN的改進(jìn)指標(biāo)AA（adamic-adar）指標(biāo)、Sorenson指標(biāo)、RA（resourceallocation index）指標(biāo)等進(jìn)行了闡述；Huang等[9]考慮了共同鄰居節(jié)點(diǎn)間依賴關(guān)系的不同，采用貝葉斯分類器計(jì)算節(jié)點(diǎn)的相似性；Sun[10]引入社區(qū)結(jié)構(gòu)的思想，提出局部親和結(jié)構(gòu)（local affinity structure,LAS）指標(biāo)以衡量節(jié)點(diǎn)間的“緊密度”；Yang等[11]綜合考慮節(jié)點(diǎn)間最短路徑和局部社區(qū)內(nèi)的邊聚類系數(shù)對節(jié)點(diǎn)間產(chǎn)生連接的影響，提出LCAR指標(biāo)計(jì)算節(jié)點(diǎn)間的相似性。

基于機(jī)器學(xué)習(xí)的預(yù)測方法通過特征提取的方式進(jìn)行鏈路預(yù)測。Li等[12]結(jié)合CN、LHN-II、COS+和MFI，提出基于集合模型的鏈路預(yù)測方法（ensemble-modelbased link prediction,EMLP）；Chiu等[13]通過建立深層神經(jīng)網(wǎng)絡(luò)，以傳統(tǒng)相似性度量組成的相似性指標(biāo)向量作為樣本，使用弱評估器評估動態(tài)系統(tǒng)中的變化概率；Hao[14]提出將融合的網(wǎng)絡(luò)特征作為深度置信網(wǎng)絡(luò)（deep belief network,DBN）的輸入，以未來的連接狀態(tài)作為標(biāo)簽，構(gòu)建預(yù)測模型；Li[15]提出利用受限玻爾茲曼機(jī)（restricted Boltzman machine,RBM）處理節(jié)點(diǎn)對歷史連接信息，將得到的信息作為梯度提升決策樹（gradient boosting decision tree,GBDT）的輸入，預(yù)測節(jié)點(diǎn)對未來時(shí)刻的連接狀態(tài)；Butun[16]提出根據(jù)網(wǎng)絡(luò)的三元關(guān)系構(gòu)建三元接近度指標(biāo)，針對有向動態(tài)網(wǎng)絡(luò)，使用三元組接近度作為訓(xùn)練樣本，訓(xùn)練基于模式的有監(jiān)機(jī)器學(xué)習(xí)模型完成鏈路預(yù)測任務(wù)。

學(xué)習(xí)自動機(jī)憑借其不受樣本的非均衡性影響，具有良好的噪聲魯棒性，非常適合處理在概率空間尋找全局最優(yōu)解的問題，經(jīng)歷幾十年的發(fā)展，其收斂速度有很大的提高，成為解決各種現(xiàn)實(shí)問題的重要工具之一[17]。PSN網(wǎng)絡(luò)具有節(jié)點(diǎn)移動性、節(jié)點(diǎn)間間歇性連接、高延遲等特點(diǎn)，其鏈路預(yù)測面臨的挑戰(zhàn)是節(jié)點(diǎn)相遇的機(jī)會性和拓?fù)涞臅r(shí)變性，因此PSN網(wǎng)絡(luò)中獲得高質(zhì)量鏈路預(yù)測的關(guān)鍵是如何較全面地獲取節(jié)點(diǎn)的屬性。作者采用學(xué)習(xí)自動機(jī)（learning automata,LA）對節(jié)點(diǎn)的屬性進(jìn)行聚類，目的在于使得網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)都找到所屬社區(qū)，以更全面地獲取節(jié)點(diǎn)的屬性。

螢火蟲算法（firefly algorithm,FA）[18]屬于仿生群智能優(yōu)化算法，是一種啟發(fā)式的算法，可解決連續(xù)空間的尋優(yōu)問題，廣泛應(yīng)用于特征值優(yōu)化、工程結(jié)構(gòu)設(shè)計(jì)、聚類、參數(shù)選擇等。作者采用螢火蟲算法對所構(gòu)建二分類器[19]的參數(shù)進(jìn)行優(yōu)化。

綜上所述，針對PSN網(wǎng)絡(luò)的節(jié)點(diǎn)屬性和節(jié)點(diǎn)移動特性，作者提出基于自動學(xué)習(xí)機(jī)和螢火蟲算法的鏈路預(yù)測方法（link prediction approach for pocket switched network based on firefly algorithm,FA-LP）。使用分布式學(xué)習(xí)自動機(jī)處理節(jié)點(diǎn)的屬性信息，完成節(jié)點(diǎn)的自適應(yīng)聚類過程，實(shí)現(xiàn)PSN網(wǎng)絡(luò)的社區(qū)劃分；構(gòu)建反映PSN網(wǎng)絡(luò)社區(qū)屬性、節(jié)點(diǎn)移動性和節(jié)點(diǎn)間間歇性連接的相似性指標(biāo)（similarity index based on community and mobile behavior,SICM），并對傳統(tǒng)相似性指標(biāo)進(jìn)行改進(jìn)；構(gòu)建鏈路預(yù)測的二分類器模型，借助螢火蟲算法在連續(xù)空間中高效尋優(yōu)的優(yōu)點(diǎn)對其進(jìn)行優(yōu)化。

1 社區(qū)劃分

PSN網(wǎng)絡(luò)社區(qū)劃分的目的在于將屬性相似的節(jié)點(diǎn)盡可能劃分在同一個(gè)社區(qū)內(nèi)，社區(qū)劃分的過程如下。

1.1 節(jié)點(diǎn)屬性的獲取

所謂物以類聚，人以群分，在網(wǎng)絡(luò)中兩個(gè)節(jié)點(diǎn)的屬性越相似就越可能產(chǎn)生聯(lián)系。人們更愿意和與自己年齡相仿、使用相同的語言、地理位置相近的人聊天。PSN網(wǎng)絡(luò)由人組成，其節(jié)點(diǎn)的屬性信息相對容易獲取?？坍嫻?jié)點(diǎn)的社區(qū)屬性，最直接的方法就是使用標(biāo)簽，可以根據(jù)年齡、職業(yè)、教育、興趣、地理位置、性別、信仰等屬性可以將節(jié)點(diǎn)劃分為不同類型。作者采用MIT發(fā)布的真實(shí)數(shù)據(jù)集“the reality mining data”[20]，節(jié)點(diǎn)擁有許多屬性信息如問卷調(diào)查結(jié)果、上下班時(shí)間、通話記錄等。

1.2 自適應(yīng)聚類

根據(jù)節(jié)點(diǎn)的屬性向量完成PSN網(wǎng)絡(luò)的自適應(yīng)聚類。學(xué)習(xí)自動機(jī)包含了動作集合和概率集合，如式（1）、（2）所示：

式中， A為 學(xué)習(xí)自動機(jī)可執(zhí)行動作的集合， Ai為執(zhí)行將節(jié)點(diǎn)分配到第i 個(gè)社區(qū)的動作， P為學(xué)習(xí)自動機(jī)執(zhí)行每個(gè)動作所對應(yīng)概率的集合， PAi為執(zhí)行動作 Ai的概率。

假設(shè)學(xué)習(xí)自動機(jī)的初始狀態(tài)為：節(jié)點(diǎn)不屬于任何社區(qū)，且分配到各個(gè)社區(qū)的概率都相等。自適應(yīng)聚類過程如下：

1）學(xué)習(xí)自動機(jī)執(zhí)行根據(jù)概率向量中最大值對應(yīng)的動作，將節(jié)點(diǎn)劃分到對應(yīng)的社區(qū)。

2）當(dāng)所有節(jié)點(diǎn)被分配到某個(gè)社區(qū)后，計(jì)算每個(gè)社區(qū)的社區(qū)中心。

3）計(jì)算節(jié)點(diǎn)到本次遞歸過程的社區(qū)中心的歐式距離 Dcurrent。

4）計(jì)算節(jié)點(diǎn)到上次遞歸過程的社區(qū)中心的歐式距離 DPrevious。

5）通過比較Dcurrent與 DPrevious的大小判斷本次迭代過程的聚類效果，若 DPrevious大 于 Dcurrent，則說明本次迭代過程中的聚類效果好，節(jié)點(diǎn)根據(jù)與其他社區(qū)中心的歐式距離更新對應(yīng)的概率向量，反之說明本次聚類效果不好，概率向量不變。當(dāng)所有節(jié)點(diǎn)所屬的社區(qū)編號都不發(fā)生變化，社區(qū)結(jié)構(gòu)趨于穩(wěn)定時(shí)，完成PSN網(wǎng)絡(luò)的社區(qū)劃分。

2 相似性指標(biāo)的構(gòu)建

定義社區(qū)屬性影響系數(shù)，通過對真實(shí)數(shù)據(jù)集的實(shí)驗(yàn)分析，定義移動行為影響系數(shù)，構(gòu)建反映PSN網(wǎng)絡(luò)社區(qū)屬性、節(jié)點(diǎn)移動性和節(jié)點(diǎn)間間歇性連接的相似性指標(biāo)；將該指標(biāo)與CN、RA、AA等7種相似性指標(biāo)融合，得到PSN網(wǎng)絡(luò)的相似性指標(biāo)（similarity index of PSN,PSN_SI），從而構(gòu)建得到PSN網(wǎng)絡(luò)的相似性指標(biāo)向量（similarity index vector,SIV）。

2.1 社區(qū)屬性影響系數(shù)

在真實(shí)世界中，人們更容易與來自同一社區(qū)的成員見面。定義社區(qū)屬性影響系數(shù)（community attributeinfluencecoefficient,CAIC），如式（3）所示：

2.2 移動行為影響系數(shù)

通過對Dartmouth數(shù)據(jù)集的分析，發(fā)現(xiàn)節(jié)點(diǎn)連接的訪問接入點(diǎn)（access point,AP）數(shù)量越多，則連接的移動節(jié)點(diǎn)數(shù)量也越多[21]。節(jié)點(diǎn)連接的AP數(shù)量代表了節(jié)點(diǎn)活躍度，節(jié)點(diǎn)活躍度的不同直接影響了節(jié)點(diǎn)與其他節(jié)點(diǎn)產(chǎn)生連接的概率。

為了說明PSN網(wǎng)絡(luò)中節(jié)點(diǎn)的活躍度與節(jié)點(diǎn)連接AP數(shù)量之間的關(guān)系，隨機(jī)從MIT數(shù)據(jù)集的97個(gè)移動節(jié)點(diǎn)中抽取8個(gè)節(jié)點(diǎn)（95、97、88、93、69、20、27、26），統(tǒng)計(jì)8個(gè)節(jié)點(diǎn)連接的移動節(jié)點(diǎn)數(shù)量和連接的AP數(shù)量，統(tǒng)計(jì)結(jié)果如圖1所示。

圖1 移動節(jié)點(diǎn)數(shù)量和AP數(shù)量的分布Fig.1 Distribution of the number of mobilenodesand the number of AP

從圖1可以看出，節(jié)點(diǎn)連接的AP數(shù)量越多，該節(jié)點(diǎn)連接的移動節(jié)點(diǎn)數(shù)量也越多，即節(jié)點(diǎn)連接的AP數(shù)量與節(jié)點(diǎn)連接的移動節(jié)點(diǎn)數(shù)量之間成正相關(guān)關(guān)系。

PSN網(wǎng)絡(luò)中連接的產(chǎn)生并不是完全偶然的，節(jié)點(diǎn)更傾向靠近與自身擁有相似連接的節(jié)點(diǎn)。隨機(jī)從MIT數(shù)據(jù)集抽取2個(gè)節(jié)點(diǎn)（21、52），統(tǒng)計(jì)與其他節(jié)點(diǎn)的連接次數(shù)以及節(jié)點(diǎn)對的共同鄰居節(jié)點(diǎn)數(shù)，部分統(tǒng)計(jì)結(jié)果如圖2、3所示。

圖2 21號節(jié)點(diǎn)連接分布情況Fig.2 Distribution of node21 connections

圖3 52號節(jié)點(diǎn)連接分布情況Fig.3 Distribution of node 52 connections

從圖2、3中可以看出，隨著節(jié)點(diǎn)對之間的共同節(jié)點(diǎn)數(shù)量增加，節(jié)點(diǎn)對之間的連接次數(shù)也增加。

通過分析節(jié)點(diǎn)的連接數(shù)與節(jié)點(diǎn)連接的AP數(shù)量、節(jié)點(diǎn)間連接的共同節(jié)點(diǎn)之間的關(guān)系，提出節(jié)點(diǎn)連接AP影響系數(shù)（node of access point coefficient, NAPC）與節(jié)點(diǎn)對共同連接節(jié)點(diǎn)影響系數(shù)（node pair common connect node coefficient,CCNC），如式（4）、（5）所示：

2.3 相似性指標(biāo)向量

基于上述研究，構(gòu)建反映PSN網(wǎng)絡(luò)社區(qū)屬性、節(jié)點(diǎn)移動性和節(jié)點(diǎn)間間歇性連接的相似性指標(biāo)SICM，如式（6）所示：

3 鏈路預(yù)測模型

鏈路預(yù)測模型的構(gòu)建過程如下。

3.1 時(shí)間序列分析

采用ARIMA對相似性指標(biāo)向量序列進(jìn)行時(shí)間序列分析，提取相似性指標(biāo)向量隨時(shí)間的變化的規(guī)律，具體步驟如下：

1）計(jì)算節(jié)點(diǎn)對在每個(gè)網(wǎng)絡(luò)快照中的相似性指標(biāo)向量，構(gòu)成相似性指標(biāo)向量序列VSIVS（similarity index vector sequence,SIVS），如式（8）所示：

2）采用單位根檢驗(yàn)（augmented Dickey-Fuller test,ADF）方法對相似性指標(biāo)向量序列進(jìn)行平穩(wěn)性檢驗(yàn)。若不平穩(wěn)，則進(jìn)行差分運(yùn)算將其轉(zhuǎn)換為平穩(wěn)序列。

3）根據(jù)自相關(guān)函數(shù)和偏自相關(guān)函數(shù)確定模型的滯后值 p 和滑動窗口q 的大小。

4）根據(jù)最小信息準(zhǔn)則（Akaike information criterion,AIC）對ARIMA模型參數(shù)尋優(yōu)，在保證模型擬合程度的前提下得到最優(yōu)參數(shù)。

采用窗口滑動截取相似性指標(biāo)向量序列輸入ARIMA模型，根據(jù)式（9）預(yù)測節(jié)點(diǎn)對下一時(shí)刻的SIV向量，以對應(yīng)連接狀態(tài)為標(biāo)簽，組成樣本，作為二分類器的輸入。

3.2 二分類器的構(gòu)建

通過將節(jié)點(diǎn)對的特征向量與超平面的權(quán)重向量進(jìn)行點(diǎn)乘運(yùn)算，判斷其正負(fù)，完成節(jié)點(diǎn)對的鏈路預(yù)測。因此，二分類器的構(gòu)建關(guān)鍵在于尋找最優(yōu)超平面的權(quán)值向量。

3.3 二分類器的優(yōu)化

3）更新種群位置。根據(jù)螢火蟲算法的個(gè)體移動規(guī)則[19]，適應(yīng)度低的權(quán)重參數(shù)向適應(yīng)度高的權(quán)重參數(shù)移動，適應(yīng)度最高的權(quán)重參數(shù)進(jìn)行隨機(jī)移動。

4）當(dāng)滿足停止條件或達(dá)到最大迭代次數(shù)時(shí)，返回適應(yīng)度最高的權(quán)重向量，反之則返回步驟2）。

經(jīng)過螢火蟲算法的優(yōu)化后，使用返回的最佳權(quán)重向量作為線性分類器的超平面，完成分類，預(yù)測節(jié)點(diǎn)對下一時(shí)刻的連接情況。

4 實(shí)驗(yàn)設(shè)計(jì)與分析

通過真實(shí)數(shù)據(jù)集下的實(shí)驗(yàn)驗(yàn)證相似性指標(biāo)PSN_SI和FA-LP方法。

4.1 實(shí)驗(yàn)數(shù)據(jù)集

采用兩種稀疏程度不一的PSN網(wǎng)絡(luò)作為驗(yàn)證的數(shù)據(jù)集，數(shù)據(jù)集信息見表1。

表1 實(shí)驗(yàn)數(shù)據(jù)集Tab.1 Experimental dataset

INFOCOM2006數(shù)據(jù)集記錄了2006年在巴西巴塞羅那為期4 d的會議期間，78位參加學(xué)術(shù)研討會并攜帶iMote通信設(shè)備的用戶與固定節(jié)點(diǎn)之間的連接記錄；MIT數(shù)據(jù)集是麻省理工大學(xué)97名實(shí)驗(yàn)人員攜帶藍(lán)牙設(shè)備通信情況，由于校園范圍大、學(xué)生的作息習(xí)慣致使晚上記錄極為稀疏。由于有的節(jié)點(diǎn)較早退出，有的節(jié)點(diǎn)較晚加入，為避免網(wǎng)絡(luò)中節(jié)點(diǎn)的個(gè)數(shù)發(fā)生變化，在此截取所有節(jié)點(diǎn)都處于活躍期的30 d數(shù)據(jù)。

4.2 評價(jià)指標(biāo)

使用受試者工作特征曲線下的面積（area under thecurve, AUC）和準(zhǔn)確率Precision作為鏈路預(yù)測結(jié)果的評價(jià)指標(biāo)。

AUC可以簡單理解為從測試邊集和不存在邊集中各取一條邊，比較兩者相似性的高低，如果測試邊相似性大于不存在邊則加1分，相等則加0.5分。AUC定義如式（12）所示，用字母H統(tǒng)一表示評價(jià)指標(biāo)相關(guān)變量。

4.3 SICM指標(biāo)的驗(yàn)證

通過選取不同的切片時(shí)長，在INFOCOM2006和MIT數(shù)據(jù)集上驗(yàn)證SICM指標(biāo)的有效性和穩(wěn)定性。

INFOCOM2006數(shù)據(jù)集的時(shí)間切片長度分別為210、240、270、300、360、430 min，對應(yīng)的切片數(shù)量分別為20、18、16、14、12、10；MIT數(shù)據(jù)集上的切片時(shí)長分別為0.5、1.0、1.5、2.0、3.0、6.0 d，對應(yīng)的切片數(shù)量分別為60、30、20、15、10、5。

相似性指標(biāo)PSN_SI的AUC值隨切片數(shù)量變化的趨勢如圖4、5所示。

圖4 INFOCOM2006數(shù)據(jù)集上的AUC值對比Fig.4 Comparison of AUC values on the INFOCOM2006 dataset

從圖4可以看出，各個(gè)指標(biāo)均隨切片數(shù)目的減少而提高了預(yù)測效果，且提高的幅度基本一致，但W_HDI低于其他指標(biāo)。

圖5 MIT數(shù)據(jù)集上的AUC值對比Fig.5 Comparison of AUC values on the MIT dataset

從圖5中可以看出，W_RA、W_AA比其他指標(biāo)在AUC上的表現(xiàn)更好，但在切片數(shù)為15時(shí)卻不如W_CN和W_Salton。通過實(shí)驗(yàn)可以得出，雖然PSN_SI中各個(gè)指標(biāo)的表現(xiàn)有所區(qū)別，但總體而言都能較好的對PSN網(wǎng)絡(luò)進(jìn)行鏈路預(yù)測，預(yù)測的效果較平穩(wěn)。

為了進(jìn)一步說明相似性指標(biāo)PSN_SI的有效性，使用Precision作為評價(jià)指標(biāo)，在上述時(shí)間切片下使用相似性指標(biāo)PSN_SI進(jìn)行鏈路預(yù)測的實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如圖6、7所示。

圖6 INFOCOM2006數(shù)據(jù)集上的Precision值對比Fig.6 Comparison of Precision values on the INFOCOM-2006 dataset

圖7 MIT數(shù)據(jù)集上的Precision值對比Fig.7 Comparison of Precision valueson the MIT dataset

從實(shí)驗(yàn)結(jié)果來看，在不同的數(shù)據(jù)集與切片數(shù)量的情況下，PSN_SI都可以較好地獲取鏈路變化的潛在特征，從而進(jìn)行鏈路預(yù)測。由圖6可知，在INFOCOM2006數(shù)據(jù)集下切片數(shù)量為10時(shí)，不同的PSN_SI均有較好的Precision表現(xiàn)，且W_CN指標(biāo)表現(xiàn)最佳。由圖7可知，所有的PSN_SI均存在波動的情況，Precision在0.561～0.881之間，W_CN比其他PSN_SI的預(yù)測效果更好。

在INFOCOM2006和MIT數(shù)據(jù)集中選取上述切片數(shù)進(jìn)行改進(jìn)前后指標(biāo)的對比實(shí)驗(yàn)，得到的AUC和Precision結(jié)果如表2、3所示。

通過表2、3的實(shí)驗(yàn)結(jié)果可以看出：無論是在AUC還是在Precision上，改進(jìn)后的指標(biāo)在絕大多數(shù)情況下比改進(jìn)前的指標(biāo)效果好。在AUC方面，相似性指標(biāo)PSN_SI相比于常見的相似性指標(biāo)的預(yù)測準(zhǔn)確率均有所提高且性能穩(wěn)定；不同的相似性指標(biāo)在不同切片數(shù)量情況下Precision指標(biāo)值波動較大，在不同數(shù)據(jù)集中表現(xiàn)差異較大。改進(jìn)后的相似性指標(biāo)在兩個(gè)數(shù)據(jù)集上不同切片數(shù)量情況下的實(shí)驗(yàn)結(jié)果并不會大幅發(fā)生變化，從而表明改進(jìn)后的相似性指標(biāo)具有良好的穩(wěn)定性。

表2 在INFOCOM2006和MIT數(shù)據(jù)集中不同的切片數(shù)下各指標(biāo)AUC的對比Tab.2 Comparison of AUC in different number of time slices in INFOCOM 2006 and MIT

表3 在INFOCOM 2006和MIT數(shù)據(jù)集中不同的切片數(shù)下各指標(biāo)Precision的對比Tab.3 Comparison of Precision in different number of time slices in INFOCOM2006 and MIT

4.4 預(yù)測性能比較

在INFOCOM2006、MIT數(shù)據(jù)集上，進(jìn)行FA-LP方法與支持向量分類（support vector classification,SVC）、K鄰近算法（K-nearest neighbor,KNN）、WEAK[13]、DBN[14]、RBM[15]方法的對比。在INFOCOM2006數(shù)據(jù)集上，設(shè)置螢火蟲算法的初始種群數(shù)量為200，迭代次數(shù)為150，時(shí)間幀長度為270 s，輸入序列長度為9；在MIT數(shù)據(jù)集上，設(shè)置螢火蟲算法的初始種群數(shù)量為250，迭代次數(shù)為120，時(shí)間幀長度為240，輸入序列長度為8。時(shí)間幀長度根據(jù)文獻(xiàn)[22]中所提的混沌時(shí)間序列理論確定，使用計(jì)算得出最佳切片時(shí)長對網(wǎng)絡(luò)進(jìn)行時(shí)間切分，可以使網(wǎng)絡(luò)切片之間的最大限度地保留圖的演變信息。作者統(tǒng)計(jì)了30次對比實(shí)驗(yàn)的結(jié)果，采用AUC作為預(yù)測方法的指標(biāo)評價(jià)。作者提出的FA-LP方法與SVC、KNN、WEAK、DBN、RBM方法在INFOCOM 2006數(shù)據(jù)集下取得的AUC如圖8所示，上述方法在MIT數(shù)據(jù)集下取得的AUC如圖9所示。并在表4中給出了上述方法在INFOCOM2006和MIT數(shù)據(jù)集中取得的AUC均值。

圖8 INFOCOM2006中不同方法的AUC值Fig.8 AUC values of different methods in INFOCOM-2006

圖9 MIT中不同方法的AUC值Fig.9 AUC valuesof different methodsin MIT

表4 在INFOCOM2006和MIT數(shù)據(jù)集中各種預(yù)測方法的AUC均值Tab.4 AUC averages of different prediction methods in INFOCOM2006 and MIT

在INFOCOM2006和MIT兩個(gè)稀疏程度不同的數(shù)據(jù)集上，基于DBN方法和提出的FA-LP方法較SVC、KNN、WEAK等方法在預(yù)測性能上表現(xiàn)更加穩(wěn)定；在兩個(gè)數(shù)據(jù)集上，基于DBN模型的AUC值在0.92左右，而FA-LP的AUC值在0.94以上，甚至在INFOCOM-2006數(shù)據(jù)集上，F(xiàn)A-LP的AUC值達(dá)到了0.95。在兩個(gè)數(shù)據(jù)集的實(shí)驗(yàn)中，F(xiàn)A-LP比其他方法都有最高的AUC值，這說明FA-LP方法能夠有效地提取PSN網(wǎng)絡(luò)的連接特征，達(dá)到更好的鏈路預(yù)測結(jié)果。

5 結(jié) 論

作者采用學(xué)習(xí)自動機(jī)對節(jié)點(diǎn)的屬性進(jìn)行聚類，構(gòu)建反映PSN網(wǎng)絡(luò)社區(qū)屬性、節(jié)點(diǎn)移動性和節(jié)點(diǎn)間間歇性連接的相似性指標(biāo)SICM，從而更好地反映節(jié)點(diǎn)相遇的機(jī)會性和拓?fù)涞臅r(shí)變性，采用螢火蟲算法優(yōu)化二分類器，從而獲得更高的準(zhǔn)確率和更好的穩(wěn)定性。但是，文中僅探討了PSN網(wǎng)絡(luò)單節(jié)點(diǎn)對的鏈路預(yù)測方法，下一步的研究方向?yàn)镻SN網(wǎng)絡(luò)中多節(jié)點(diǎn)對間的鏈路預(yù)測。