趙宇紅 張曉煒

(內蒙古科技大學信息工程學院 內蒙古 包頭 014010)

0 引 言

鏈路預測[1]作為復雜網絡的核心內容之一，可以從網絡數據中挖掘有用的鏈路信息，即基于已存在的網絡拓撲信息、節(jié)點屬性和歷史信息，預測未來尚未建立連接關系的節(jié)點對之間連接的可能性[2]。傳統(tǒng)的鏈路預測方法主要是建立在靜態(tài)網絡[3]的基礎上的，具有代表性的常用的方法有Common Neighbor(CN)[4]、Adamic-Adar(AA)[5]和Preferential Attachment Index(PA)[6]等，這些方法雖然能在靜態(tài)網絡中取到較好結果，但卻忽略了網絡的動態(tài)性特點。為了解決這一問題，動態(tài)網絡的鏈路預測被提出，考慮了時間信息，可以根據網絡歷史時刻的拓撲結構來預測出該網絡在未來的鏈接結構。

對未來可能產生的邊進行預測的核心是對網絡演化規(guī)律的把握，然而，現有的大多數動態(tài)鏈路預測方法都是直接在網絡宏觀的全局拓撲結構進行分析，并沒有注意到網絡中的微觀結構對網絡演化是如何影響的。模體(motif)是一種非常重要的網絡微觀結構[7]，研究發(fā)現它的演化規(guī)律可以在動態(tài)網絡分析中起到關鍵作用。文獻[8]從網絡的微觀演化為切入點，通過分析網絡中頻繁出現的模式的演變情況來進行鏈路預測。文獻[9]首次度量模體的轉換概率并定義其轉換概率矩陣進行鏈路預測。文獻[10]改進了文獻[9]的方法，換用三階張量分解的方法計算模體轉換概率矩陣，同時考慮模體結構指標。

但這些方法都沒有對動態(tài)網絡下時間窗口的準確選取做過多的探究，并且文獻[10]的方法是針對無向網絡的研究，而現實中的大多網絡數據是有向的，同時研究中也沒有考慮網絡中重復連邊的問題。針對這些問題，提出基于模體演化的多因子動態(tài)鏈路預測方法(MFME)。該方法在動態(tài)有向網絡下從合適大小的時間窗口的劃分入手，利用模體演化矩陣來記錄網絡中的模體演化情況，引入整合移動平均自回歸模型有效地預測模體的演化概率。最后，通過結合模體演化影響因子來計算節(jié)點間產生連邊分數來進行鏈路預測。通過真實數據集下與其他方法的比較，驗證了本文方法能夠達到更好的鏈路預測效果。

1 相關介紹

1.1 動態(tài)鏈路預測

假設存在一個有向網絡G=(V,E)，V={v1,v2,…,vN}是該網絡的節(jié)點集合，E={e1,e2,…,eN}是網絡中的節(jié)點間構成的帶權有向邊集合。對于一個動態(tài)有向網絡G，給出它的時間窗口序列1,2,…,t，在t個連續(xù)的時間窗口下G=(g1,g2,…,gt),其中gt=(vt,et)，vt表示t時間窗口下網絡的節(jié)點集合，et表示t時間窗口下網絡中的vt個節(jié)點之間形成的帶權有向邊集合[11]。為了達到研究目的，本文根據已知動態(tài)網絡G中g1到gt的演化情況，設計一種鏈路預測方法，預測時間窗口gt+1中的任意有序節(jié)點間產生連邊的分數值，該分數值越大，則表示兩節(jié)點之間產生鏈路的概率越高。

1.2 模體及其演化理論

模體最早是在生物學的蛋白質網絡里表示最基本的功能模塊，引入到復雜網絡中便可以表示為網絡的基本子結構，其中由三個節(jié)點構成的結構為最基本的模體結構。有向網絡內，共有15種三元模體[12]結構，如圖1所示。圖中標注的模體編號與結構一一對應，該編號將在本文中應用，且下文所述模體均為三元類型。

圖1 15種三元模體結構

網絡中不同模體間的演化規(guī)律的作用非常重要，本文正是利用各時序狀態(tài)下不同模體間的演化規(guī)律來對動態(tài)網絡的鏈路關系分析和預測。

定義1動態(tài)有向網絡中，任意由三個點組成的節(jié)點集可以稱為一個模體m。m為圖1中的15種模體類型之一，用mtfi來表示圖1中第i類模體。動態(tài)網絡的變化可以看作是大量模體間的演化過程，若在任意兩個相鄰的時間窗口下，某三個節(jié)點組成的模體由模體類型i轉化成模體類型j，那么這個過程可表示為：

mtfi→mtfj1≤i,j≤15

(1)

網絡中各模體的演化即衍生了動態(tài)網絡的演化。本文用15×15的模體演化矩陣MEM(Motif Evolution Matrix)來表示動態(tài)網絡相鄰時間窗口上各模體間的演化規(guī)律。矩陣的行標分別對應前一時間窗口的15種不同類型的模體，而列標分別對應后一時間窗口的15種模體。

兩相鄰時間窗口對應矩陣中的每個元素都表示行標對應的模體轉換到列標對應的模體的概率。將15×15種模體之間的歷史轉移概率看作特定的時間序列，使用MEMt,i,j表示在t時刻mtfi轉換為mtfj的概率。

在時間窗口1～t之間，任意兩類模體mtfi、mtfj之間均存在演化概率時間序列MEM1,i,j,MEM2,i,j,…,MEMt-1,i,j。通過上述的演化序列，如果MEMt,i,j的值能被準確預測，則會有利于動態(tài)鏈路預測的研究。

1.3 整合移動平均自回歸模型

自回歸移動平均模型(Autoregressive Moving Average Model)是一種時間序列預測方法。該模型的基本原理是：預測指標隨時間形成的數據序列被視為隨機序列，這些隨機變量的相關性反映了原始數據在時間上的延續(xù)性。一方面，隨機變量受某些因素的影響，另一方面，也有其自身的變化規(guī)律[13]。若一時間序列Yt={Y1,Y2,…,YT}滿足自回歸移動平均模型，可表示為：

Φ(B)▽dYt=Θ(B)εt

(2)

式中：Φ(B)=1-φ1B-…-φpBP,Bp為延遲算子，與Yt作用后得到Yt-p，φp為自回歸系數；▽d=(1-B)d，d為差分次數；Θ(B)=1-θ1B-…-θqBq，θq為移動平滑系數；εt為零均值白噪聲序列。式(2)可簡寫為：

(3)

將模型中心化后，可將公式簡寫為：

Yt=φ0+φ1Yt-1+…+φpYt-p+εt+θ1εt-1-…-θqεt-q

(4)

整合移動平均自回歸模型是自回歸移動平均模型的改進，它不僅有自回歸移動平均模型的優(yōu)點，而且還針對性地加入了非穩(wěn)定序列的預測，并且它完成預測不需要借助其他外生變量。對于非數值型時間序列的處理，本文采用面向屬性的預測思路，即預測每種不同類型屬性在不同取值上的數量分布，可將非數值型預測轉化為數值型預測。預測序列的穩(wěn)定性對模型預測結果影響很大，數據穩(wěn)定表示數據序列是沒有趨勢，沒有周期性的；若數據是不穩(wěn)定的，則無法捕捉到規(guī)律，難以預測。

1.4 模體演化影響因子

1.4.1鏈接權重

現實中的動態(tài)網絡往往存在重復的連邊，把任意兩節(jié)點關系的強度用其鏈接重復次數表示。假如模體內的某條邊重復出現，則認為這條邊代表的關系也就越強。若網絡中兩節(jié)點出現的重復連邊e1,e2,…,en，用最初出現的邊e1作為這條鏈接的代表，把出現的次數作為e1的權重w，用w表示這兩點間聯(lián)系的強弱程度，鏈接關系的強弱將對連邊的演化有著重要的影響。

1.4.2閉包三原組

三元閉包是一種非常直觀和自然關系的描述。例如，如果兩個人B和C存在一個共同朋友A，則這兩個人在未來成為朋友的可能性就會提高。共同的朋友A直接導致他們彼此見面的幾率增加，并且關系鏈形成的過程中，B和C都和A是朋友，這為他們提供了陌生人所缺乏的基本信任[14]。這種三節(jié)點之間的關聯(lián)形成三元閉包，而閉包也呈現不同的結構，且不同結構的閉包也會影響鏈接的演化結果。

1.5 實驗數據集

本文使用兩個真實的數據集進行鏈路預測實驗。安然(Enron)網絡[15]是2000年至2002年間150位安然員工之間發(fā)送的60多萬封電子郵件的公開數據庫，該數據集網絡的連邊中帶有時間戳注釋；Facebook-wosn-wall[16]是某一用戶發(fā)給其他用戶的一小部分帖子的定向網絡，網絡中的節(jié)點是Facebook用戶，每個有向邊代表一個帖子，并且連邊具有時間戳。這兩個真實網絡中的節(jié)點關系都是有向的，并且這些節(jié)點關系都包含時間信息，因此都是動態(tài)的有向網絡。數據具體參數如表1所示。

表1 實驗數據集參數表

2 算法思路與設計

本文的研究重點是對動態(tài)鏈路預測的多影響因子的獲取，主要分為兩部分，一是如何對動態(tài)網絡進行合適大小的時間窗口劃分；二是怎樣考慮模體演化過程中鏈接權重和閉包三元組對連邊形成的影響。首先，確定兩個動態(tài)網絡中以時間窗口為共同變量且呈現趨勢相反的函數，利用兩函數的差值最小化來找到合適的窗口大?。黄浯?，利用預測模型得到模體演化預測矩陣MEPM(Motif Evolution Prediction Matrix)后，結合兩個模體演化影響因子計算出相應的模體影響指數，綜合預測矩陣得出任意兩節(jié)點的產生連邊的概率。

2.1 合適的時間窗口劃分

對于動態(tài)網絡預測研究，時間窗口的劃分對其預測結果有較大的影響，因此選取適當的時間窗口劃分方法非常必要。本文采用SOTS(Segment of Time Series)方法對動態(tài)網絡劃分時間窗口。

在給定窗口大小為ω和相應的網絡g(ω)的情況下，f代表動態(tài)網絡時間快照的不同統(tǒng)計信息，Sω表示其對應的時間序列信息：

Sω(g)=[f(G1),f(G2),…,f(Gt),…,f(GT)]

(5)

為了保障時間窗口中保留較完善的網絡快照信息，采用如下方法：

(1) 方差：V(Sω)表示Sω的方差，可以看作是一種時間序列Sω的噪聲度量方法，公式如下：

(6)

(7)

式中：ε(Sω)為Sω的均值。隨著時間窗口ω的變化，方差的值也會發(fā)生改變。如果方差值較大的話，說明Sω隨著時間發(fā)生了劇烈的變化，這樣會產生信息冗余，產生很多噪聲；反之，會使得Sω過于平滑，丟失很多有用信息。

(2) 時序壓縮比：d表示Sω(g)的序列長度，cd表示利用數據壓縮算法壓縮后的Sω(g)的序列長度，則Sω(g)的時序壓縮比R(Sω)表示如下：

(8)

R(Sω)是一種對Sω的信息編碼方式，一個較小的時序壓縮比值表示Sω的信息中存在大量的噪聲；反之，則表示混亂度低，信息含量多。

由上邊的描述可以看出，方差和壓縮比隨著窗口大小ω的變化呈現著相反的趨勢，方差和時序壓縮比的最小差值也就是最優(yōu)的時間窗口劃分值。SOTS時間窗口劃分方法步驟如算法1所示。

算法1SOTS時間窗口劃分方法

輸入:1.帶有時間標簽的有向網絡

2.該網絡下窗口劃分的最大可能值ωmax≥1

輸出:合適的窗口大小ω

1 forω=1 toωmaxdo

2 根據圖序列計算時間序列Sω:[f(G1),f(G2),…,f(Gt),…,f(GT)]；

3 計算對應窗口下的方差V(Sω)和時序壓縮比R(Sω)；

4 ifV(Sω)-R(Sω)=0 then

5 輸出ω；

6 end if

7 end for

2.2 構建模體演化概率預測矩陣

以優(yōu)化的時間窗口對動態(tài)網絡進行等值窗口切分，對歷史演化信息統(tǒng)計，則可以得到相鄰時間窗口下不同模體類型的轉換概率。在兩個數據集下對所獲取的模體演化信息進行分析，圖2和圖3分別是Enron數據集和Facebook數據集所截取的前15個時間窗口的不同模體下的演化情況，可以看出模體在演化過程中會出現一定的趨勢性和周期性，即演化過程中的不穩(wěn)定性。例如，圖2中008號模體到011號模體的演化過程，圖3中005號模體到006號模體的演化過程等，這樣的不穩(wěn)定性對預測模型的訓練和預測結果都會有不好的影響。

圖2 Enron數據集下不同模體間演化概率

圖3 Facebook數據集下不同模體間演化概率

本文基于TTM prediction[9]算法將每兩個相鄰時間窗口下的模體演化概率分別記錄到對應的模體演化矩陣MEM當中，最后利用整合移動平均自回歸的時序預測模型計算兩個相鄰時間窗口下的模體間演化概率并得到預測矩陣。

在劃分好的相鄰時間窗口下，若某兩個類型模特間的演化概率的時間序列為MEM1,i,j,MEM2,i,j,…,MEMt,i,j，表示為Yt=(y1,y2，…,yt)，使用整合移動平均自回歸模型可表示為式(2)的形式。

(1) 用單位根檢驗法來判斷數據的平穩(wěn)性。當數據不平穩(wěn)時，對其進行差分處理，差分階數的選取從1逐漸增加，直至滿足校驗。檢驗方法如下：

假設序列經過d階差分后平穩(wěn)，可以設：

(9)

(10)

由式(10)知，模型可以得出p+q個根。當d≠0時，可判斷序列在模型下不平穩(wěn)。

(2) 確定模型最佳的p、q值。根據所選數據的自相關函數ACF和偏自相關函數PACF的拖尾性和截尾性來確定p和q。本文采用AIC標準，即利用使AIC達到最小值的自回歸移動平均模型進行擬合。AIC的標準函數如下：

AIC=nlnL+2(p+q+1)

(11)

式中：L為似然函數。選擇使AIC達到最小的p、q值為最佳p、q值。

(3) 估計預測模型中參數的值。本文選用最小二乘法來估計參數值。方法如下：

(12)

θ2εt-2-…-θqεt-q

(13)

式中：φi為自回歸系數；θi為移動平均系數；εi為零均值白噪聲序列。則殘差項為：

(14)

至此，確立適合本文的模型及其參數。利用得到的模型預測出T-1到T時間窗口下任意兩類模體間的演化概率，從而得到預測矩陣MEPM。整個過程可用圖4表示。

圖4 模體演化矩陣及預測矩陣構建過程

每相鄰的兩個時間窗口下的模體演化信息用一個MEM記錄，并把前T-1個MEM作為歷史序列，用整合移動平均自回歸模型學習并預測出最后的MEPM。

2.3 基于模體演化的多因子鏈路預測方法

網絡中的一個節(jié)點對往往可能屬于多個模體之中。如圖5所示，一個簡單的有向網絡中存在節(jié)點對(vm,vn),該節(jié)點對可以屬于模體(vm,vn,v2)、(vm,vn,v5),也可以屬于(vm,vn,v4)等。因此，當得到模體預測矩陣時，并不能完全直接由其得出某節(jié)點對之間的連邊概率。但是，每個包含該節(jié)點對的模體的狀態(tài)都為連邊可能性的預測提供了參考，并且對該節(jié)點對影響更大的模體對預測結果往往也起到積極的作用。

圖5 簡單動態(tài)有向網絡結構示例圖

2.3.1模體演化影響因子

影響模體的演化主要集中表現為兩個方面，一方面是單個模體中各節(jié)點間的連邊次數，連接頻率越高，則說明該模體的影響度越大；另一方面是模體的閉合次數，在模體演化的過程中，如果某一模體形成的閉合次數越多，說明該模體內節(jié)點間關系越緊密，對節(jié)點對連邊的預測也越重要。此外，針對有向網絡而言模體的閉合類型也不一樣，比如模體(vm,vn,v2)是單層閉合，而模體(vm,vn,v5)則存在一條雙層閉合。

基于上述分析，對于任一個模體(vm,vn,vj)，本文定義模體影響指數來綜合描述模體演化影響因子即連邊次數和閉包閉合次數對鏈路預測的影響程度：

ei∈link(vm,vn,vj)

(15)

式中：I(vm,vn,vj)表示該模體的模體影響指數；Wvi表示模體內任兩節(jié)點間的連邊次數；link(vm,vn,vj)表示當前模體內所有存在的連邊；synt表示t時刻模體是否閉合，閉合為1，不閉合為0；δ表示連邊次數和閉合次數的影響占比。對于一個有向網的模體閉合狀態(tài)，考慮θ為模體閉合程度，取值如式(16)所示。

(16)

根據得到的MEPM和模體影響指數，可以計算出預測的T時刻中任意節(jié)點對(vm,vn)間的連邊概率：

vj∈neig(vm,vn)

(17)

式中：mtfT-1為T-1時刻(vm,vn,vj)的模體名；mtfT為T時刻(vm,vn,vj)的模體名；neig(vm,vn)為節(jié)點vm、vn的鄰居節(jié)點集。

2.3.2算法描述

在上述分析基礎上，本文提出基于模體演化的多因子鏈路預測方法MFME，算法如下：

算法2基于模體演化的多因子鏈路預測方法

輸入:1到T時刻的時間窗口

輸出:T時刻各節(jié)點對的連邊概率

1 初始化: 計算1～T-1相鄰時間窗口的模體演化矩陣；

2 計算T-1到T時間窗口的模體演化預測矩陣MEPM；

3 for each(vm,vn) do

4 for each(vm,vn)∈(vm,vn,vj) ；

//vj∈neig(vm,vn)

5 用式(15)計算模體影響指數；

6 end

7 用式(17)計算節(jié)點對的連邊概率；

8 end

3 實驗與結果分析

3.1 實驗設計

本文研究采用的實驗環(huán)境是AMD Ryzen 5 2600X，16 GB內存，系統(tǒng)采用Windows 10，實驗程序采用MATLAB編寫，版本為R2019a。

本文所提的MFME方法將與TTM[9]、TCM[10]、TS[18]進行對比實驗。其中，TTM是最先利用模體的轉換概率信息進行鏈路預測的方法，并得到了較好結果；TCM是在TTM的基礎上用三階張量分解的方法計算模體轉換概率矩陣，效果優(yōu)于TTM方法；而TS方法是一種經典的動態(tài)鏈路預測方法。AUC[19]可以從整體上衡量結果的精確度，對比實驗采用AUC指標對預測結果的準確性進行驗證。

3.2 實驗結果及分析

下面先利用SOTS算法對選定的兩個真實數據集進行時間窗口的劃分。圖6為Enron數據集在SOTS算法下的方差和時序壓縮比的計算結果，可以看到隨著時間窗口ω的增大，方差是總體呈下降趨勢的；反之時序壓縮比呈持續(xù)增長的趨勢，并且很明顯可以看到在ω=6附近時兩者的值出現交點，因此我們將選取ω=6為Enron數據集的時間窗口劃分大小。

圖6 SOTS算法在Enron下的劃分情況

由于Facebook-wosn-wall數據集的網絡規(guī)模和時間跨度都更大，因此在利用SOTS算法進行劃分的時候，所呈現的曲線也有很大的不同。如圖7所示，該數據集下的方差曲線呈快速下降的趨勢，而時序壓縮比曲線在ω=20附近才開始有明顯的增長趨勢，并且兩條曲線在ω=30附近出現交點，因此，本文將選取ω=30為Facebook-wosn-wall數據集的時間窗口劃分大小。

圖7 SOTS算法在Facebook-wosn-wall下的劃分情況

為了驗證算法的有效性并能從中體現出時間窗口對實驗結果產生的影響，分別對所用的兩個數據集進行了多組實驗。圖8是Enron數據集在不同時間窗口下各算法的AUC值曲線，可以看出各算法在不同時間窗口下的AUC值有著較為明顯的變化趨勢，并且時間窗口在5～8的范圍里各方法的AUC值都達到了最大值；圖9是Facebook-wosn-wall數據集在不同時間窗口下各算法的AUC值變化曲線，可以看到曲線隨著窗口大小的增長同樣有明顯的變化趨勢，而且在窗口大小為28～35的區(qū)間里四種方法的AUC值也是達到一個最高的水平。

圖8 Enron數據集不同時間窗口下各算法AUC對比

圖9 Facebook-wosn-wall數據集不同時間窗口下各算法AUC對比

實驗表明在SOTS的時間窗口劃分結果下進行實驗，各預測算法都能在選取的窗口大小中得到更為精準的預測結果，說明SOTS算法對動態(tài)網絡時間窗口劃分的有效性；同時利用兩個時序相關函數的計算，也能更為快速地確定劃分結果，這也體現了SOTS算法的高效性。

基于優(yōu)化的時間窗口的劃分，分別在兩個數據集上進行了上述4種鏈路預測方法的對比實驗。實驗中，考慮到稀疏網絡中模體的閉合次數較少，因此將連邊次數的影響占比δ設為0.7，則模體的閉合次數影響占比為0.3。實驗結果如圖10所示，TS算法作為一種經典的時序鏈路預測方法還是有著較高的準確性的，它在Enron數據集上的表現明顯比TTM和TCM算法更好，但在Facebook-wosn-wall數據集上的表現較差，由于Facebook-wosn-wall數據集規(guī)模相對較大，模體演化的規(guī)律性更容易體現出來并被模型所學習，三種基于模體轉換分析的算法都有著相似的表現。

圖10 不同數據集下各算法的AUC值對比

雖然TTM和TCM都對模特轉換進行了分析，但TTM缺乏對不同模體轉換概率隨時間變化的規(guī)律的進一步挖掘，而TCM缺乏對動態(tài)網絡時間窗口劃分準確合理的處理和對真實網絡有向性的考慮。與其他三種算法相比，MFME方法利用SOTS算法快速得到了更為準確合理的時間窗口的劃分，對模體演化規(guī)律分析后選用合理的時序預測方法，同時充分考慮了模體的兩個影響因子對模體演化的影響，使得MFME算法在兩個數據集下的預測效果都有較好表現。

3.3 算法復雜度分析

本文所提的算法可分為三個主要部分，一是時間窗口大小的確定，二是模體演化概率矩陣的構建，三是模體影響指數的計算。其中，SOTS算法的時間復雜度為O(n),模體演化概率矩陣計算時間復雜度為：如果采用傳統(tǒng)的對網絡進行遍歷的方式計算則時間復雜度為O(tn3)，模體影響指數計算時間復雜度為O(nt)。其中，n為網絡節(jié)點數，b為網絡最大度，t為時間窗口。

4 結 語

鏈路預測是動態(tài)網絡演化研究的重要內容，合適的時間窗口劃分是對動態(tài)網絡演化研究的必要且關鍵的一步。將模體這種微觀結構的演化規(guī)律應用到動態(tài)網絡的鏈路預測之中，可以更加深入、準確地挖掘節(jié)點間的關聯(lián)變化從而取得較好的鏈路預測效果?，F實中的大多數動態(tài)網絡都是有向網絡，本文基于動態(tài)有向網絡首先研究時間窗口的劃分，基于優(yōu)化的時間窗口利用模體演化矩陣來記錄網絡中不同時間序列模體演化情況，引入整合移動平均自回歸模型來預測模體的演化概率。最后，綜合考慮模體演化影響因子獲得連邊影響指數并結合模體演化概率來計算節(jié)點間產生連邊的分數。仿真實驗表明，本文所提方法在時序鏈路預測中可獲得更精確的預測值。在以后的研究中，欲更加深刻挖掘模體演化的周期性和趨勢性等規(guī)律對動態(tài)有向網絡鏈路預測的影響。