顧秋陽，琚春華，吳功興

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

1 引言

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

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

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

步驟1設螞蟻k由社交網絡圖中節(jié)點i遍歷至節(jié)點j的概率為，如式(1)所示。

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

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

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

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

其中，ρ為基本參數。

本文首先以子圖演化的鏈路預測為基礎，在社交網絡圖中確定特殊子圖。然后，研究子圖演化以預測圖中的新鏈接，并用蟻群優(yōu)化算法來定位特殊子圖。最后，本文針對所提方法使用不同的網絡拓撲環(huán)境與數據集進行實驗，以期為社交網絡環(huán)境的優(yōu)化、鏈路的預測、監(jiān)控與追責提供實驗依據；同時也為大眾更好地使用社交網絡提供指導意見。

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

2 文獻回顧

2.1 文獻綜述

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

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

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

2.2 文獻評述

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

基于以上綜述，本文首先提出一種基于子圖演化與蟻群優(yōu)化算法融合的社交網絡鏈路預測方法，以基于子圖演化的鏈路預測為基礎，在社交網絡圖中確定特殊子圖；然后研究子圖演化以預測圖中的新鏈接，并用蟻群優(yōu)化算法定位特殊子圖；最后針對所提方法使用不同網絡拓撲環(huán)境與數據集進行驗證。

3 社交網絡鏈路預測方法設計

3.1 方法設計總體思路

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

圖1 單個關系無向網絡中節(jié)點與社群間可能存在的交互關系

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

圖2 社交網絡中兩實體間更復雜的交互層次交互關系

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

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

算法1SE-ACO 算法

輸入三角關系triangles(G)

輸出預測鏈接result ←result+link

3.2 基于改進蟻群優(yōu)化算法定位三角關系的模型構建

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

1) 假設初始狀態(tài)下螞蟻沒有家，這表示所有螞蟻在一開始時是分散在社交網絡的各個節(jié)點中的。

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

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

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

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

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

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

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

算法2SE-ACO 算法尋找三角關系

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

輸出三角關系triangles(G)

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

3.3 基于三角關系進行預測鏈接

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

算法3SE-ACO 算法的鏈路預測

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

4 實驗驗證與結果分析

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

4.1 數據說明

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

表1 各數據集在時刻t 的統計信息

表2 各數據集在時刻t+1 的統計信息

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

4.2 實驗結果

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

1) 公共鄰點（CN,common neighbor）。令Γ(x)表示節(jié)點x的鄰點數，2 個領點具有的公共鄰點越多，則鏈路預測任務[36]的分數越高，如式(7)所示。

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

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

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

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

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

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

8) SR（SimRank）算法。在該相似度度量算法中，2 個節(jié)點越相似，則分數越高。該算法的主要思想是根據社交網絡的趨同性[11]進行預測。SimRank算法[45]可由式(13)～式(15)表示，如果2 個節(jié)點與較多的相似節(jié)點有關聯，則這2 個結果較相似。式(14)中的γ取值為[0,1]，本文實驗中，設γ=0.8。

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

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

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

表3 鏈路預測中TP、TN、FP 和FN 的定義

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

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

本文實驗中，由于使用SE-ACO 算法預測列表在每次運行時都有可能不同，故設置評估結果為迭代100 次運行后的平均值，運行結果的標準差為1.328。SE-ACO 算法考慮了圖1 中的子圖(a)與子圖(b)。

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

表4 幾種算法在數據集的精度對比

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

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

圖5 算法運行時間對比

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

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

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

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

為評估SE-ACO 算法在大型公開標準數據集中的性能，本文選擇了3 個數據集：MovieLens 1M、MovieLens 10M 基準數據集[51]和Epinion 數據集[52]，結果如圖7 所示。由圖7 可知，在大型公開標準數據集中，SE-ACO 算法較其他算法仍然可以得到較高的精度，這也再次證明了SE-ACO 算法的科學性。

圖7 公開標準數據集中基于ROC 曲線下面積的幾種算法的比較結果

5 結束語

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

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