基于子圖演化與改進(jìn)蟻群優(yōu)化算法的社交網(wǎng)絡(luò)鏈路預(yù)測(cè)方法

顧秋陽，琚春華，吳功興

（1.浙江工業(yè)大學(xué)管理學(xué)院，浙江 杭州 310023；2.浙江工業(yè)大學(xué)中國中小企業(yè)研究院，浙江 杭州 310023；3.寧波諾丁漢大學(xué)商學(xué)院，浙江 寧波 315175；4.浙江工商大學(xué)管理工程與電子商務(wù)學(xué)院，浙江 杭州 310018）

1 引言

近年來在線社交網(wǎng)絡(luò)規(guī)模和用戶數(shù)量日益增加，鏈路預(yù)測(cè)作為社交網(wǎng)絡(luò)分析中的一個(gè)新興課題，現(xiàn)有研究往往根據(jù)社交網(wǎng)絡(luò)圖中現(xiàn)有節(jié)點(diǎn)及鏈接屬性來預(yù)測(cè)2 個(gè)節(jié)點(diǎn)之間的新鏈接[1]。鏈路預(yù)測(cè)的目標(biāo)為通過考慮社交網(wǎng)絡(luò)圖在時(shí)刻t的快照，預(yù)測(cè)出該網(wǎng)絡(luò)圖在時(shí)刻t+1 可能產(chǎn)生新鏈接，而時(shí)刻t+1 可能是拍下快照后的一周、一個(gè)月、一年，甚至幾年[2]。Liben-Nowell 等[3]將社交網(wǎng)絡(luò)中的鏈路預(yù)測(cè)視為挖掘鏈接的子集。鏈路預(yù)測(cè)可用于許多不同的應(yīng)用中。王智強(qiáng)等[4]等認(rèn)為在許多網(wǎng)絡(luò)中，由于信息或數(shù)據(jù)帶有噪聲，會(huì)產(chǎn)生一些不必要的鏈接，可以借助于鏈路預(yù)測(cè)方法來檢測(cè)這些不必要的鏈接，可用于通信偵察領(lǐng)域。其通過對(duì)社交網(wǎng)絡(luò)進(jìn)行鏈路預(yù)測(cè)得到了網(wǎng)絡(luò)的演化模型，使研究者能更好地了解網(wǎng)絡(luò)。Huang 等[5]提出了基于鏈路預(yù)測(cè)算法的新型似然方法，使用社交網(wǎng)絡(luò)圖對(duì)傳染病的患病率進(jìn)行建模，每個(gè)預(yù)測(cè)鏈接均顯示了社會(huì)中潛在的感染區(qū)域。Yin 等[6]在社交網(wǎng)絡(luò)環(huán)境中，通過預(yù)測(cè)用戶中的共同興趣來發(fā)掘新好友（即新鏈接），此類推薦也會(huì)增加用戶對(duì)社交網(wǎng)絡(luò)的忠誠度。Pech 等[7]通過分析客戶購物情況進(jìn)行鏈路預(yù)測(cè)，形成客戶商品推薦，優(yōu)化推薦系統(tǒng)，提升了預(yù)測(cè)成功率。

如今常用的鏈路預(yù)測(cè)方法可分為兩大類，即有監(jiān)督式方法和無監(jiān)督式方法。在預(yù)測(cè)鏈接時(shí)不需要任何先驗(yàn)知識(shí)或培訓(xùn)的為無監(jiān)督式方法，而使用該網(wǎng)絡(luò)訓(xùn)練所得的模型及先驗(yàn)知識(shí)來預(yù)測(cè)鏈接的為有監(jiān)督式方法。無監(jiān)督式方法大多使用網(wǎng)絡(luò)相似度度量及結(jié)構(gòu)屬性來實(shí)現(xiàn)鏈路預(yù)測(cè)，且不需要進(jìn)行任何訓(xùn)練。Wang 等[2]認(rèn)為兩節(jié)點(diǎn)之間最短路徑的長度和公共鄰節(jié)點(diǎn)的數(shù)量都可視為結(jié)構(gòu)屬性，這些屬性均可以用于鏈路預(yù)測(cè)。Jaccard 等[8]提出的Jaccard系數(shù)等方法類似于公共鄰點(diǎn)，而不同之處在于，在這種相似度度量方法中，如果兩節(jié)點(diǎn)所擁有的公共鄰點(diǎn)較多、非公共鄰點(diǎn)較少，則兩節(jié)點(diǎn)越靠近彼此。節(jié)點(diǎn)度數(shù)也是社交網(wǎng)絡(luò)環(huán)境中預(yù)測(cè)新鏈接的關(guān)鍵結(jié)構(gòu)屬性之一，即節(jié)點(diǎn)度數(shù)較高的2 個(gè)節(jié)點(diǎn)以后彼此交互的可能性更大，這種方法又被稱為優(yōu)先鏈接[9-11]。而近年來，某些鏈路預(yù)測(cè)算法所用的方法是基于特殊子圖的演化，此部分將在第2 節(jié)進(jìn)行詳細(xì)介紹。最大似然方法為典型的有監(jiān)督鏈路預(yù)測(cè)算法。Wu等[12]介紹了一種由網(wǎng)絡(luò)數(shù)據(jù)推導(dǎo)的層次結(jié)構(gòu)似然估計(jì)方法（系統(tǒng)樹圖），而概率模型也可視為有監(jiān)督式鏈路預(yù)測(cè)算法。王凱等[13]利用二元分類器進(jìn)行鏈路預(yù)測(cè)。雖然有監(jiān)督式方法考慮了每種網(wǎng)絡(luò)的特殊性，但可能會(huì)耗費(fèi)大量時(shí)間，且不適用于大型網(wǎng)絡(luò)[14]。

蟻群優(yōu)化（ACO,ant colony optimization）算法最早由Dorigo 等[15]提出，旨在解決困難的組合問題。蟻群優(yōu)化算法以螞蟻的覓食行為為基礎(chǔ)，認(rèn)為螞蟻在覓食時(shí)會(huì)隨機(jī)搜尋周圍環(huán)境；在發(fā)現(xiàn)食物后，螞蟻會(huì)檢查食物的數(shù)量和質(zhì)量并取走一塊食物；在回家的路上，螞蟻會(huì)沿途釋放一種叫作信息素的化學(xué)物質(zhì)，信息素的數(shù)量與食物源的數(shù)量和質(zhì)量成正比。信息素即為蟻群間的協(xié)同機(jī)制，可讓它們找出食物源到家的最短路徑[15]。本文擬使用蟻群優(yōu)化算法對(duì)所研究的問題進(jìn)行建模，主要包括以下3 個(gè)步驟。

步驟1設(shè)螞蟻k由社交網(wǎng)絡(luò)圖中節(jié)點(diǎn)i遍歷至節(jié)點(diǎn)j的概率為，如式(1)所示。

其中，τij為邊信息素?cái)?shù)量，ηij為由節(jié)點(diǎn)i移動(dòng)至節(jié)點(diǎn)j的成本，Ni為節(jié)點(diǎn)i的鄰節(jié)點(diǎn)集，系數(shù)α和β分別為蟻群優(yōu)化算法的基本參數(shù)。本文假設(shè)所有邊都具有初始數(shù)量的信息素。

步驟2無論何時(shí)使螞蟻都能找到食物為該問題的理想解，且每只螞蟻在從食物源到家的沿途上都會(huì)釋放信息素，如式(2)和式(3)所示。

其中，TK為螞蟻k所遍歷的由家至食物源的路徑，其長度為ck；m為現(xiàn)有蟻群的總數(shù)，表示找出由食物源至家的最短路徑。本文假設(shè)每條邊上的信息素都會(huì)逐漸消退；路徑越擁擠，其上保留的信息素就越多。

步驟3分析信息素的消退機(jī)理，如式(4)所示。

其中，ρ為基本參數(shù)。

本文首先以子圖演化的鏈路預(yù)測(cè)為基礎(chǔ)，在社交網(wǎng)絡(luò)圖中確定特殊子圖。然后，研究子圖演化以預(yù)測(cè)圖中的新鏈接，并用蟻群優(yōu)化算法來定位特殊子圖。最后，本文針對(duì)所提方法使用不同的網(wǎng)絡(luò)拓?fù)洵h(huán)境與數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，以期為社交網(wǎng)絡(luò)環(huán)境的優(yōu)化、鏈路的預(yù)測(cè)、監(jiān)控與追責(zé)提供實(shí)驗(yàn)依據(jù)；同時(shí)也為大眾更好地使用社交網(wǎng)絡(luò)提供指導(dǎo)意見。

本文的主要貢獻(xiàn)包括：1) 提出了一種基于子圖演化與蟻群優(yōu)化算法融合的社交網(wǎng)絡(luò)鏈路預(yù)測(cè)方法，提升了預(yù)測(cè)精度；2) 證明了圖形結(jié)構(gòu)在鏈路預(yù)測(cè)算法中起到重要作用；3) 相對(duì)于圖神經(jīng)網(wǎng)絡(luò)及圖深度學(xué)習(xí)等熱門鏈路預(yù)測(cè)方法，SE-ACO 算法能夠有效地縮短運(yùn)算時(shí)間。

2 文獻(xiàn)回顧

2.1 文獻(xiàn)綜述

由于本文所提方法運(yùn)用蟻群優(yōu)化算法找出了特殊子圖，因此本文將介紹基于子圖查找和演化的鏈路預(yù)測(cè)方法。本文所提方法與其他方法的最大區(qū)別在于將蟻群優(yōu)化算法首次用于鏈路預(yù)測(cè)過程中。Fadaee 等[16]認(rèn)為通過找出一定時(shí)間間隔內(nèi)的三元組演化模型，可預(yù)測(cè)出2 個(gè)連續(xù)社交網(wǎng)絡(luò)快照間的新鏈接，其所述方法為有監(jiān)督式結(jié)構(gòu)鏈路預(yù)測(cè)算法。如果該圖為有向圖，則會(huì)有64 個(gè)三元組，在每個(gè)三元組中的每2 個(gè)節(jié)點(diǎn)之間有4 種不同的關(guān)系：一個(gè)雙向鏈接，2 個(gè)單向鏈接，一個(gè)無鏈接。計(jì)算2個(gè)連續(xù)社交網(wǎng)絡(luò)快照上的64 個(gè)三元組可得到三元組轉(zhuǎn)換矩陣（TTM,triad transition matrix），基于此可找出 2 個(gè)非連接節(jié)點(diǎn)之間的鏈接概率。Lichtenwalter 等[17]提出了一種新型有監(jiān)督式社交網(wǎng)絡(luò)鏈路預(yù)測(cè)及分析算法，旨在找出社交網(wǎng)絡(luò)圖的子結(jié)構(gòu)，也稱為頂點(diǎn)配置結(jié)構(gòu)（VCP,vertex collocation profile）。張子柯等[18]將聚類系數(shù)的定義進(jìn)行擴(kuò)展，提出了一種新型概率鏈路預(yù)測(cè)算法。聚類系數(shù)是社交網(wǎng)絡(luò)圖中的三元組變?yōu)槿顷P(guān)系的趨勢(shì)，式(5)展示了如何計(jì)算社交網(wǎng)絡(luò)圖中的聚類系數(shù)。

Zhang 等[19]研究了有向網(wǎng)絡(luò)中的特殊子圖，認(rèn)為這些子圖代表有向網(wǎng)絡(luò)中的微觀組織原理，并表明，這些子圖中在社交網(wǎng)絡(luò)中較普遍。最優(yōu)的有向網(wǎng)絡(luò)局部結(jié)構(gòu)是包括4 個(gè)節(jié)點(diǎn)與4 個(gè)有向鏈接的Bi-Fan 結(jié)構(gòu)，胡文斌等[20]基于聚類機(jī)制（CM,clustering mechanism）和潛在理論（PT,potential theory）證實(shí)了上述觀點(diǎn)，即如果子圖是僅比Bi-Fan結(jié)構(gòu)少一個(gè)鏈接的子圖，則創(chuàng)建該鏈接的概率將是最高的。郭麗媛等[21]采用譜聚類（SC,spectral clustering）的方法對(duì)社交網(wǎng)絡(luò)的鏈路預(yù)測(cè)進(jìn)行研究，通過降維方法獲得簡易矩陣,采用該矩陣能夠提高預(yù)測(cè)效果；其不僅計(jì)算了類內(nèi)節(jié)點(diǎn)之間的相似度，還計(jì)算了不同類之間的節(jié)點(diǎn)相似度。Gong 等[22]首先提出了一個(gè)特征轉(zhuǎn)化方法，該方法能夠把原有特征進(jìn)行簡化，提高了鏈路預(yù)測(cè)精度；其次構(gòu)建基于受限玻爾茲曼機(jī)的深度學(xué)習(xí)算法進(jìn)行鏈路預(yù)測(cè)。這種無監(jiān)督算法僅使用小樣本訓(xùn)練即可取得良好效果。

目前在社區(qū)發(fā)現(xiàn)和預(yù)測(cè)這一領(lǐng)域，圖神經(jīng)網(wǎng)絡(luò)（GNN,graph neural network）和圖搜索聚類算法也表現(xiàn)出了較優(yōu)能力。Gori 等[23]借鑒神經(jīng)網(wǎng)絡(luò)的研究成果，設(shè)計(jì)了一種用于處理圖結(jié)構(gòu)數(shù)據(jù)的模型。Bronstein 等[24]對(duì)圖結(jié)構(gòu)數(shù)據(jù)和流形數(shù)據(jù)領(lǐng)域的深度學(xué)習(xí)方法進(jìn)行了綜述，側(cè)重于將所述各種方法置于一個(gè)稱為幾何深度學(xué)習(xí)的統(tǒng)一框架內(nèi)。白鉑等[25]提出了一種新的圖神經(jīng)網(wǎng)絡(luò)分類方法，重點(diǎn)介紹了圖卷積網(wǎng)絡(luò)，并總結(jié)了圖神經(jīng)網(wǎng)絡(luò)方法在不同學(xué)習(xí)任務(wù)中的開源代碼和基準(zhǔn)。Fan 等[26]將圖神經(jīng)網(wǎng)絡(luò)提取的物品特征和節(jié)點(diǎn)特征，通過多層感知機(jī)進(jìn)行評(píng)分預(yù)測(cè)推薦。郭嘉琰等[27]指出了在不同GNN 變體中出現(xiàn)的相關(guān)聚集過程，但也發(fā)現(xiàn)了以圖神經(jīng)網(wǎng)絡(luò)為代表的方法通常時(shí)間成本較高。

2.2 文獻(xiàn)評(píng)述

通過對(duì)現(xiàn)有研究成果的梳理發(fā)現(xiàn)，社交網(wǎng)絡(luò)中的鏈路預(yù)測(cè)方法已經(jīng)受到了國內(nèi)外學(xué)者的重視并得到豐富的成果。上述研究成果對(duì)本文具有一定的借鑒意義，但也存在一些不足：1)已有很多學(xué)者對(duì)基于社交網(wǎng)絡(luò)圖的鏈路預(yù)測(cè)開展了一系列卓有成效的研究，但是多數(shù)將其定義為靜態(tài)圖（如李冬等[28]），鮮有基于子圖演化進(jìn)行動(dòng)態(tài)社交網(wǎng)絡(luò)鏈路預(yù)測(cè)的文獻(xiàn)；2) 現(xiàn)有的社交網(wǎng)絡(luò)鏈路預(yù)測(cè)方法大多基于數(shù)理推導(dǎo)（如Gao 等[11]），但很少有加入如蟻群優(yōu)化算法等概率型路徑尋優(yōu)算法進(jìn)行社交網(wǎng)絡(luò)鏈路預(yù)測(cè)的文獻(xiàn)；3) 幾乎所有的相關(guān)文獻(xiàn)都使用了例如BA 無標(biāo)度網(wǎng)絡(luò)（BA scale-free network）、WS 小世界網(wǎng)絡(luò)（WS small world network）等人工網(wǎng)絡(luò)進(jìn)行實(shí)驗(yàn)（如方哲等[29]），很少有使用真實(shí)數(shù)據(jù)集對(duì)社交網(wǎng)絡(luò)鏈路預(yù)測(cè)進(jìn)行分析的文獻(xiàn)記錄；4) 幾乎所有的相關(guān)文獻(xiàn)都直接使用現(xiàn)有算法進(jìn)行鏈路預(yù)測(cè)（如尚鳳軍等[30]），很少有使用改進(jìn)算法對(duì)社交網(wǎng)絡(luò)進(jìn)行鏈路預(yù)測(cè)的文獻(xiàn)。

基于以上綜述，本文首先提出一種基于子圖演化與蟻群優(yōu)化算法融合的社交網(wǎng)絡(luò)鏈路預(yù)測(cè)方法，以基于子圖演化的鏈路預(yù)測(cè)為基礎(chǔ)，在社交網(wǎng)絡(luò)圖中確定特殊子圖；然后研究子圖演化以預(yù)測(cè)圖中的新鏈接，并用蟻群優(yōu)化算法定位特殊子圖；最后針對(duì)所提方法使用不同網(wǎng)絡(luò)拓?fù)洵h(huán)境與數(shù)據(jù)集進(jìn)行驗(yàn)證。

3 社交網(wǎng)絡(luò)鏈路預(yù)測(cè)方法設(shè)計(jì)

3.1 方法設(shè)計(jì)總體思路

社交網(wǎng)絡(luò)中的每個(gè)實(shí)體都可以用一個(gè)節(jié)點(diǎn)表示，2 個(gè)節(jié)點(diǎn)之間的關(guān)系可用鏈接表示。為預(yù)測(cè)2 個(gè)節(jié)點(diǎn)之間可能產(chǎn)生的新鏈接，那么這2 個(gè)節(jié)點(diǎn)之間至少應(yīng)該有一個(gè)關(guān)聯(lián)。另一方面，本文認(rèn)為預(yù)測(cè)2個(gè)無任何關(guān)系的節(jié)點(diǎn)之間的鏈接為一項(xiàng)隨機(jī)任務(wù)，特別是對(duì)于大型社交網(wǎng)絡(luò)而言，該問題至關(guān)重要，這是由于人們可以從這些社交網(wǎng)絡(luò)的預(yù)測(cè)列表中剔除許多候選鏈接。Lichtenwalter 等[17]認(rèn)為這就是如果2 個(gè)節(jié)點(diǎn)之間最多相距2 個(gè)跳點(diǎn)，則大多數(shù)鏈路預(yù)測(cè)算法都認(rèn)為這2 個(gè)節(jié)點(diǎn)之間有潛在鏈接的原因。故本文認(rèn)為2 個(gè)節(jié)點(diǎn)鏈接的預(yù)測(cè)問題可以轉(zhuǎn)化為預(yù)測(cè)社會(huì)群體中源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)之間鏈接的問題。例如社會(huì)群體中的節(jié)點(diǎn)存在相似興趣、利益或目標(biāo)，則源節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)社會(huì)群體可能存在更多共同興趣（即鏈接），則這2 個(gè)節(jié)點(diǎn)之間創(chuàng)建新鏈接的概率較高。社交網(wǎng)絡(luò)中最簡單的社會(huì)群體為單節(jié)點(diǎn)，在單個(gè)關(guān)系的無向網(wǎng)絡(luò)中，單節(jié)點(diǎn)社群的源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)之間至多存在一種關(guān)系。要對(duì)這2 個(gè)節(jié)點(diǎn)之間的鏈接進(jìn)行預(yù)測(cè)，其之間就必須存在這種單一關(guān)系。為了對(duì)社交網(wǎng)絡(luò)中的新鏈接進(jìn)行預(yù)測(cè)，應(yīng)考慮更復(fù)雜的社群，這些社群內(nèi)部至少要存在2 個(gè)節(jié)點(diǎn)，且隨著社群中節(jié)點(diǎn)數(shù)量的增多及源節(jié)點(diǎn)與該社群間關(guān)系的增多，源節(jié)點(diǎn)與社群中目標(biāo)節(jié)點(diǎn)之間創(chuàng)建新鏈接的概率也會(huì)增大。

圖1 單個(gè)關(guān)系無向網(wǎng)絡(luò)中節(jié)點(diǎn)與社群間可能存在的交互關(guān)系

單個(gè)關(guān)系無向網(wǎng)絡(luò)中某節(jié)點(diǎn)和某社群間可能的相關(guān)性如圖1 所示。圖1 中第一層顯示了節(jié)點(diǎn)和社群的最簡單關(guān)系，該層中單個(gè)關(guān)系無向網(wǎng)絡(luò)中僅存在一個(gè)鏈接，如時(shí)刻t的快照所示。時(shí)刻t的快照表示一種網(wǎng)絡(luò)結(jié)構(gòu)，鏈路預(yù)測(cè)算法用該結(jié)構(gòu)預(yù)測(cè)下個(gè)快照中的新鏈接。如前所述，每2 個(gè)實(shí)體間至少應(yīng)有一個(gè)鏈接，這樣才能預(yù)測(cè)下個(gè)快照中的鏈接。圖1 中的2 個(gè)實(shí)體分別為左側(cè)的源節(jié)點(diǎn)和右側(cè)的目標(biāo)社群。第一層中未保留鏈接來預(yù)測(cè)網(wǎng)絡(luò)中的下一快照。第二層的目標(biāo)社群由2 個(gè)節(jié)點(diǎn)組成，該層中時(shí)刻t的快照表示源節(jié)點(diǎn)與社群間的關(guān)聯(lián)，時(shí)刻t+1 的快照表示可創(chuàng)建的可能鏈接（虛線）。由于所有鏈接和節(jié)點(diǎn)的權(quán)重相同，因此圖1 中未描繪其他可能的同構(gòu)交互。第二層中有4 種不同的關(guān)系，因此存在4 種不同的可能鏈接。第四層是本文關(guān)注點(diǎn)的重點(diǎn)，其群體結(jié)構(gòu)為三角關(guān)系，左右兩部分分別有2 個(gè)可能的鏈接。本文將講述如何根據(jù)第四層的子圖結(jié)構(gòu)來預(yù)測(cè)鏈接。而第三層中為最常見的社交網(wǎng)絡(luò)結(jié)構(gòu)，在此不做贅述。圖1 所示四大層次并不是如今算力所能解決的，還可以考慮更多節(jié)點(diǎn)、更復(fù)雜的群體結(jié)構(gòu)，但由于找出這些的群體成本更高，因此本文未考慮更復(fù)雜的層次，僅示例社交網(wǎng)絡(luò)中兩實(shí)體間更復(fù)雜的交互層次交互關(guān)系，如圖2所示。

圖2 社交網(wǎng)絡(luò)中兩實(shí)體間更復(fù)雜的交互層次交互關(guān)系

圖1 中的第四層定義了本文所述方法，具有一個(gè)節(jié)點(diǎn)和一個(gè)三角關(guān)系，且三角關(guān)系中至少存在一條公共邊。第四層有2 個(gè)子圖(a)和(b)。由于子圖(b)的結(jié)構(gòu)屬性多于子圖(a)，而結(jié)構(gòu)屬性越多，預(yù)測(cè)出正確鏈接的機(jī)會(huì)就越大，故子圖(b)價(jià)值更大。為證明這一觀點(diǎn)，本文對(duì)比了根據(jù)子圖(a)與子圖(b)所預(yù)測(cè)的鏈接的準(zhǔn)確性。首先從社交網(wǎng)絡(luò)樣本中提取出子圖(a)和子圖(b)，然后考察了作為潛在鏈接的所有潛在鏈接（即圖1 中的虛線），最后根據(jù)精度度量對(duì)比了這2 個(gè)子圖所預(yù)測(cè)出的鏈接質(zhì)量。對(duì)比結(jié)果顯示本文觀點(diǎn)是正確的，即如果使用更多的結(jié)構(gòu)屬性，可以更正確地預(yù)測(cè)鏈接。Huang[31]的實(shí)驗(yàn)也證實(shí)了該結(jié)論，具體遍歷與循環(huán)數(shù)計(jì)算方式參考文獻(xiàn)[31]。因此，根據(jù)黃璐等[32]提出的概率模型，子圖(b)中僅有一條邊不存在的概率要大于子圖(a)中2 個(gè)鏈接都不存在的概率。本文對(duì)圖1 的其他層也進(jìn)行了同樣的實(shí)驗(yàn)，并將其結(jié)果與第四層結(jié)果進(jìn)行了對(duì)比，發(fā)現(xiàn)第四層中的子圖結(jié)構(gòu)更有利于社交網(wǎng)絡(luò)情景中的鏈路預(yù)測(cè)，故本文用第四層的子圖結(jié)構(gòu)來進(jìn)行社交網(wǎng)絡(luò)鏈路預(yù)測(cè)。

算法1 描述了SE-ACO 算法的具體過程，其目的是由社交網(wǎng)絡(luò)在時(shí)刻t的快照找出圖1 中子圖(a)與子圖(b)，然后預(yù)測(cè)這些子圖中在時(shí)刻t+1 的快照的潛在鏈接（即圖1 中的虛線鏈接）。接下來，根據(jù)蟻群優(yōu)化算法找出的社交網(wǎng)絡(luò)中的三角關(guān)系。找到三角關(guān)系后，本文試圖根據(jù)這些三角關(guān)系找出圖1中的子圖(a)與子圖(b)。由于某些鏈接在多個(gè)子圖結(jié)構(gòu)中是共用的，故其評(píng)分會(huì)更高。最后，本文按評(píng)分降序排列得出預(yù)測(cè)鏈接的列表。

算法1SE-ACO 算法

輸入三角關(guān)系triangles(G)

輸出預(yù)測(cè)鏈接result ←result+link

3.2 基于改進(jìn)蟻群優(yōu)化算法定位三角關(guān)系的模型構(gòu)建

為了找出三角關(guān)系，本文對(duì)蟻群優(yōu)化算法進(jìn)行了改進(jìn)，與原始蟻群優(yōu)化算法的區(qū)別主要有以下幾點(diǎn)。

1) 假設(shè)初始狀態(tài)下螞蟻沒有家，這表示所有螞蟻在一開始時(shí)是分散在社交網(wǎng)絡(luò)的各個(gè)節(jié)點(diǎn)中的。

2) 與原始蟻群優(yōu)化算法（如式(1)所示）相反，SE-ACO 算法中的螞蟻更傾向于選擇信息素含量較低的路徑。這一特性使螞蟻能夠有更高的概率對(duì)社交網(wǎng)絡(luò)圖上未曾勘探過的部分進(jìn)行探索。螞蟻k由節(jié)點(diǎn)i移動(dòng)至節(jié)點(diǎn)j的概率如式(6)所示，其中，τ為對(duì)應(yīng)邊的信息素含量；α為基本參數(shù)，本文設(shè)α=1。與式(1)不同，即SE-ACO算法與傳統(tǒng)蟻群優(yōu)化算法的區(qū)別，式(6)令β=0，且其兩者圖中的信息素含量成反比。如果給釋放的信息素一個(gè)負(fù)值系數(shù)，則螞蟻移動(dòng)與信息素之間為正相關(guān)關(guān)系。

3) 食物（即解）呈現(xiàn)為三角關(guān)系，而螞蟻的目標(biāo)是找出三角關(guān)系。由于每個(gè)三角關(guān)系中都存在3 個(gè)節(jié)點(diǎn)，而螞蟻擁有如圖3 所示的特殊記憶力，故螞蟻在社交網(wǎng)絡(luò)圖上的每次移動(dòng)均會(huì)記錄在其記憶中。如果記憶存在已滿，則將數(shù)據(jù)寫入先前的記憶單元內(nèi)（圖3 中數(shù)字表示螞蟻循環(huán)覆蓋的特殊記憶力，箭頭代表循環(huán)覆蓋的方向），但首先要檢驗(yàn)準(zhǔn)備寫入的數(shù)據(jù)是否等同于先前的記憶單元，如果相等，則認(rèn)為找到了三角關(guān)系。

圖3 蟻群優(yōu)化算法中螞蟻的記憶結(jié)構(gòu)圖

4) 令所有邊上的信息素的初始數(shù)量均等于一個(gè)單位，如果信息素屬于已找出的三角關(guān)系中的邊，則邊上的信息素將增加。每當(dāng)發(fā)現(xiàn)一個(gè)三角關(guān)系時(shí)，該三角關(guān)系中所有邊上的信息素將增加一個(gè)單位，SE-ACO 算法中找到食物（即解）的方法為找出社交網(wǎng)絡(luò)圖中的三角關(guān)系。

5) 各邊所釋放的信息素不會(huì)消退。

6) 螞蟻有死亡屬性。鑒于該特性，螞蟻不會(huì)勘探社交網(wǎng)絡(luò)圖中已訪問過的部分，整個(gè)社交網(wǎng)絡(luò)圖都已被充分勘探后，由于不需要做進(jìn)一步勘探，故所有螞蟻都會(huì)死亡。螞蟻死亡的條件如下：之前已勘探過的任意邊均不含有初始信息素；困在2 個(gè)節(jié)點(diǎn)孤島或邊緣節(jié)點(diǎn)中；螞蟻的周圍環(huán)境都充滿了信息素。

使用SE-ACO 算法進(jìn)行三角關(guān)系查找的具體過程如算法2 所示。首先，創(chuàng)建一定數(shù)量的螞蟻并將它們隨機(jī)放置于社交網(wǎng)絡(luò)節(jié)點(diǎn)中。由于螞蟻會(huì)死亡，故螞蟻的初始數(shù)量一般為社交網(wǎng)絡(luò)圖中節(jié)點(diǎn)數(shù)量的10～20 倍，且在移動(dòng)2 次或3 次后，會(huì)有將近一半的螞蟻死亡，而當(dāng)所有螞蟻死亡或迭代次數(shù)超過特定次數(shù)后，算法停止。在大多數(shù)網(wǎng)絡(luò)中，算法2 的平均迭代次數(shù)為10。每次迭代時(shí)，新節(jié)點(diǎn)被螞蟻選中的概率如式(6)所示，同時(shí)檢查網(wǎng)絡(luò)中是否發(fā)現(xiàn)新的三角關(guān)系，如發(fā)現(xiàn)則將該三角關(guān)系中所有邊的信息素增加一個(gè)單位，然后將該三角關(guān)系加入已找到的三角關(guān)系列表中。每次迭代時(shí)均檢查螞蟻的健康狀況，如果符合死亡條件中的任一條件，則該螞蟻死亡。

算法2SE-ACO 算法尋找三角關(guān)系

輸入初始化信息素initialize pheromone(E)

輸出三角關(guān)系triangles(G)

Latany 等[33]在大型低權(quán)值網(wǎng)絡(luò)中引入了一種新型三角計(jì)算算法，并使用Tsourakakis 等[34]所提特征三角形算法進(jìn)行三角關(guān)系計(jì)算。劉樹新等[35]所述三角計(jì)算方法的應(yīng)用之一為鏈路預(yù)測(cè)，其理念為社交網(wǎng)絡(luò)中朋友的朋友也是朋友的概率較大，故能生成最多三角關(guān)系的鏈接即是鏈路預(yù)測(cè)的最佳候選鏈接，這一理念與Newman 等[36]所提的公共鄰點(diǎn)算法非常接近。由于鏈路預(yù)測(cè)不需要找出社交網(wǎng)絡(luò)圖中三角關(guān)系的確切數(shù)量，故Newman 等[36]所提的公共鄰點(diǎn)算法并未找出社交網(wǎng)絡(luò)圖中三角關(guān)系的確切數(shù)量。要在大型社交網(wǎng)絡(luò)圖中找出三角關(guān)系的確切數(shù)量非常耗時(shí)，且成本很高。本文將改進(jìn)蟻群優(yōu)化算法用于查找三角關(guān)系，且將其應(yīng)用于MapReduce 框架（一種高度并行的分布式大規(guī)模數(shù)據(jù)處理框架）中[37]，這提升了算法的可擴(kuò)展性。如前所述，用于查找三角關(guān)系的所述方法的時(shí)間復(fù)雜度為O(n)。邊上的信息素也可用于圖形分區(qū)，這意味著信息素含量較低的邊為圖形分區(qū)的最佳候選點(diǎn)。而邊上所釋放的信息素也可用于確定節(jié)點(diǎn)的中心性，節(jié)點(diǎn)所連接的具有較多信息素的邊越多，該節(jié)點(diǎn)的中心性越強(qiáng)[38]。

3.3 基于三角關(guān)系進(jìn)行預(yù)測(cè)鏈接

本文根據(jù)上文中找出的三角關(guān)系來進(jìn)行預(yù)測(cè)鏈接（如算法3 所示）。首先，確定已找出三角關(guān)系節(jié)點(diǎn)的所有鄰點(diǎn)，然后檢驗(yàn)每個(gè)鄰居節(jié)點(diǎn)是否屬于圖1 中子圖(a)或子圖(b)中的一種。由于子圖(b)優(yōu)于子圖(a)，因此如果社交網(wǎng)絡(luò)圖不是稀疏的，僅考察子圖(b)就足夠了。如果找出了一定數(shù)量的子圖(a)或(b)，則這些子圖中不存在的鏈接將被視為潛在鏈接。對(duì)于每個(gè)預(yù)測(cè)鏈接，可根據(jù)三角關(guān)系節(jié)點(diǎn)邊上的信息素?cái)?shù)量及它們所屬的子圖類型來計(jì)算其分?jǐn)?shù)。信息素越高，則分?jǐn)?shù)越高，子圖(b)中的鏈接的分?jǐn)?shù)較高。預(yù)測(cè)鏈接在某些子圖結(jié)構(gòu)間可能是重疊的，且要預(yù)測(cè)多次。每次進(jìn)行一次鏈路預(yù)測(cè)，其分?jǐn)?shù)就越高。2 個(gè)子圖(b)之間的重疊鏈接如圖4所示，由于該鏈接會(huì)預(yù)測(cè)2 次，故該鏈接的分?jǐn)?shù)也較高。

算法3SE-ACO 算法的鏈路預(yù)測(cè)

圖4 2 個(gè)子圖(b)之間的重疊鏈接

4 實(shí)驗(yàn)驗(yàn)證與結(jié)果分析

首先對(duì)數(shù)據(jù)集及其特征進(jìn)行介紹，然后將SE-ACO 算法在這些數(shù)據(jù)集上的評(píng)估結(jié)果與其他非監(jiān)督式結(jié)構(gòu)鏈路預(yù)測(cè)算法進(jìn)行比較。使用Top-n精度和接收器操作特性（ROC,receiver operating characteristic）曲線下面積及精確率?召回率曲線等方法進(jìn)行評(píng)估，最后根據(jù)已執(zhí)行的不同評(píng)估指標(biāo)對(duì)算法結(jié)果進(jìn)行了討論。

4.1 數(shù)據(jù)說明

各數(shù)據(jù)集在時(shí)刻t和時(shí)刻t+1 的統(tǒng)計(jì)信息分別如表1 和表2 所示。SE-ACO 算法使用了時(shí)刻t的數(shù)據(jù)集來預(yù)測(cè)時(shí)刻t+1 的鏈接。其中節(jié)點(diǎn)和邊的數(shù)量表示社交網(wǎng)絡(luò)圖中存在多少個(gè)節(jié)點(diǎn)和邊，平均聚類系數(shù)表示三元組變成三角關(guān)系的傾向性度量，網(wǎng)絡(luò)的聚類系數(shù)越高每個(gè)圖中生成的鏈接越多。相稱系數(shù)[39]是進(jìn)行相似性度量的關(guān)鍵參數(shù)，度數(shù)相同的節(jié)點(diǎn)比其他節(jié)點(diǎn)更容易彼此關(guān)聯(lián)，該度量范圍為[?1,1]。相較于相稱系數(shù)接近?1 的網(wǎng)絡(luò)，在相稱系數(shù)接近1 的網(wǎng)絡(luò)中度數(shù)相同的節(jié)點(diǎn)彼此的關(guān)聯(lián)度最高。強(qiáng)連通分量（SCC,strongly connected component）表示社交網(wǎng)絡(luò)圖中的子圖，由于大型網(wǎng)絡(luò)的直徑計(jì)算非常耗時(shí)，故本文使用Lichtenwalter 等[40]中的近似算法來估算網(wǎng)絡(luò)直徑，使用五折交叉驗(yàn)證法來評(píng)估所提架構(gòu)的性能。使用Rapidminer 數(shù)據(jù)挖掘工具隨機(jī)選取各用戶評(píng)級(jí)數(shù)據(jù)的20%作為測(cè)試集，并將剩余80%的用戶數(shù)據(jù)作為訓(xùn)練集。

表1 各數(shù)據(jù)集在時(shí)刻t 的統(tǒng)計(jì)信息

表2 各數(shù)據(jù)集在時(shí)刻t+1 的統(tǒng)計(jì)信息

本文使用國內(nèi)外共9 個(gè)相關(guān)數(shù)據(jù)集對(duì)SE-ACO算法進(jìn)行驗(yàn)證，并利用Python 工具從新浪微博、Twitter 與Facebook 的AP（Iapplication programming interface）端口選取10 個(gè)節(jié)點(diǎn)作為初始節(jié)點(diǎn)，爬取真實(shí)用戶數(shù)據(jù)集作為實(shí)驗(yàn)仿真的基礎(chǔ)數(shù)據(jù)，爬取時(shí)間為2019 年1 月1 日—6 月30 日，數(shù)據(jù)集分別包含37 864 個(gè)新浪微博節(jié)點(diǎn)、49 822 個(gè)Twitter 節(jié)點(diǎn)和38 942 個(gè)Facebook 節(jié)點(diǎn)，記為時(shí)刻t；爬取時(shí)間為2019 年7 月1 日—12 月31 日，數(shù)據(jù)集分別包含42 093 個(gè)新浪微博節(jié)點(diǎn)、55 891 個(gè)Twitter 節(jié)點(diǎn)和42 965 個(gè)Facebook 節(jié)點(diǎn)，記為時(shí)刻t+1。除此之外，本文認(rèn)為如果科研論文作者的合作網(wǎng)絡(luò)、網(wǎng)站之間的信息分享網(wǎng)絡(luò)與專利合作網(wǎng)絡(luò)等都應(yīng)納入考察范圍。但由于數(shù)據(jù)的可得性問題，故本文使用以下數(shù)據(jù)集進(jìn)行分析。hep-ph 與astro-ph 表示科研論文作者合作網(wǎng)絡(luò)，其中，hep-ph 為物理現(xiàn)象學(xué)領(lǐng)域，astro-ph 為天體物理學(xué)領(lǐng)域[2]。2004 年— 2006 年撰寫論文的樣本為時(shí)刻t，2007 年—2009 年撰寫的論文的樣本為時(shí)刻t+1。對(duì)上述2 個(gè)數(shù)據(jù)集，本文僅使用核圖，且使用撰寫3 篇論文及以上的作者作為節(jié)點(diǎn)。dblp-collab 和dblp-cite 均來自于DBLP 計(jì)算機(jī)科學(xué)文獻(xiàn)[17]。其中，dblp-collab 為計(jì)算機(jī)科學(xué)作者合作網(wǎng)絡(luò)，該網(wǎng)絡(luò)中的時(shí)刻t為2001 年— 2003 年的作者合作，快照時(shí)刻t+1 為2004 年—2005 年的作者合作；dblp-cite 表示相互引用的計(jì)算科學(xué)論文網(wǎng)絡(luò)，該網(wǎng)絡(luò)的時(shí)刻t為1997 年—1998 年，時(shí)刻t+1 為1999年—2000 年。Polblogs 為2004 年的美國政治網(wǎng)絡(luò)及網(wǎng)站間的鏈接[41]，將該網(wǎng)絡(luò)圖中的后20%劃分為時(shí)刻t+1，其余則為時(shí)刻t。patent-colla 為節(jié)點(diǎn)為專利作者的數(shù)據(jù)集，其鏈接表示專利作者間的合作[42]。時(shí)刻t為2006 年—2007 年作者的合作，時(shí)刻t+1為2008 年—2009 年的合作，并將所有數(shù)據(jù)以csv格式保存在MySQL 數(shù)據(jù)庫中以便進(jìn)行數(shù)據(jù)處理。對(duì)每一個(gè)社交網(wǎng)絡(luò)數(shù)據(jù)集，采用80%的數(shù)據(jù)進(jìn)行訓(xùn)練，剩余的20%用于測(cè)試。

4.2 實(shí)驗(yàn)結(jié)果

為體現(xiàn)SE-ACO 算法的優(yōu)越性，本文將其與10 種不同的非監(jiān)督式結(jié)構(gòu)鏈路預(yù)測(cè)算法進(jìn)行了對(duì)比。這10 種算法的簡要描述如下。

1) 公共鄰點(diǎn)（CN,common neighbor）。令Γ(x)表示節(jié)點(diǎn)x的鄰點(diǎn)數(shù)，2 個(gè)領(lǐng)點(diǎn)具有的公共鄰點(diǎn)越多，則鏈路預(yù)測(cè)任務(wù)[36]的分?jǐn)?shù)越高，如式(7)所示。

2) AA（Adamic-Adar）算法。Adamic 等[41]設(shè)計(jì)了一種用于檢測(cè)2 個(gè)網(wǎng)頁相似度的度量，這種度量也可用于度量社交網(wǎng)絡(luò)中兩節(jié)點(diǎn)的相似度，具體如式(8)所示。其中，文獻(xiàn)表明度數(shù)較小的2 個(gè)節(jié)點(diǎn)的公共鄰點(diǎn)比其他節(jié)點(diǎn)更有價(jià)值。

3) Jaccard 系數(shù)算法。該相似度度量類似于尋找公共鄰點(diǎn)，不同之處在于，就此度量方法而言，如果2 個(gè)節(jié)點(diǎn)有較多的公共鄰點(diǎn)和較少的非公共鄰點(diǎn)，則它們的相似度較大[8]，如式(9)所示。

4) 優(yōu)先連接（PA,preferential attachment）算法。節(jié)點(diǎn)度數(shù)是預(yù)測(cè)新鏈接的關(guān)鍵屬性。度數(shù)較高的2 個(gè)節(jié)點(diǎn)在未來彼此交互的可能性越大[9-11]，這一理論可由式(10)推導(dǎo)得出。

5) Katz（Katz 指數(shù)）算法。該度量根據(jù)兩節(jié)點(diǎn)之間的路徑數(shù)及其長度來確定節(jié)點(diǎn)之間的相似度[43]，如式(11)所示。

6) Distance（距離）算法。使用距離算法進(jìn)行相似度度量時(shí)，距離越近的兩節(jié)點(diǎn)關(guān)聯(lián)的機(jī)會(huì)越高，因此，距離2 個(gè)跳點(diǎn)的節(jié)點(diǎn)，其彼此關(guān)聯(lián)的概率最大[3]。在該度量算法中，距源節(jié)點(diǎn)具有相同數(shù)量跳點(diǎn)的節(jié)點(diǎn)與源節(jié)點(diǎn)形成的鏈接都具有相同的打分。

7) RP（Rooted PageRank）算法。該算法基于隨機(jī)游走，由PageRank[44]算法改寫而成，并被文獻(xiàn)[2]用于鏈路預(yù)測(cè)，如式(12)所示。其中，Hx,y（節(jié)點(diǎn)x,y的首次接觸時(shí)間）為隨機(jī)游走者由節(jié)點(diǎn)x移動(dòng)至節(jié)點(diǎn)y所需的步數(shù)。由于擊中時(shí)間不對(duì)稱，因此Hy,x的首次接觸時(shí)間也是不同的。式(12)中的πx與πy均為平穩(wěn)概率，為防止隨機(jī)游走者距離起始節(jié)點(diǎn)x太遠(yuǎn)，這里使用了概率α，即隨機(jī)游走者返回至起始節(jié)點(diǎn)的概率為α，移動(dòng)至鄰點(diǎn)的概率為1?α。本文實(shí)驗(yàn)設(shè)α=0.5。

8) SR（SimRank）算法。在該相似度度量算法中，2 個(gè)節(jié)點(diǎn)越相似，則分?jǐn)?shù)越高。該算法的主要思想是根據(jù)社交網(wǎng)絡(luò)的趨同性[11]進(jìn)行預(yù)測(cè)。SimRank算法[45]可由式(13)～式(15)表示，如果2 個(gè)節(jié)點(diǎn)與較多的相似節(jié)點(diǎn)有關(guān)聯(lián)，則這2 個(gè)結(jié)果較相似。式(14)中的γ取值為[0,1]，本文實(shí)驗(yàn)中，設(shè)γ=0.8。

9) PF（PropFlow）算法[46]。該算法為一種限制性隨機(jī)游走預(yù)測(cè)器，是橫向優(yōu)先搜索的變形，本文實(shí)驗(yàn)中僅考慮了最大長度為5 的路徑。

10) 資源分配（RA,resource allocation）算法。該算法是基于復(fù)雜網(wǎng)絡(luò)中的資源分析理念提出的[4]。其中，節(jié)點(diǎn)x可借助于鄰點(diǎn)向節(jié)點(diǎn)y發(fā)送資源。簡化情況下，每個(gè)節(jié)點(diǎn)僅向目標(biāo)節(jié)點(diǎn)發(fā)送一個(gè)單位的資源，且該資源將發(fā)送至該節(jié)點(diǎn)的所有鄰節(jié)點(diǎn)。節(jié)點(diǎn)x和y的相似度為它從節(jié)點(diǎn)x所得到的資源數(shù)量。參考文獻(xiàn)[4]中的做法，使用式(16)中的deg(z)表示節(jié)點(diǎn)z的度數(shù)。

本文在Python 環(huán)境中分別使用Scipy[47]、Numpy[48]和LPmade 工具包[40]執(zhí)行上述算法。用于計(jì)算鏈接精度和召回率的真正例（TP,true positive）、真負(fù)例（TN,true negative）、假正例（FP,false positive）和假負(fù)例（FN,false negative）的定義如表3 所示。而召回率（Recall）、精確率（Precision）、真正率（TPR,true positive rate）和假正率（FPR,false positive rate）分別如式(17)～式(20)所示。

表3 鏈路預(yù)測(cè)中TP、TN、FP 和FN 的定義

根據(jù)文獻(xiàn)[3]進(jìn)行第一次評(píng)估，將每個(gè)算法的精度與隨機(jī)預(yù)測(cè)器的精度進(jìn)行比較，其中隨機(jī)預(yù)測(cè)器的精度為圖形時(shí)刻t+1 所創(chuàng)建新鏈接的數(shù)量除以圖形時(shí)刻t消失鏈接的數(shù)量。每個(gè)數(shù)據(jù)集中隨機(jī)預(yù)測(cè)器的精度如表4 所示。該指標(biāo)也稱為Top-n精度，其中n表示時(shí)刻t節(jié)點(diǎn)之間增加的新鏈接。在本文實(shí)驗(yàn)中，所有算法都進(jìn)行了100 次迭代實(shí)驗(yàn)，并取平均值作為預(yù)測(cè)精度的實(shí)驗(yàn)結(jié)果，且各組方差的分布區(qū)間為[1.033,3.784]。

根據(jù)優(yōu)于隨機(jī)預(yù)測(cè)器的倍數(shù)，SE-ACO 算法的Top-n與其他算法的精度比較情況如表5 所示，n為大于或等于1 的正整數(shù)，精度會(huì)隨n先變大再變小。對(duì)于每個(gè)預(yù)測(cè)器，給定數(shù)字表示優(yōu)于隨機(jī)預(yù)測(cè)器的倍數(shù)。例如新浪微博數(shù)據(jù)集上SE-ACO 算法的結(jié)果為42.68，這表明該算法的精度要優(yōu)于隨機(jī)預(yù)測(cè)器42.68 倍，因此SE-ACO 算法在新浪微博中的精度為24.69%，即0.578 4%與42.68 的乘積。表5中的SR 和RP 用于大型數(shù)據(jù)庫時(shí)非常耗時(shí)，故使用少數(shù)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)時(shí)未使用這些算法。對(duì)于Twitter 數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果中AA 預(yù)測(cè)器效果最佳的原因，本文認(rèn)為這是由于AA 預(yù)測(cè)器為基于節(jié)點(diǎn)相似度進(jìn)行預(yù)測(cè)的，其中度數(shù)較小的2 個(gè)節(jié)點(diǎn)的公共鄰點(diǎn)比其他節(jié)點(diǎn)更有價(jià)值。而由于Twitter 為主要發(fā)布短文本的社交網(wǎng)絡(luò)平臺(tái)，故節(jié)點(diǎn)之間相似度本身較強(qiáng)，預(yù)測(cè)精度相對(duì)較高。

本文實(shí)驗(yàn)中，由于使用SE-ACO 算法預(yù)測(cè)列表在每次運(yùn)行時(shí)都有可能不同，故設(shè)置評(píng)估結(jié)果為迭代100 次運(yùn)行后的平均值，運(yùn)行結(jié)果的標(biāo)準(zhǔn)差為1.328。SE-ACO 算法考慮了圖1 中的子圖(a)與子圖(b)。

螞蟻的初始數(shù)量取決于圖的節(jié)點(diǎn)數(shù)，如果螞蟻數(shù)量不足，則所找到三角關(guān)系可能較少，從而降低了SE-ACO 算法的評(píng)估結(jié)果。實(shí)驗(yàn)表明，當(dāng)螞蟻的初始數(shù)量設(shè)定為網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)的 10～20 倍時(shí)，SE-ACO 算法的運(yùn)行效率最佳。本文實(shí)驗(yàn)將螞蟻的初始數(shù)量設(shè)為各數(shù)據(jù)集節(jié)點(diǎn)數(shù)的10 倍。為進(jìn)一步比較算法的可擴(kuò)展性，本文比較了不同網(wǎng)絡(luò)中基于節(jié)點(diǎn)數(shù)量的算法的運(yùn)行時(shí)間，如圖5 所示。由圖5可知，運(yùn)行效率最高的算法為CN 算法，而SE-ACO算法的運(yùn)行時(shí)間接近CN 算法，這表明它可用于大型數(shù)據(jù)集的預(yù)測(cè)。且各預(yù)測(cè)器在不同數(shù)據(jù)集的表現(xiàn)基本一致，故在此不再贅述。

表4 幾種算法在數(shù)據(jù)集的精度對(duì)比

其他評(píng)估方法為ROC 面積[49]和精確率?召回率曲線方法[50]。各算法根據(jù)ROC 曲線下面積的評(píng)估結(jié)果如表6 所示；新浪微博、hep-ph 和patent-colla數(shù)據(jù)集根據(jù)精確率?召回率曲線下面積所得的評(píng)估結(jié)果如表7 所示。ROC 曲線如圖6(a)～圖6(c)所示，所選的3 個(gè)鏈路預(yù)測(cè)算法在3 個(gè)數(shù)據(jù)集上的精確率?召回率曲線如圖6(d)～圖6(f)所示。結(jié)果表明，在大多數(shù)預(yù)測(cè)器中SE-ACO 算法的精度都高于其他算法，而預(yù)測(cè)器在某幾個(gè)數(shù)據(jù)集中精度較低的原因是由于數(shù)據(jù)集本身特征所導(dǎo)致（其他預(yù)測(cè)器實(shí)驗(yàn)所得結(jié)果在此不再贅述）。

表5 SE-ACO 算法的Top-n 與其他算法的精度比較情況

圖5 算法運(yùn)行時(shí)間對(duì)比

表6 基于ROC 曲線下面積的不同算法比較

表7 基于精確率?召回率曲線下面積的不同算法比較

圖6 基于ROC 與精確率–召回率曲線的算法比較結(jié)果

表4 表明可用隨機(jī)鏈路預(yù)測(cè)器的性能評(píng)估鏈路預(yù)測(cè)算法的總體性能，即如果隨機(jī)預(yù)測(cè)器在某些網(wǎng)絡(luò)上表現(xiàn)良好，則鏈路預(yù)測(cè)算法在該網(wǎng)絡(luò)上的性能也較好。另一方面，隨機(jī)預(yù)測(cè)器在聚類系數(shù)較高、密度較高且圖形直徑較短的網(wǎng)絡(luò)上的性能較好（如表2 所示）。Katz 指數(shù)性能取決于網(wǎng)絡(luò)直徑，即在直徑較短的網(wǎng)絡(luò)中，該算法有著更好的Top-n精度（如表2 和表5 所示）。AA 算法與CN 算法均使用了公共節(jié)點(diǎn)數(shù)來測(cè)量相似度，但AA 算法幾乎在所有數(shù)據(jù)集上均優(yōu)于CN 算法。AA 算法在聚類系數(shù)較高的網(wǎng)絡(luò)中有著較好的性能，其原因是在這些算法中，能將更多的三元組轉(zhuǎn)化為三角關(guān)系的鏈接為價(jià)值較高的鏈接，其得分也較高（如表2 和表6 所示）。SE-ACO 算法在 dblp-collab、dblp-cite 和patent-collab 數(shù)據(jù)集上的結(jié)果較好，其主要原因?yàn)樵摂?shù)據(jù)集的SCC 值較高，因此使用節(jié)點(diǎn)度數(shù)和路徑長度方法的性能較低。在SE-ACO 算法中，螞蟻開始時(shí)是隨機(jī)分散在社交網(wǎng)絡(luò)的各個(gè)部分，更多地利用網(wǎng)絡(luò)的結(jié)構(gòu)特性，因此SE-ACO 算法在出度較高的網(wǎng)絡(luò)上有著較好的性能。圖6 表示SE-ACO 算法的鏈路預(yù)測(cè)精度較高，這是由于根據(jù)圖1 中子圖(b)所預(yù)測(cè)的鏈接有較高的分?jǐn)?shù)，這些鏈接位于預(yù)測(cè)列表的頂部，但根據(jù)子圖(a)所預(yù)測(cè)的結(jié)果則較差。表6 中的Distance 算法在所有數(shù)據(jù)集上所得結(jié)果均一致，這是因?yàn)樵撍惴▽⑺A(yù)測(cè)的所有鏈接都關(guān)聯(lián)了相同的分?jǐn)?shù)。最后本文將表5 與表7 中的結(jié)果進(jìn)行對(duì)比可知，如果這些算法用Top-n精度得出的性能較好，則其用精確度–召回率曲線下面積所得出的性能也較好。

為評(píng)估SE-ACO 算法在大型公開標(biāo)準(zhǔn)數(shù)據(jù)集中的性能，本文選擇了3 個(gè)數(shù)據(jù)集：MovieLens 1M、MovieLens 10M 基準(zhǔn)數(shù)據(jù)集[51]和Epinion 數(shù)據(jù)集[52]，結(jié)果如圖7 所示。由圖7 可知，在大型公開標(biāo)準(zhǔn)數(shù)據(jù)集中，SE-ACO 算法較其他算法仍然可以得到較高的精度，這也再次證明了SE-ACO 算法的科學(xué)性。

圖7 公開標(biāo)準(zhǔn)數(shù)據(jù)集中基于ROC 曲線下面積的幾種算法的比較結(jié)果

5 結(jié)束語

本文提出了一種基于子圖演化與改進(jìn)蟻群優(yōu)化算法的社交網(wǎng)絡(luò)鏈路預(yù)測(cè)方法。首先在社交網(wǎng)絡(luò)圖中確定特殊子圖；然后研究子圖演化以預(yù)測(cè)圖中的新鏈接，并用蟻群優(yōu)化算法定位特殊子圖；最后本文針對(duì)SE-ACO 算法使用不同網(wǎng)絡(luò)拓?fù)洵h(huán)境與數(shù)據(jù)集進(jìn)行檢驗(yàn)與算法比較。實(shí)驗(yàn)結(jié)論表明，與其他無監(jiān)督社交網(wǎng)絡(luò)預(yù)測(cè)算法相比，SE-ACO 算法在多數(shù)數(shù)據(jù)集上的評(píng)估結(jié)果最好，這表明圖形結(jié)構(gòu)在鏈路預(yù)測(cè)算法中起到重要作用。SE-ACO 算法在大型公開標(biāo)準(zhǔn)數(shù)據(jù)集上的運(yùn)行時(shí)間較短且效果較佳。通過使用SE-ACO 算法，能以高度并行方式進(jìn)行鏈路預(yù)測(cè)。

本文可以從以下幾個(gè)方面進(jìn)一步展開研究。1)由于數(shù)據(jù)可得性，本文與眾多文獻(xiàn)[7,44]一樣，采用若干個(gè)社交網(wǎng)絡(luò)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，這些數(shù)據(jù)集往往具有不同的量級(jí)，這會(huì)在一定程度上影響實(shí)驗(yàn)結(jié)果[45]。因此，在未來的研究中，有必要使用不同場(chǎng)景、不同量級(jí)的數(shù)據(jù)集來進(jìn)行社交網(wǎng)絡(luò)中的鏈路預(yù)測(cè)實(shí)驗(yàn)。2) 本文僅包含圖1 所示的2 種子圖結(jié)構(gòu)，未來可以嘗試使用更復(fù)雜的子圖結(jié)構(gòu)進(jìn)行算法改進(jìn)，這能夠使鏈路預(yù)測(cè)算法適合更多的社交網(wǎng)絡(luò)場(chǎng)景。3) 未來可以進(jìn)一步融入其他機(jī)器學(xué)習(xí)和深度學(xué)習(xí)方法進(jìn)行算法改進(jìn)。