趙宇紅 張曉煒

(內(nèi)蒙古科技大學(xué)信息工程學(xué)院 內(nèi)蒙古 包頭 014010)

0 引 言

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

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

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

1 相關(guān)介紹

1.1 動(dòng)態(tài)鏈路預(yù)測(cè)

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

1.2 模體及其演化理論

模體最早是在生物學(xué)的蛋白質(zhì)網(wǎng)絡(luò)里表示最基本的功能模塊，引入到復(fù)雜網(wǎng)絡(luò)中便可以表示為網(wǎng)絡(luò)的基本子結(jié)構(gòu)，其中由三個(gè)節(jié)點(diǎn)構(gòu)成的結(jié)構(gòu)為最基本的模體結(jié)構(gòu)。有向網(wǎng)絡(luò)內(nèi)，共有15種三元模體[12]結(jié)構(gòu)，如圖1所示。圖中標(biāo)注的模體編號(hào)與結(jié)構(gòu)一一對(duì)應(yīng)，該編號(hào)將在本文中應(yīng)用，且下文所述模體均為三元類(lèi)型。

圖1 15種三元模體結(jié)構(gòu)

網(wǎng)絡(luò)中不同模體間的演化規(guī)律的作用非常重要，本文正是利用各時(shí)序狀態(tài)下不同模體間的演化規(guī)律來(lái)對(duì)動(dòng)態(tài)網(wǎng)絡(luò)的鏈路關(guān)系分析和預(yù)測(cè)。

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

mtfi→mtfj1≤i,j≤15

(1)

網(wǎng)絡(luò)中各模體的演化即衍生了動(dòng)態(tài)網(wǎng)絡(luò)的演化。本文用15×15的模體演化矩陣MEM(Motif Evolution Matrix)來(lái)表示動(dòng)態(tài)網(wǎng)絡(luò)相鄰時(shí)間窗口上各模體間的演化規(guī)律。矩陣的行標(biāo)分別對(duì)應(yīng)前一時(shí)間窗口的15種不同類(lèi)型的模體，而列標(biāo)分別對(duì)應(yīng)后一時(shí)間窗口的15種模體。

兩相鄰時(shí)間窗口對(duì)應(yīng)矩陣中的每個(gè)元素都表示行標(biāo)對(duì)應(yīng)的模體轉(zhuǎn)換到列標(biāo)對(duì)應(yīng)的模體的概率。將15×15種模體之間的歷史轉(zhuǎn)移概率看作特定的時(shí)間序列，使用MEMt,i,j表示在t時(shí)刻mtfi轉(zhuǎn)換為mtfj的概率。

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

1.3 整合移動(dòng)平均自回歸模型

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

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

(2)

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

(3)

將模型中心化后，可將公式簡(jiǎn)寫(xiě)為：

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

(4)

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

1.4 模體演化影響因子

1.4.1鏈接權(quán)重

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

1.4.2閉包三原組

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

1.5 實(shí)驗(yàn)數(shù)據(jù)集

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

表1 實(shí)驗(yàn)數(shù)據(jù)集參數(shù)表

2 算法思路與設(shè)計(jì)

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

2.1 合適的時(shí)間窗口劃分

對(duì)于動(dòng)態(tài)網(wǎng)絡(luò)預(yù)測(cè)研究，時(shí)間窗口的劃分對(duì)其預(yù)測(cè)結(jié)果有較大的影響，因此選取適當(dāng)?shù)臅r(shí)間窗口劃分方法非常必要。本文采用SOTS(Segment of Time Series)方法對(duì)動(dòng)態(tài)網(wǎng)絡(luò)劃分時(shí)間窗口。

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

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

(5)

為了保障時(shí)間窗口中保留較完善的網(wǎng)絡(luò)快照信息，采用如下方法：

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

(6)

(7)

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

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

(8)

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

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

算法1SOTS時(shí)間窗口劃分方法

輸入:1.帶有時(shí)間標(biāo)簽的有向網(wǎng)絡(luò)

2.該網(wǎng)絡(luò)下窗口劃分的最大可能值ωmax≥1

輸出:合適的窗口大小ω

1 forω=1 toωmaxdo

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

3 計(jì)算對(duì)應(yīng)窗口下的方差V(Sω)和時(shí)序壓縮比R(Sω)；

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

5 輸出ω；

6 end if

7 end for

2.2 構(gòu)建模體演化概率預(yù)測(cè)矩陣

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

圖2 Enron數(shù)據(jù)集下不同模體間演化概率

圖3 Facebook數(shù)據(jù)集下不同模體間演化概率

本文基于TTM prediction[9]算法將每?jī)蓚€(gè)相鄰時(shí)間窗口下的模體演化概率分別記錄到對(duì)應(yīng)的模體演化矩陣MEM當(dāng)中，最后利用整合移動(dòng)平均自回歸的時(shí)序預(yù)測(cè)模型計(jì)算兩個(gè)相鄰時(shí)間窗口下的模體間演化概率并得到預(yù)測(cè)矩陣。

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

(1) 用單位根檢驗(yàn)法來(lái)判斷數(shù)據(jù)的平穩(wěn)性。當(dāng)數(shù)據(jù)不平穩(wěn)時(shí)，對(duì)其進(jìn)行差分處理，差分階數(shù)的選取從1逐漸增加，直至滿足校驗(yàn)。檢驗(yàn)方法如下：

假設(shè)序列經(jīng)過(guò)d階差分后平穩(wěn)，可以設(shè)：

(9)

(10)

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

(2) 確定模型最佳的p、q值。根據(jù)所選數(shù)據(jù)的自相關(guān)函數(shù)ACF和偏自相關(guān)函數(shù)PACF的拖尾性和截尾性來(lái)確定p和q。本文采用AIC標(biāo)準(zhǔn)，即利用使AIC達(dá)到最小值的自回歸移動(dòng)平均模型進(jìn)行擬合。AIC的標(biāo)準(zhǔn)函數(shù)如下：

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

(11)

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

(3) 估計(jì)預(yù)測(cè)模型中參數(shù)的值。本文選用最小二乘法來(lái)估計(jì)參數(shù)值。方法如下：

(12)

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

(13)

式中：φi為自回歸系數(shù)；θi為移動(dòng)平均系數(shù)；εi為零均值白噪聲序列。則殘差項(xiàng)為：

(14)

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

圖4 模體演化矩陣及預(yù)測(cè)矩陣構(gòu)建過(guò)程

每相鄰的兩個(gè)時(shí)間窗口下的模體演化信息用一個(gè)MEM記錄，并把前T-1個(gè)MEM作為歷史序列，用整合移動(dòng)平均自回歸模型學(xué)習(xí)并預(yù)測(cè)出最后的MEPM。

2.3 基于模體演化的多因子鏈路預(yù)測(cè)方法

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

圖5 簡(jiǎn)單動(dòng)態(tài)有向網(wǎng)絡(luò)結(jié)構(gòu)示例圖

2.3.1模體演化影響因子

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

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

ei∈link(vm,vn,vj)

(15)

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

(16)

根據(jù)得到的MEPM和模體影響指數(shù)，可以計(jì)算出預(yù)測(cè)的T時(shí)刻中任意節(jié)點(diǎn)對(duì)(vm,vn)間的連邊概率：

vj∈neig(vm,vn)

(17)

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

2.3.2算法描述

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

算法2基于模體演化的多因子鏈路預(yù)測(cè)方法

輸入:1到T時(shí)刻的時(shí)間窗口

輸出:T時(shí)刻各節(jié)點(diǎn)對(duì)的連邊概率

1 初始化: 計(jì)算1～T-1相鄰時(shí)間窗口的模體演化矩陣；

2 計(jì)算T-1到T時(shí)間窗口的模體演化預(yù)測(cè)矩陣MEPM；

3 for each(vm,vn) do

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

//vj∈neig(vm,vn)

5 用式(15)計(jì)算模體影響指數(shù)；

6 end

7 用式(17)計(jì)算節(jié)點(diǎn)對(duì)的連邊概率；

8 end

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

3.1 實(shí)驗(yàn)設(shè)計(jì)

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

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

3.2 實(shí)驗(yàn)結(jié)果及分析

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

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

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

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

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

圖8 Enron數(shù)據(jù)集不同時(shí)間窗口下各算法AUC對(duì)比

圖9 Facebook-wosn-wall數(shù)據(jù)集不同時(shí)間窗口下各算法AUC對(duì)比

實(shí)驗(yàn)表明在SOTS的時(shí)間窗口劃分結(jié)果下進(jìn)行實(shí)驗(yàn)，各預(yù)測(cè)算法都能在選取的窗口大小中得到更為精準(zhǔn)的預(yù)測(cè)結(jié)果，說(shuō)明SOTS算法對(duì)動(dòng)態(tài)網(wǎng)絡(luò)時(shí)間窗口劃分的有效性；同時(shí)利用兩個(gè)時(shí)序相關(guān)函數(shù)的計(jì)算，也能更為快速地確定劃分結(jié)果，這也體現(xiàn)了SOTS算法的高效性。

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

圖10 不同數(shù)據(jù)集下各算法的AUC值對(duì)比

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

3.3 算法復(fù)雜度分析

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

4 結(jié) 語(yǔ)

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