基于混合深度學習的復雜網絡鏈路預測研究

白 雪，董德森

(1.吉林化工學院信息中心，吉林吉林 132022；2.延邊大學師范學院，吉林延吉 133002)

1 引言

在復雜網絡的鏈路預測中，在已有的網絡節點屬性和信息獲取過程中，不僅存在未來網絡鏈路，還存在沒有被發現的網絡鏈路[1]。在預測復雜網絡節點之間的鏈路中，通過找出復雜網絡中很多不被知道的鏈路間關系，獲取復雜網絡結構分析與鏈路預測研究理論之間的關系，分析網絡拓撲結構的演化機制，以此對復雜網絡鏈路進行預測。鏈路預測來分析復雜網絡和應用網絡，來找出好的鏈路預測方法，繼而找出預測復雜網絡拓撲結構的演化規律[2]。在復雜網絡分析中，鏈路預測問題是其重要的組成部分，鏈路預測在復雜網絡中的目的是為了解決路由策略的難點。但是在不同的復雜網絡中，鏈路預測的方法也存在不同[3]。所以要設計一個好的鏈路預測方法，在現有的經驗和網絡的實際條件下，根據復雜網絡的特征來設計出鏈路預測方法。

王文濤等人[4]主要是對現有的鏈路預測方法進行著重研究，來獲悉網絡節點的領域拓撲信息，從而形成網絡鏈路中的特殊向量，先是通過網絡來學習node2vec算法，形成節點表示向量，而通過該向量來映射網絡節點的結構信息，使之成為具有三維特征的數據，接著通過稠密連接卷積神經網絡來獲取鏈路的結構特征，并形成兩個分類模型，形成了鏈路預測，并經仿真表明該鏈路預測方法具備較好的預測性能；白樺等人[5]為了提高網絡鏈路預測的準確性，將節點局部相似性應用到了復雜網絡鏈路預測中，并通過五個復雜網絡數據集進行實驗，采用AUC指標評價其效果，實驗表明改進的方法在預測準確率上整體優于其它的局部相似性方法。但是以上兩種方法在多次迭代的情況下，會出現網絡鏈路的預測精度偏低，導致最終的預測結果較差。

針對以上研究背景，本文采用混合深度學習來預測復雜網絡鏈路，從而提高復雜網絡鏈路預測效果。

2 復雜網絡鏈路預測方法

2.1 相似性指標

在復雜網絡中，可以使用與節點屬性相似的外部信息來預測網絡鏈路，但由于復雜網絡節點屬性隨網絡結構的變化而變化[6]，因此無法應用于復雜網絡的鏈路預測。但相對于復雜網絡節點的屬性信息，結構信息和歷史行為信息具有更高的可信度，且更易于獲取。

鏈路變化的情況具有不確定性，常常受到時間的演化和網絡本身固有的某些因素影響，如果能在網絡鏈路預測方法中加以考慮，并能進一步分析這些因素對鏈路變化的具體影響，則對實際復雜網絡的鏈路預測研究有很大幫助[7]。圖1顯示了復雜網絡鏈路變化的示意圖。

圖1 鏈路變化示意圖

如圖1所示，如果只考慮復雜網絡在t3時刻的結構，那么當預測下一個時刻的復雜網絡鏈路情況時，就可以直接得出節點S和節點D之間基本不會發生連接[8]。但是，綜合考慮t1時刻和t2時刻的復雜網絡拓撲結構，可以發現節點S和節點D之間的關系比較密切，它們之間存在著很高的連接可能性。如果能利用混合深度學習網絡上的歷史信息來預測復雜網絡鏈路，則預測結果會更加準確[9]。

將復雜網絡中節點對連接的總時長、頻率和最終時刻相結合，計算網絡歷史信息對復雜網絡鏈路的影響系數

HIC=Il+If+Ic

(1)

其中，Il表示復雜網絡節點對連接的時長系數，If表示頻次系數，Ic表示復雜網絡節點對最近聯系的時刻系數。

利用RA、AA、CN三個指標綜合考慮復雜網絡歷史信息對鏈路的影響系數[10]，得到H_CN、H_AA、H_RA相似性指標，即

(2)

(3)

(4)

復雜網絡會隨著時間的頻繁變化而產生一種拓撲結構，H_CN、H_AA、H_RA相似性指標考慮到了復雜網絡結構對鏈路的影響程度，分析了復雜網絡的拓撲特征，適合應用于復雜網絡鏈路的預測。

利用鏈路變化示意圖，分析了歷史信息對復雜網絡鏈路的影響系數，結合RA指標、AA指標和CN指標的計算，分析了復雜網絡的拓撲特征。

2.2 基于混合深度學習的預測模型

通過混合深度學習技術，在機器學習的過程中構建人工神經網絡[11]。在網絡每一隱含層中，神經網絡都會產生非線性變換，最后，提取輸入數據中的隱藏規律。現有的機器學習模型都是在淺層次學習的基礎上進行的，不能很好的提取網絡鏈路的基本特征，而混合深度學習技術中的隱藏層具有非線性計算功能，能快速的處理信息，因此，利用混合深度學習技術，對復雜網絡鏈路進行預測[12]。

混合深度學習技術是在輸入網絡數據和模型的基礎上，構建一個與人大腦層次結構類似的神經系統。混合深度學習的反向傳播的流程如圖2所示。

圖2 混合深度學習的反向傳播流程圖

基于混合深度學習的反向傳播流程，可以在t時刻描述出復雜網絡鏈路隱藏層的狀態，如下

(5)

t時刻復雜網絡隱藏層的狀態是由t-1時刻的狀態和t時刻的輸入數據來決定的，其中，σ表示激活函數，b表示偏置參數，那么t時刻復雜網絡隱藏層的輸出為

o(t)=Vh(t)+c

(6)

那么t時刻預測出的復雜網絡鏈路輸出值為

(7)

利用時間窗中的相似性指標對復雜網絡鏈路進行預測，取得了良好的效果，但目前還沒有發現時間窗和時間窗之間的具體聯系。若能隨著時間變化，挖掘出復雜網絡鏈路的規律，則能較好地預測復雜網絡中的鏈路，并能準確地將相似度指標作為混合深度學習的訓練樣本，預處理訓練之后，再將數據輸入到復雜網絡鏈路預測模型中，以相似度指標作為網絡鏈路的基本特征，提取出復雜網絡的變化規律。

基于深度學習的復雜網絡鏈路預測模型框架如圖3所示。

圖3 基于深度學習的復雜網絡鏈路預測模型框架

基于混合深度學習的反向傳播流程，描述出復雜網絡鏈路隱藏層的狀態，利用復雜網絡隱藏層的輸出，預測出的復雜網絡鏈路輸出值，將相似性指標作為復雜網絡鏈路預測的訓練樣本，構建了復雜網絡鏈路預測模型。

2.3 復雜網絡鏈路預測實現

復雜網絡節點移動的隨機性會導致復雜網絡出現稀疏的特性。由于大多數情況下網絡連接數較少，在鏈路預測模型的訓練階段，正負樣本的比例嚴重失衡。為了減少上述問題對模型精度的影響，有必要針對性地選擇預測區域中的復雜網絡節點，以保證其中生成的連接不太稀疏。本文不根據節點在物理空間中的位置劃分預測區域，而是確定節點組成的邏輯空間。具體方法是：遍歷所有復雜網絡節點，獲取每個節點的歷史連接信息，計算每個節點的連接權重，如下式所示

(8)

其中，R(i)表示每個節點的連接權重，i表示復雜網絡節點的編號，j表示與節點i產生連接的節點編號，R表示相關性系數。接下來對所有復雜網絡節點的連接權重進行排序，按照下式來計算復雜網絡節點的多項式概率分布情況

(9)

其中，Rall表示所有節點的連接權重。在目前主流的網絡鏈路預測研究中，由于網絡的演化過程都比較復雜，大多數鏈路預測方法都考慮了一對節點之間的鏈路。然而，在實際的網絡環境中，多個網絡節點之間的鏈路情況往往反映了復雜網絡結構的演化規律。單節點對之間的鏈路預測本質是一個二元分類問題。如果預測結果為1，則表示該對節點在下一個周期內可以連接，如果預測結果為0，則不連接。在此基礎上，針對多個網絡節點之間的鏈路，將多個網絡節點之間的每一個可能的連接視為一個模式(如圖4所示)，然后利用模式分類方法實現多個網絡節點之間的鏈路預測。

圖4 復雜網絡鏈路劃分結果

復雜網絡在下一個時刻的鏈路模式就是預測的輸出標簽，每一類標簽都具有特定的編號，由下式計算得到

(10)

其中，N表示復雜網絡節點對的數量，Si表示第i個復雜網絡節點對之間的鏈路狀態，N的大小由下式決定

(11)

其中，n表示復雜網絡節點的數量。

綜上所述，采用歷史信息計算復雜網絡鏈路的影響系數，引入復雜網絡鏈路預測相似性指標，利用混合深度學習構建復雜網絡鏈路的預測模型，結合模式分類方法實現多個網絡節點之間的鏈路預測

3 實驗對比分析

3.1 實驗數據集

采用復雜網絡中比較具有代表性的數據集進行實驗分析，數據集的參數設置如表1所示。

表1 數據集的參數設置

Infocom05數據集中的復雜網絡節點的活動范圍比較小，具有較高的相遇頻率，而MIT數據集具有節點密度小、場景大的特點，且復雜網絡節點的相遇頻率比較低。兩個數據集之間具有非常強烈的針對性。

3.2 實驗平臺及工具

采用Matlab仿真工具計算Infocom05數據集和MIT數據集在特定時間窗口內的指標值，并對復雜網絡中的鏈路數據進行分割處理，使復雜網絡鏈路數據在測試過程中與混合深度學習的格式更貼切。在復雜網絡鏈路預測對比測試中，采用機器學習庫中的算法進行比較，驗證基于混合深度學習的復雜網絡鏈路預測方法的準確性。

3.3 實驗結果分析

在Infocom05數據集和MIT數據集中，復雜網絡節點對平均每一個240秒和1400秒都會自動完成一次連接，令復雜網絡鏈路不發生改變。實驗測試過程中，設置Infocom05數據集在60秒～600秒的相鄰范圍內進行對比，采樣間隔為60秒，設置MIT數據集在300秒～3000秒的相鄰范圍內進行對比，對比結果如表2所示。

表2 不同時間窗口下復雜網絡鏈路的預測效果

從表2的結果可以看出，時間窗口的長度不同會影響復雜網絡鏈路的預測效果，如果時間窗口比較短，輸入的復雜網絡鏈路樣本就會出現過多的鏈路數據重復的特征，并且在訓練網絡鏈路數據樣本的過程中，由于復雜網絡中新鏈路特征的敏感性比較強烈，導致鏈路預測的效果越來越差；如果時間窗口隨著實驗測試的進行越來越大，就會增大復雜網絡鏈路特征的提取難度，還會在鏈路數據訓練過程中，無法提取出網絡鏈路特征。根據表2的仿真結果可以得出，為了使預測效果達到最優，需要將時間窗口在兩個數據集中分別設為360秒和180秒。

在鏈路預測效果實驗中，假設鏈路數據樣本的維度在100步長～600步長之間，實驗結果采集間隔為50個步長。結果如表3所示。

表3 不同維度下復雜網絡鏈路的預測結果

從表3的結果可以看出，樣本維度的不同會影響復雜網絡鏈路的預測效果，在Infocom05數據集和MIT數據集中，復雜網絡鏈路要想達到最好的預測效果，需要將樣本維度設置為500和600。

為了驗證本文方法的有效性，采用本文提出的基于混合深度學習的復雜網絡鏈路預測方法、文獻[4]提出的基于密集連接卷積神經網絡的鏈路預測方法和文獻[5]提出的基于節點局部相似性的復雜網絡鏈路預測方法，對復雜網絡鏈路預測精度進行對比分析，對比結果如圖5所示。

圖5 三種方法的預測精度對比結果

根據圖5可知，隨著迭代次數的不斷增加，本文方法的復雜網絡鏈路預測精度較穩定，一直持續在99%左右，而文獻[4]提出的基于密集連接卷積神經網絡的鏈路預測方法和文獻[5]提出的基于節點局部相似性的復雜網絡鏈路預測方法隨著迭代次數的不斷增加，復雜網絡鏈路預測精度曲線波動較大，最高只有90%，說明本文方法的復雜網絡鏈路預測精度比文獻[4]提出的基于密集連接卷積神經網絡的鏈路預測方法和文獻[5]提出的基于節點局部相似性的復雜網絡鏈路預測方法的復雜網絡鏈路預測精度高。

4 結束語

為了解決傳統的復雜網絡鏈路預測方法存在預測精度低的問題，本文提出了基于混合深度學習的復雜網絡鏈路預測方法，利用混合深度學習構建了復雜網絡鏈路的預測模型，結合復雜網絡鏈路程序設計，實現了復雜網絡鏈路的預測。仿真結果顯示，該方法的復雜網絡鏈路預測精度較高，預測效果較好。