錢榕,許建婷,張克君,董宏宇,邢方遠
(1.北京電子科技學院網(wǎng)絡空間安全系,北京 100070;2.西安電子科技大學計算機科學與技術學院,陜西 西安 710071)
隨著網(wǎng)絡信息技術的迅速發(fā)展,人類社會進入復雜網(wǎng)絡時代,人們的生產(chǎn)和生活越來越依賴于以Internet、WWW、通信網(wǎng)絡、社會關系網(wǎng)絡、經(jīng)濟網(wǎng)絡等為代表的復雜網(wǎng)絡系統(tǒng)的安全可靠和有效運行。異質網(wǎng)絡從拓撲結構上看擁有不同類型的頂點和不同類型的邊,更加貼近于客觀世界。因此人們對異質網(wǎng)絡進行研究具有現(xiàn)實意義和挑戰(zhàn)性。
鏈接預測是復雜網(wǎng)絡研究的一個重要方向,旨在根據(jù)已知的網(wǎng)絡結構和信息,發(fā)現(xiàn)和還原網(wǎng)絡中丟失的信息,或者預測節(jié)點之間未來可能存在的關系[1]。在現(xiàn)實生活中,鏈接預測已經(jīng)有很多成功的應用,比如推薦系統(tǒng),可以給新用戶推薦興趣相近的朋友,或給用戶推薦其可能感興趣的視頻;再如疫情傳播動力學中,可以還原一些丟失的傳播路徑。隨著異質網(wǎng)絡研究的深入,元路徑思想給異質網(wǎng)絡預測鏈接的研究提供了新的思路?;谠窂降漠愘|網(wǎng)絡鏈接預測能夠考慮不同節(jié)點類型及節(jié)點之間的關系,更好地提取網(wǎng)絡中不同的語義信息,從而大大提高網(wǎng)絡鏈接預測方法結果的精確度。近年來,更多的研究學者將元路徑融入異質網(wǎng)絡的研究中,如將元路徑權重融合到異質網(wǎng)絡的表征學習中[2],將元路徑與圖神經(jīng)網(wǎng)絡結合[3]采樣異質鄰居節(jié)點,使用元路徑高效提取異質網(wǎng)絡的語義信息[4-5]等。因此,將元路徑與隱馬爾可夫模型(HMM,hidden Markov model)結合并應用于異質網(wǎng)絡的預測有著十分重要的理論意義與應用前景。
本文的主要研究工作如下。
1) 提出基于聚簇的一階隱馬爾可夫模型的鏈接預測方法,即C-HMM(1)。將HMM 應用于鏈接預測中,并將數(shù)據(jù)簇的方法應用于 HMM。對k-means 算法在確定初始聚簇中心時進行改進,得到基于距離均方差最小的方法,使簇中心同時滿足到其他簇中心之間的距離之和最大以及與其他所有的簇中心之間距離的均方差最小。
2) 提出基于聚簇的二階隱馬爾可夫模型的鏈接預測方法,即C-HMM(2),并分析了C-HMM(2)在鏈接預測上的有效性。C-HMM(2)在考慮模型當前狀態(tài)的基礎上,又合理地考慮了概率和模型歷史狀態(tài)之間的關聯(lián)性,提高了鏈接預測的準確率。
3) 提出基于最大熵(ME,maximum entropy)的C-HMM(2)的鏈接預測方法,即ME-HMM。通過最大熵模型,在鏈接預測中加入訓練數(shù)據(jù)的特征信息;同時通過C-HMM(2)考慮狀態(tài)轉移概率和觀測值輸出概率和模型歷史狀態(tài)之間的關聯(lián)性,進一步提高了鏈接預測的準確率。
4) 對本文提出的方法與已有的鏈接預測方法進行實驗對比分析。實驗結果表明,本文提出的方法優(yōu)于已有的鏈接預測方法。
本文方法的研究框架如圖1所示,其中C-HMM(1)與C-HMM(2)統(tǒng)稱為C-HMM 方法。
圖1 本文方法的研究框架
基于異質網(wǎng)絡中的鏈路預測問題引起了學者們的廣泛關注,目前基于元路徑的鏈接預測研究十分火熱。
異質網(wǎng)絡[6]是一個帶有對象類型映射函數(shù)? :ν→ Α和鏈接類型映射函數(shù) ψ :ε → R 且的有向圖 G=(ν ,ε),其中ν 和ε 分別表示網(wǎng)絡的節(jié)點集合和鏈接的邊集合,Α 和R分別表示網(wǎng)絡中的節(jié)點類型集合和鏈接類型集合。本文選用的DBLP(digital bibliography &library project)數(shù)據(jù)集中選取了論文、作者、會議3 種類型節(jié)點,以及作者與論文之間的撰寫關系、論文與會議之間的發(fā)表關系等。
元路徑[7]是在異質網(wǎng)絡模式上鏈接兩類節(jié)點的路徑。元路徑 P 定義為的形式,它表示節(jié)點A1和Al+1之間的復合關系其中,Ai為節(jié)點類型,Ri為關系類型,?為關系間的復合算子。在DBLP 數(shù)據(jù)集中,作者與作者合作撰寫論文關系的元路徑可以表示為作者( A)”,如果作者與論文、論文與作者之間沒有任何其他的鏈接關系,則該元路徑可以簡化為“APA”,語義信息為與指定作者合作的作者。圖2為異質網(wǎng)絡DBLP 的常見元路徑。
圖2 異質網(wǎng)絡DBLP 的常見元路徑
鏈路預測技術是研究異質網(wǎng)絡中重要的研究方向之一。郭振宏等[8]提出對不同元路徑綜合網(wǎng)絡的拓撲特征獲得異質和同質數(shù)據(jù),再通過邏輯回歸作為鏈路預測模型。韓忠明等[9]提出基于動態(tài)網(wǎng)絡表示的鏈接預測(DNRLP,dynamic network representation based link prediction)模型,基于連接強度的隨機游走算法模擬網(wǎng)絡的動態(tài)信息擴散,對新時刻下得到的節(jié)點表示通過度量相似度得到預測結果。劉大偉等[10]提出將局部共同鄰居集合根據(jù)全局最短路徑信息進行建模的鏈路預測算法。董鑫等[11]提出基于Boosting 的異質信息網(wǎng)絡鏈路預測方法,通過選擇樣本擇優(yōu)的方式和增設閾值分別對Boosting 算法的訓練速度和防止過擬合方面進行改進,并通過集成學習的思想改進鏈路預測性能。趙妍等[12]提出挖掘有效元路徑來生成帶節(jié)點屬性的子圖,用子圖代表被預測鏈路,用圖核方法計算子圖相似性,再訓練支持向量機得到預測結果。孫誠等[13]提出基于共同鄰居(CN,common neighbor)、路徑和隨機游走的8種常用鏈路預測指標的線性組合作為度量指標,并找到較好的優(yōu)化參數(shù),提出相應的神經(jīng)網(wǎng)絡模型。黃立威等[14]分析了異質信息網(wǎng)絡不同元路徑上不同類型節(jié)點和關系的不同語義,并通過不同元路徑上節(jié)點之間的連接概率進行鏈接預測。
本文選用易于擴展、可用于大型數(shù)據(jù)集且最常用的基于相似性指標的CN 方法[15-16]、能夠獲得大量節(jié)點之間的上下文信息的重啟隨機游走(RWR,restart in random walks)方法[17]、單一的HMM 方法[18],以及近些年學者提出的針對不同類型對象間來凝結關系而重構異質網(wǎng)絡的BRLinks 方法[19]、通過將異質網(wǎng)絡劃分多通道再對其進行圖卷積網(wǎng)絡學習網(wǎng)絡節(jié)點的向量表示的MDGCN(multichannel deep graph convolutional network)方法[20]、將異質網(wǎng)絡關系預測視為PU 學習問題的PURP(positive and unlabeled relationship link prediction)方法[21],在此只簡單介紹CN 和RWR 方法。
1) CN 方法
CN 是最常見的相似性指標之一。CN 指的是2 個節(jié)點之間的公共鄰居節(jié)點。公共鄰居節(jié)點數(shù)目越多,這2 個節(jié)點就越有可能產(chǎn)生鏈接。若節(jié)點x的鄰居節(jié)點集合是 Γ(x),那么節(jié)點x和節(jié)點y的相似性指標CN 為2) RWR 方法
RWR 是在隨機游走方法的基礎上改進得到的,其主要原理是從圖中的某一節(jié)點開始出發(fā),隨機選擇該節(jié)點相鄰節(jié)點的一個或返回開始的節(jié)點。RWR方法有一個重啟概率α,而1 -α則表示移動到相鄰節(jié)點的概率,經(jīng)過多次迭代達到穩(wěn)定狀態(tài)之后結束。RWR 的定義式為
其中,rt=[ri,j]是 n× 1的得分向量,ri,j是節(jié)點j到節(jié)點i的相關度得分;et是 n× 1的初始向量,第i個元素為1,其他為0。
HMM 常用來描述一個含有隱含未知參數(shù)的馬爾可夫過程。在HMM 中,狀態(tài)是不直接可見的,可以通過觀測序列的隨機過程表現(xiàn)出來。HMM 可以用S、 O、π、A、 B 這5 個元素表示。其中,S為隱含狀態(tài),O為可觀測狀態(tài),π 為初始狀態(tài)概率矩陣,A為隱含狀態(tài)轉移概率矩陣,B為觀測狀態(tài)轉移概率矩陣。HMM(1)如圖3 所示。HMM 在研究中被廣泛應用,如用HMM 進行食品安全風險評估[22]、進行人臉特征標注與識別[23]等。
圖3 HMM(1)
1) 數(shù)據(jù)聚簇
由k-means 算法的基本思想[24]可知,選到合理節(jié)點作為初始簇中心的可能性比較小,算法的復雜性也相對增加,不一定能得到理想的聚簇結果。本文了解到有學者通過聚簇分析理論提出了層次和密度聚簇分析方法的航跡關聯(lián)算法[25],提高了目標數(shù)量多且相互位置較近時航跡關聯(lián)的準確性;以及為了改進空間聚簇算法的效率提出了距離代價函數(shù)的概念,利用距離代價最小準則,設計了一個新的k值優(yōu)化算法[26],對空間聚簇算法k-means 算法和k-中心法進行改進等。因此本文也嘗試通過提高聚簇的性能,提出一種基于距離均方差最小的初始聚簇中心方法,思想如下。
一般用對象之間的距離表示相似度[27],首先根據(jù)數(shù)據(jù)集中節(jié)點的相似性矩陣(計算式如式(3)所示),得到具有最大距離的2 個節(jié)點,作為2 個聚簇的初始簇中心。
其中,d(i,j)表示節(jié)點i和節(jié)點j之間的距離,其計算式為
其中,pIij表示第I個節(jié)點從狀態(tài)si到狀態(tài)sj的轉移概率。2 個節(jié)點之間的相似性程度越高,其距離值d越小。其余聚簇中心的確定方式如下:假設需要聚簇的總個數(shù)為k,已經(jīng)得到的初始簇中心的個數(shù)為n,那么第n+1個待確定的簇中心與其他已得到的簇中心的距離為
其中,di,n+1表示第n+1個簇中心與第i個簇中心之間的距離。同時,第n+1個待確定的簇中心節(jié)點需滿足該簇中心到其他所有簇中心之間的距離之和最大,且和其他所有簇中心之間距離的均方差最小,也就是
常用平方誤差作為準則函數(shù),即
其中,Ci表示第i個聚簇,p表示Ci中的一個數(shù)據(jù)節(jié)點(p∈Ci),mi表示Ci的簇中心。
采用改進k-means 進行聚簇,聚簇算法如算法1 所示。
算法1聚簇算法
輸入n 個已標記的數(shù)據(jù)訓練集,聚簇數(shù)目k
輸出滿足函數(shù)收斂的k個聚簇
①用最大似然估計(MLE,maximum likelihood estimate)中的統(tǒng)計公式計算已標記的數(shù)據(jù)訓練集的狀態(tài)轉移概率,計算訓練集的初始狀態(tài)概率,訓練HMM;
② 用式(4)計算節(jié)點之間的距離,構造節(jié)點相似性矩陣;
③利用初始簇中心算法,初始化k個聚簇中心;
④ 將數(shù)據(jù)訓練集中的節(jié)點分配給與簇中心距離最近的簇;
⑤ 計算簇的平均值,更新各簇的簇中心;
⑥ 若準則函數(shù)(式(7))未收斂,或仍有節(jié)點需要進行重新分配,則重復執(zhí)行步驟④;否則結束算法,輸出聚簇結果。
2) 基于聚簇一階隱馬爾可夫模型的鏈接預測算法
采用DBLP 數(shù)據(jù)集引入元路徑的思想,抽取節(jié)點之間的關系,預測某個作者與某個會議是否存在鏈接關系或是否將會發(fā)生鏈接關系。C-HMM(1)算法主要分為以下5 個步驟。
①在保留語義信息的基礎上,去除冗雜數(shù)據(jù),提取作者、論文、會議信息。
② 提取異質網(wǎng)絡中的作者信息,采用改進的k-means 進行聚簇分析。
③挖掘異質網(wǎng)絡中節(jié)點之間的相關性,提取各聚簇對應的元路徑。
④ 對每個聚簇分別進行訓練,得到狀態(tài)轉移概率矩陣。
⑤ 對預測節(jié)點所在的聚簇使用 Viterbi 算法,選擇概率最大的結果作為鏈接預測的最終結果。
C-HMM(1)算法的流程如圖4 所示。
圖4 C-HMM(1)算法的流程
將數(shù)據(jù)聚簇,從而得到多個簇,分別訓練HMM中的3 個參數(shù)π、A、B。運用MLE 算法訓練數(shù)據(jù)集并對HMM 的參數(shù)進行學習,其參數(shù)估計式為
從數(shù)據(jù)集訓練出HMM 的參數(shù)后,使用Viterbi算法來預測待預測節(jié)點的元路徑。將 δt定義為在時刻t且狀態(tài)為i的所有路徑 (i1,i2,…,it)中的概率最大值,其計算方法為
遞推式為
定義在時刻t且狀態(tài)為i的所有路徑中概率最大路徑的第 t-1個節(jié)點的計算式為
HMM(2)如圖5 所示。HMM(2)增加了觀測值輸出的約束條件,相應地,鏈接預測的準確率也有較大的提高。
圖5 HMM(2)
HMM(2)可以被定義為七元組(S ,O,π,A1,A2,B1,B2),七元組中S、 O、π 和C-HMM(1)中的含義一樣,其他需要重點說明的介紹如下。
HMM(2)與HMM(1)一樣,在鏈接預測中用來解決學習問題和解碼問題。
C-HMM(2)算法利用數(shù)據(jù)集中的訓練樣本,首先用C-HMM(2)中的MLE 算法學習HMM(2)的參數(shù),然后用C-HMM(2)中的Viterbi 算法獲取鏈接預測的最大概率的狀態(tài)序列?;贑-HMM(2)的鏈接預測與基于C-HMM(1)的鏈接預測類似:收集處理異質網(wǎng)絡數(shù)據(jù),對其聚簇;提取元路徑;應用C-HMM(2)。
1) C-HMM(2)的MLE 算法模型
初始狀態(tài)概率計算式為
其中,Init(i)表示在數(shù)據(jù)集訓練樣本中初始狀態(tài)si的序列數(shù)目表示在數(shù)據(jù)集訓練樣本中所有狀態(tài)的序列數(shù)目之和。
隱含狀態(tài)轉移概率計算式為
其中,cij表示數(shù)據(jù)集訓練樣本中,在時刻t狀態(tài)為si、時刻 t+1狀態(tài)轉換為sj的次數(shù);cijk表示數(shù)據(jù)集訓練樣本中,在時刻 t-1狀態(tài)為si、時刻t狀態(tài)為sj、時刻 t+1轉換為狀態(tài)sk的次數(shù);表示在數(shù)據(jù)集訓練樣本中,在時刻 t-1狀態(tài)為si、時刻t狀態(tài)為sj,時刻 t+1轉換到所有狀態(tài)的次數(shù)之和。
觀測狀態(tài)轉移概率計算式為
其中,Ej(ok)表示數(shù)據(jù)集訓練樣本中,在時刻t狀態(tài)為sj時可觀測狀態(tài)為ok的次數(shù)表示數(shù)據(jù)集訓練樣本中,在時刻 t-1狀態(tài)為si、時刻t狀態(tài)為sj時可觀測狀態(tài)為ok的次數(shù)表示數(shù)據(jù)集訓練樣本中,在時刻 t-1狀態(tài)為si、時刻t狀態(tài)為sj時所有觀測狀態(tài)為ok的次數(shù)之和。
最大熵原理的主要思想是在只掌握知識的部分信息且是未知知識時,應該選擇對已知的知識熵最大的概率分布。為了進一步提高鏈接預測性和準確率,在最大熵模型中加入了特征信息對鏈接預測中狀態(tài)轉移的影響,提出了ME-HMM 方法,如圖6所示。ME-HMM 方法處理流程大致概括為:對異質網(wǎng)絡數(shù)據(jù)集聚簇并提取元路徑;進行最大熵處理提取特征;應用C-HMM(2)。
圖6 ME-HMM 方法
首先在數(shù)據(jù)集中選擇合適的特征信息,考慮這些特征信息對鏈接預測模型狀態(tài)轉移的影響,將其加入鏈接預測模型的訓練中,訓練特征-狀態(tài)轉移概率矩陣。
1) 提取特征信息。根據(jù)本文采用的數(shù)據(jù)集,選取一些特征信息,如是否包含人名、是否都是大寫字母、是否以“.”結尾、是否以“a”開頭、是否以“v”開頭。
如果特征信息l只影響一個狀態(tài)sj,則應用
如果特征信息l同時影響狀態(tài)sj和狀態(tài)si,則應用
2) 計算特征-狀態(tài)轉移概率矩陣。當特征信息l只影響狀態(tài)sj時,特征-狀態(tài)轉移概率矩陣為M={Mi,j},其中Mi,j是從狀態(tài)i到狀態(tài)j的轉移概率,且滿足
其中,NF表示特征的個數(shù),NS表示狀態(tài)的個數(shù)。
當特征信息l同時影響狀態(tài)sj和si時,特征-狀態(tài)轉移概率矩陣為其中l(wèi),i,j
M 是從狀態(tài)l到狀態(tài)i、狀態(tài)j的狀態(tài)轉移概率,且滿足
訓練特征-狀態(tài)轉移概率矩陣的步驟如下。
①計算數(shù)據(jù)集中每個特征-狀態(tài)的平均值。假設可觀測狀態(tài)的長度是ms,第l個特征信息、第j個狀態(tài)平均值的計算式為
第l個特征信息、第i個狀態(tài)、第j個狀態(tài)平均值的計算式為
② 根據(jù)GIS 參數(shù)估計算法,得出特征-狀態(tài)概率矩陣。
在最大熵的C-HMM(2)中,時刻 t+1的狀態(tài)sk的轉移概率由時刻t的狀態(tài)sj、時刻 t-1的狀態(tài)si,以及在時刻t得到的特征-狀態(tài)轉移概率共同決定。
當?shù)趌個特征信息僅影響狀態(tài)sk時,狀態(tài)sk的狀態(tài)轉移概率的計算式為
其中,αi,j,k是時刻 t-1狀態(tài)為si、時刻t狀態(tài)為sj時,時刻 t+1狀態(tài)是sk的狀態(tài)轉移概率,γ 是歸一化常數(shù)。
當?shù)趌個特征信息同時影響sk和si時,狀態(tài)sk的狀態(tài)轉移概率的計算式為
其中,λ 是調(diào)節(jié)特征-狀態(tài)轉移概率和狀態(tài)轉移概率矩陣重要性的權重。
本文所采用的DBLP 數(shù)據(jù)集為XML 格式文件且文件較大,在此選擇SAX 解析方式來處理文件。DBLP 數(shù)據(jù)集按年份列出了60 000 多名作者的科研成果,包括72 902 篇論文和464 個會議。其中,每條數(shù)據(jù)
數(shù)據(jù)預處理首先需要提取數(shù)據(jù)中所收錄的論文,每一條記錄中都包含論文的作者、標題、會議等信息。論文中涉及的作者為合作關系,同時將論文的標題信息加入相關作者的屬性信息中。另外,在當前數(shù)據(jù)庫中檢索當前作者相關的其他論文,保證作者的文本屬性完整。本文只提取論文中前3 位作者與該論文的關系。DBLP 數(shù)據(jù)預處理流程如圖7所示。
圖7 DBLP 數(shù)據(jù)預處理流程
本文在Intel i7 10750H 6 核12 線程CPU 主頻為2.6 GHz 的機器上運行程序,隨機抽取90%的數(shù)據(jù)集作為訓練集,剩下的10%作為測試集。
本文通過隨機游走模型生成元路徑來表示網(wǎng)絡結構和節(jié)點的上下文關系,并采用skip-gram 模型生成異質網(wǎng)絡的節(jié)點表示,提取出待預測的2 個節(jié)點之間的元路徑作為候選集。同時通過調(diào)查大量基于元路徑的研究和工作發(fā)現(xiàn),異質網(wǎng)絡中最常用的也是最有效的元路徑方案是APVPA,表示的語義信息是兩位作者在同一會議發(fā)表論文的關系??紤]到本文的實驗環(huán)境,本文抽取的元路徑長度是100,每個節(jié)點的游走次數(shù)是500。部分抽取的元路徑如圖8 所示。
圖8 部分抽取的元路徑
采用計算測試集的精確度(Precision)、召回率(Recall)、F 值(F-Measure)3 種指標作為衡量本文提出的鏈接預測模型的指標。本文將鏈接預測的結果分為有鏈接和無鏈接2 種,將有鏈接的數(shù)據(jù)定義為正例,無鏈接的數(shù)據(jù)定義為負例。針對以上2 種不同情況,分別計算Precision 和Recall??傮w的Precision 和Recall 分別如式(22)和式(23)所示。
其中,PrecisionE和 PrecisionN分別為正例和反例的準確率,RecallE和 RecallN分別為正例和反例的召回率。精確率表示預測正確的鏈接數(shù)目占預測為有鏈接(無鏈接)的數(shù)目的比值;召回率又稱查全率,表示預測正確的鏈接數(shù)目占實際存在鏈接(無鏈接)的數(shù)目的比值。采用Precision 和Recall 這2 個指標的調(diào)和平均值F-Measure 作為評估標準,其計算式為其中,β 是衡量精確度和召回率重要性的權值,本文將β 的值設為常數(shù)1。
本文選擇 CN、RWR、HMM、BRLinks、MDGCN、PURP 方法來進行對比實驗。首先確定聚簇的數(shù)目,以達到最佳的鏈接預測性能。通過多次改變聚簇數(shù)目進行實驗測試,得到鏈接預測的總精確度與聚簇數(shù)目的關系,如圖9 所示。
圖9 鏈接預測的總精確度與聚簇數(shù)目的關系
從圖9 中可以看出,鏈接預測的總精確度隨著聚簇數(shù)目的增加而提高,但當聚簇數(shù)目為6 時,精確度不再有明顯的提高。其原因一方面是有些聚簇訓練得到的HMM 的鏈接預測準確率大致相同;另一方面是對于同一條元路徑來說,不同模型的鏈接預測結果可能相同;除此之外,聚簇數(shù)目多的簇中可能包含的訓練數(shù)據(jù)不多,通過這些簇得到的鏈接預測模型很少作為最終的鏈接預測結果。因此,這些新增簇對HMM 鏈接預測的結果影響不大。同時,本節(jié)又對不同聚簇數(shù)目下的程序運行時間做了測試,如圖10 所示。
圖10 不同聚簇數(shù)目下的程序運行時間
從圖10 中可以看出,聚簇數(shù)目越多,程序運行時間也就更多。圖9 和圖10 的實驗數(shù)據(jù)表明,本文實驗選擇聚簇數(shù)目為6 的效果是最佳的,因此以下對比實驗均采用聚簇數(shù)目為6。
1) C-HMM(1)和HMM 鏈接預測的實驗對比
選擇最佳聚簇數(shù)目6 進行C-HMM(1)和HMM這2 種方法的實驗。C-HMM(1)和HMM 鏈接預測總精確度比較如圖11 所示。
圖11 C-HMM(1)和HMM 鏈接預測總精確度比較
從圖11 中可以看出,C-HMM(1)總精確度比單獨使用HMM 精確度高。當訓練元路徑數(shù)為170 000 時,預測類型節(jié)點鏈接預測精確度比較如表1 所示,進一步說明聚簇能更有效地捕捉異質網(wǎng)絡的結構信息,因此C-HMM(1)有更好的鏈接預測性能。
表1 C-HMM(1)和HMM 對各狀態(tài)鏈接預測精確度比較
2) C-HMM(1)和C-HMM(2)鏈接預測的實驗對比
訓練集從30 000 條開始,不斷增加到170 000 條,C-HMM(1)和C-HMM(2)鏈接預測總精確度比較如圖12 所示。
圖12 C-HMM(1)和C-HMM(2)鏈接預測總精確度比較
從圖12 中可以看出,選取不同數(shù)量的元路徑,C-HMM(2)鏈接預測的總精確度都高于C-HMM(1)。隨著訓練數(shù)據(jù)的增加,C-HMM(2)的總精確度始終較高,這是因為隨著訓練數(shù)據(jù)的增加,C-HMM(2)更加優(yōu)化,識別錯誤的能力更強。當訓練數(shù)據(jù)從120 000 條增加到150 000 條時,2 種方法精確度提高不大,這可能是因為此時增加的訓練集和測試集中數(shù)據(jù)的匹配度較低。
以150 000條元路徑作為訓練集為例,C-HMM(1)和C-HMM(2)鏈接預測的總精確度如表2 所示。
表2 C-HMM(1)和C-HMM(2)鏈接預測的總精確度
從表2 中可以看出,基于C-HMM(2)的鏈接預測精確度高于C-HMM(1)的鏈接預測精確度,更進一步論證了C-HMM(2)的算法性能高于C-HMM(1)。
3) ME-CHMM 鏈接預測的實驗對比
選取相關的特征信息,建立相關的特征匹配字典進行匹配。在判斷是否包含人名特征信息時,使用從網(wǎng)上下載的外國人名進行匹配;對于是否都是大寫字母、是否以“a”“v”開頭、是否以“.”結尾的特征信息,不需要建立特征字典,在程序中可以通過邏輯判斷的方式進行匹配。在實驗中,進行交叉測試,取平均值,不斷調(diào)整特征-狀態(tài)轉移概率和狀態(tài)轉移概率的相對重要程度λ 的值。當λ 取0.6、訓練集從30 000 條增加到170 000 條時,部分鏈接預測方法總精確度的比較如圖13 所示。
圖13 部分鏈接預測方法總精確度的比較
從圖13 中可以看出,隨著訓練數(shù)據(jù)的增加,各方法的總精確度都有不同程度的提升,其中ME-HMM 的鏈接預測總精確度高于其他模型,尤其是高于CN、RWR 和基準方法。C-HMM(1)和C-HMM(2)隨著訓練數(shù)據(jù)的增加,鏈接預測的總精確度有所下降,這是由于新增加的訓練集與測試集匹配度不高,但是在ME-HMM 模型的預測中,這種情況并沒有出現(xiàn),這表明在HMM(2)中加入數(shù)據(jù)特征信息的最大熵模型對鏈接預測更加有效。多種鏈接預測方法實驗比較如表3 所示。
表3 多種鏈接預測方法實驗比較
從表3 中可以看出,在鏈接預測精確度上,C-HMM(2)比 C-HMM(1)更高;在召回率方面,C-HMM(2)沒有優(yōu)勢,但C-HMM(2)總的F-Measure比C-HMM(1)高,這說明C-HMM(2)的鏈接預測性能更高。ME-HMM 在進一步提高鏈接預測精確度的同時,也提高了鏈接預測的召回率。HMM、MDGCN的精確度分別為0.829、0.830,而本文提出的方法的精確度都在0.853 以上;BRLinks、PURP 的F-Measure 的值分別為0.873、0.805,而本文提出的方法的F-Measure 都在0.903 以上,通過對比可以發(fā)現(xiàn),本文提出的方法的F-Measure 至少提高了3 個百分點。由以上實驗結果可知,本文提出的方法性能較為優(yōu)異,其中ME-HMM 方法的性能最好。
在復雜網(wǎng)絡中,如何更加精確地對異質網(wǎng)絡進行鏈接預測一直是人們研究的熱點之一,據(jù)此本文提出了通過改進k-means 算法實現(xiàn)基于聚簇的隱馬爾可夫模型的異質網(wǎng)絡的鏈接預測,并通過分析在C-HMM(2)中狀態(tài)轉移概率、觀測值輸出概率和模型歷史狀態(tài)之間的關系,可知鏈接預測的準確率有較大的提高。在此基礎上,提出ME-HMM,將數(shù)據(jù)的特征信息加入鏈接預測中。實驗表明,ME-HMM在本文中的鏈接預測中具有最優(yōu)的性能,最大程度地提高了鏈接預測的準確率。但本文使用的是靜態(tài)數(shù)據(jù),沒有考慮到數(shù)據(jù)的實時動態(tài)問題。但在實際生活中,數(shù)據(jù)每時每刻都在快速增長,對增量數(shù)據(jù)集的研究更符合現(xiàn)實網(wǎng)絡的特征。因此,在后續(xù)的工作中,可以更深一步地對異質網(wǎng)絡鏈接預測的有關課題進行研究。