陳東明， 袁澤枝， 黃新宇， 王冬琦

(東北大學(xué) 軟件學(xué)院， 遼寧 沈陽 110169)

網(wǎng)絡(luò)科學(xué)的研究不僅是在宏觀上挖掘不同復(fù)雜網(wǎng)絡(luò)之間的共性以及它們所遵循的普適性規(guī)律，從中觀層面對(duì)網(wǎng)絡(luò)群組結(jié)構(gòu)和層次結(jié)構(gòu)進(jìn)行研究，而且在微觀層面也提出節(jié)點(diǎn)的度及其度分布、最短距離等來表示網(wǎng)絡(luò)的測度.然而根據(jù)已有的信息構(gòu)建網(wǎng)絡(luò)模型時(shí)，所得到的觀測數(shù)據(jù)并不一定真實(shí)有效，或部分缺失、或摻雜錯(cuò)誤數(shù)據(jù)等，有時(shí)還會(huì)因時(shí)間因素導(dǎo)致不能夠獲得潛在的網(wǎng)絡(luò)信息，在仿真實(shí)驗(yàn)時(shí)得不到準(zhǔn)確的數(shù)據(jù)和理想的研究結(jié)論.因此，鏈路預(yù)測成為網(wǎng)絡(luò)信息挖掘的一個(gè)研究熱點(diǎn)[1].

鏈路預(yù)測(link prediction)是通過對(duì)已知的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)進(jìn)行分析，構(gòu)建預(yù)測算法以發(fā)現(xiàn)網(wǎng)絡(luò)中尚未存在連邊的節(jié)點(diǎn)對(duì)之間產(chǎn)生連邊的概率[2]，本質(zhì)上是從網(wǎng)絡(luò)鏈路的微觀層面解釋網(wǎng)絡(luò)結(jié)構(gòu)形成的原因.鏈路預(yù)測解決的是網(wǎng)絡(luò)中缺失信息的還原與預(yù)測問題.所謂還原，指的是對(duì)網(wǎng)絡(luò)中實(shí)際存在的但尚未被探測到的鏈路的發(fā)現(xiàn)，這種鏈路也被稱為未知鏈接(unknown links)；所謂預(yù)測，指的是對(duì)網(wǎng)絡(luò)中目前不存在但是未來很可能存在的鏈路的預(yù)測，這種鏈路也被稱為未來鏈接(future links).

復(fù)雜網(wǎng)絡(luò)中的鏈路預(yù)測算法主要是基于網(wǎng)絡(luò)靜態(tài)圖，即網(wǎng)絡(luò)規(guī)模以及節(jié)點(diǎn)間相互作用不變，然后分析其拓?fù)浣Y(jié)構(gòu)，推斷網(wǎng)絡(luò)的真實(shí)情況.然而現(xiàn)實(shí)網(wǎng)絡(luò)是動(dòng)態(tài)變化的，網(wǎng)絡(luò)結(jié)構(gòu)隨時(shí)間推移不斷變化，時(shí)態(tài)網(wǎng)絡(luò)(temporal networks)[3]中節(jié)點(diǎn)間產(chǎn)生連邊的時(shí)間信息對(duì)預(yù)測將來產(chǎn)生新鏈接的概率有重要的意義.Tang[4]將時(shí)態(tài)網(wǎng)絡(luò)切片，提出了時(shí)態(tài)距離、可達(dá)性等概念研究時(shí)態(tài)網(wǎng)絡(luò).Paranjape等[5]定義δ-motif小子圖作為分析時(shí)態(tài)網(wǎng)絡(luò)的工具，大大提高了算法的時(shí)間效率.Lei等[6]提出了一種非線性模型(GCN-GAN)來解決加權(quán)的時(shí)態(tài)網(wǎng)絡(luò)鏈路預(yù)測問題.該模型利用GCN計(jì)算各個(gè)時(shí)間切片的局部特征，然后將計(jì)算結(jié)果輸入到LSTM模型，刻畫網(wǎng)絡(luò)的動(dòng)態(tài)變化情況，再利用GAN生成預(yù)測結(jié)果.由于該方法的訓(xùn)練過程較為復(fù)雜，因此還需要進(jìn)一步優(yōu)化以實(shí)現(xiàn)大規(guī)模網(wǎng)絡(luò)上的鏈路預(yù)測.Yasami等[7]利用隨機(jī)多層網(wǎng)絡(luò)模型解決網(wǎng)絡(luò)中的鏈路缺失和未來鏈路的預(yù)測問題，并在仿真數(shù)據(jù)集和真實(shí)的DBLP數(shù)據(jù)集中表現(xiàn)出眾.然而，算法僅限于有向網(wǎng)絡(luò)，其他類型的網(wǎng)絡(luò)中缺少通用性.此外，一些統(tǒng)計(jì)學(xué)方法，如整合移動(dòng)自回歸模型，即ARIMA[8]也可以用于時(shí)態(tài)網(wǎng)絡(luò)鏈路預(yù)測研究，但受限于網(wǎng)絡(luò)數(shù)據(jù)的平穩(wěn)性檢驗(yàn)，因此對(duì)于網(wǎng)絡(luò)結(jié)構(gòu)隨時(shí)間變化較大的預(yù)測效果并不是十分理想.因此，時(shí)態(tài)網(wǎng)絡(luò)鏈路預(yù)測問題還有很大的研究空間.

1 問題描述

G={Gt|t=1,2,,m}.

(1)

其中，Gt表示網(wǎng)絡(luò)在t時(shí)刻的拓?fù)浣Y(jié)構(gòu).

時(shí)態(tài)網(wǎng)絡(luò)中的鏈路預(yù)測問題可以描述為：已知0～T時(shí)刻的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)變化情況，預(yù)測第T+1時(shí)刻的網(wǎng)絡(luò)中節(jié)點(diǎn)的連邊情況，簡單來說，就是根據(jù)網(wǎng)絡(luò)歷史信息預(yù)測下一時(shí)刻網(wǎng)絡(luò)中的連邊情況.以數(shù)學(xué)形式表示為

G={Gt|t=0,1,2,,T}?GT+1.

(2)

2 算法設(shè)計(jì)與分析

2.1 算法提出

鏈路的存在與當(dāng)前網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)有著密不可分的關(guān)系，如果在每一層的網(wǎng)絡(luò)時(shí)間快照中計(jì)算節(jié)點(diǎn)對(duì)的相似性值，則會(huì)得到對(duì)應(yīng)的一系列按時(shí)間順序排列的節(jié)點(diǎn)對(duì)之間的相似性值，記為

S={St(vx,vy)|t=1,2,,m}.

(3)

其中，St(vx,vy)表示在第t時(shí)刻的網(wǎng)絡(luò)結(jié)構(gòu)中節(jié)點(diǎn)對(duì)(vx,vy)的相似性值.在第t時(shí)刻，網(wǎng)絡(luò)可以視為靜態(tài)網(wǎng)絡(luò)，則可以利用靜態(tài)網(wǎng)絡(luò)中的相似性指標(biāo)計(jì)算相似性.

基于共同鄰居的JC指標(biāo)[9]、AA指標(biāo)[10]等在實(shí)驗(yàn)中都有很好的表現(xiàn)，而且算法復(fù)雜度低且適用于大型網(wǎng)絡(luò).盡管表現(xiàn)良好，但是由于所使用的網(wǎng)絡(luò)信息有限，因此預(yù)測準(zhǔn)確度不夠理想.該方法的另一個(gè)劣勢在于，鏈路預(yù)測指標(biāo)對(duì)于連邊的刻畫粒度比較粗糙.當(dāng)網(wǎng)絡(luò)中子圖結(jié)構(gòu)相似時(shí)，只利用共同鄰居這一信息會(huì)忽略鄰居節(jié)點(diǎn)間的連邊關(guān)系這一重要信息，具有不同結(jié)構(gòu)的節(jié)點(diǎn)對(duì)之間的相似性指標(biāo)值區(qū)分度不大.圖1所示為具有相同共同鄰居信息的網(wǎng)絡(luò)A和B，有兩對(duì)未連接的種子節(jié)點(diǎn)(A,a) 和(B,b)都只有3個(gè)共同鄰居節(jié)點(diǎn).

分別計(jì)算圖1所示網(wǎng)絡(luò)中兩個(gè)種子節(jié)點(diǎn)的連接概率，如果以Jaccard指標(biāo)值表示Score分?jǐn)?shù)值，那么在網(wǎng)絡(luò)A中S(vA,va)=3/7，在網(wǎng)絡(luò)B中S(vB,vb)=3/7.顯然，JC指標(biāo)賦予了它們相同的值，然而網(wǎng)絡(luò)B中的兩個(gè)種子節(jié)點(diǎn)顯然比網(wǎng)絡(luò)A中的兩個(gè)種子節(jié)點(diǎn)有更緊密的關(guān)系，局部相似性更高.因此可知，所利用的局部信息不能輕易地區(qū)分這兩對(duì)節(jié)點(diǎn)，也不足以完整地表示節(jié)點(diǎn)之間的相似性.

為了更加完備地利用網(wǎng)絡(luò)的結(jié)構(gòu)信息，本文利用鄰居節(jié)點(diǎn)的局部聚類信息來表達(dá)鏈路的結(jié)構(gòu)信息，這樣的優(yōu)勢在于可以表達(dá)與目標(biāo)鏈路具有相同結(jié)構(gòu)的一些其他重要鏈路的結(jié)構(gòu)信息.如何利用節(jié)點(diǎn)的聚集特性來描述種子節(jié)點(diǎn)之間產(chǎn)生連邊的可能性，提出以下兩種假設(shè)思路：

1)假設(shè)種子節(jié)點(diǎn)間產(chǎn)生鏈接的概率(或分值)等于節(jié)點(diǎn)間的相似性值，而相似性可以用種子節(jié)點(diǎn)的共同鄰居節(jié)點(diǎn)的聚類性表示.

2)如果種子節(jié)點(diǎn)間產(chǎn)生鏈接的概率(或分值)等于節(jié)點(diǎn)間的相似性值，假設(shè)鄰居節(jié)點(diǎn)的聚類性可以增強(qiáng)種子節(jié)點(diǎn)間原有的相似性.

在網(wǎng)絡(luò)中，連邊關(guān)系的局部聚集特性表現(xiàn)形式為所有的連邊都比較緊密，聚集成一個(gè)簇，也可以稱之為社區(qū)結(jié)構(gòu)，而節(jié)點(diǎn)的局部聚集特性可以由聚類系數(shù)(clustering coefficient)[11]來表示.用數(shù)學(xué)公式表達(dá)，其定義如下：

(4)

其中:Ci為節(jié)點(diǎn)的聚類系數(shù)；Ti是{ejk:vj,vk∈L(i),ejk∈E}中邊的數(shù)目，節(jié)點(diǎn)vj,vk是節(jié)點(diǎn)vi的鄰居節(jié)點(diǎn)，L(i)是節(jié)點(diǎn)vi的鄰居節(jié)點(diǎn)集合，ejk是節(jié)點(diǎn)vi的鄰居節(jié)點(diǎn)之間的連邊；ki表示節(jié)點(diǎn)vi的度.節(jié)點(diǎn)的聚類系數(shù)反映了節(jié)點(diǎn)的鄰居節(jié)點(diǎn)之間相互連接的概率.Ci取值在0與1之間，Ci越接近1，說明節(jié)點(diǎn)vi的鄰居們抱成一團(tuán)，節(jié)點(diǎn)vi的局部越緊密；Ci越接近0，說明節(jié)點(diǎn)vi的鄰居比較稀疏，整個(gè)結(jié)構(gòu)接近樹狀.

(5)

(6)

其中，|Θcn|表示對(duì)CN指標(biāo)歸一化處理，保證每個(gè)相似值平等對(duì)待，避免相似值過大，與事實(shí)相悖.由CN指標(biāo)計(jì)算公式Sxy=|Γ(x)∩Γ(y)|，其中Γ(x)是節(jié)點(diǎn)vx的鄰居節(jié)點(diǎn)的集合，z∈Γ(x)∩Γ(y).由此可知，CN指標(biāo)的相似性分值S∈[0,)，需要采用函數(shù)將S∈R(R為實(shí)數(shù))映射到[0, 1]，本文采用具有較好歸一化效果的Logistic函數(shù).結(jié)合式(5)和式(6)，可以得到適用于時(shí)態(tài)網(wǎng)絡(luò)的節(jié)點(diǎn)相似性計(jì)算公式：

(7)

(8)

本文將網(wǎng)絡(luò)時(shí)間快照計(jì)算得到的相似性值序列S={St(vx,vy)|t=1,2,,m}看作是一組動(dòng)態(tài)數(shù)列，為了使模型簡單易于計(jì)算，降低算法的計(jì)算復(fù)雜度，采用線性回歸(linear regression，LR)預(yù)測模型[12]作為基本的回歸預(yù)測模型，該模型計(jì)算效率高、性能良好，且模型的預(yù)測范圍較小，預(yù)測值在[0,1]之間.在文獻(xiàn)[13]中作者將科學(xué)家合作網(wǎng)絡(luò)劃分成網(wǎng)絡(luò)時(shí)間序列，然后利用有監(jiān)督和無監(jiān)督兩種方法進(jìn)行鏈路預(yù)測實(shí)驗(yàn)，結(jié)果表明在同等指標(biāo)下，無監(jiān)督預(yù)測的線性回歸模型(LR)表現(xiàn)較好.

(9)

結(jié)合式(7)和式(8)，利用一元線性回歸分析法可以計(jì)算最佳參數(shù)a和b的值，最終得到在第t時(shí)刻的相似性計(jì)算公式為

(10)

(11)

2.2 算法過程描述

本算法的核心思想是：將網(wǎng)絡(luò)劃分為多個(gè)時(shí)間快照，然后利用所有快照的歷史信息來預(yù)測未來時(shí)刻的網(wǎng)絡(luò)狀態(tài).時(shí)態(tài)網(wǎng)絡(luò)鏈路預(yù)測算法過程為

輸入：時(shí)態(tài)網(wǎng)絡(luò)G(V,E,T)

輸出：算法評(píng)價(jià)指標(biāo)值

1)讀取網(wǎng)絡(luò)G(V,E,T)，獲取網(wǎng)絡(luò)中所有可能出現(xiàn)的邊.

2)將時(shí)態(tài)網(wǎng)絡(luò)劃分為m個(gè)單層網(wǎng)絡(luò)，構(gòu)建一系列網(wǎng)絡(luò)時(shí)間快照{(diào)Gt|t=1,2,,m}.

3)根據(jù)式(7)、式(8)分別計(jì)算前m-1個(gè)時(shí)刻的節(jié)點(diǎn)對(duì)之間的相似性值，構(gòu)建相似性值時(shí)間序列.

4)選擇對(duì)比度量指標(biāo)[NCC, NCCP, CN, JC, AA, RA]，計(jì)算在其他相似性指標(biāo)下的節(jié)點(diǎn)對(duì)的相似性值.

5)根據(jù)得到的前m-1個(gè)時(shí)刻的分?jǐn)?shù)值序列訓(xùn)練得到預(yù)測模型，采用式(10)、式(11)計(jì)算第m時(shí)刻節(jié)點(diǎn)間的相似性值.

6)計(jì)算衡量算法的多個(gè)評(píng)價(jià)指標(biāo)，如AUC(接受者操作特性曲線下方的面積)、精確度P、召回率R和F1指標(biāo)等.

2.3 復(fù)雜度分析

CN指標(biāo)[14]的時(shí)間復(fù)雜度與節(jié)點(diǎn)的度有關(guān)，假設(shè)網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)為N,整個(gè)網(wǎng)絡(luò)的平均度為k，則計(jì)算共同鄰居的時(shí)間復(fù)雜度為O(k)，則CN算法的時(shí)間復(fù)雜度為O(N2k).基于共同鄰居的JC，AA，RA算法[15]與CN算法有類似的計(jì)算過程，因此它們有相同的時(shí)間復(fù)雜度.基于隨機(jī)游走的SimRank算法[16]的時(shí)間復(fù)雜度為O(Nkl)，其中l(wèi)是隨機(jī)游走的步數(shù).本文所提出的兩種相似性度量方法NCC和NCCP需要計(jì)算節(jié)點(diǎn)的聚類系數(shù)，進(jìn)行鏈路預(yù)測過程的時(shí)間復(fù)雜度為O(N2k).以上算法的時(shí)間復(fù)雜度比較如表1所示.

表1 經(jīng)典算法的時(shí)間復(fù)雜度比較

由表1可以看出，SR算法時(shí)間復(fù)雜度最低，是O(Nk)，因此效率最高.但由于其屬于全局迭代算法，包含隨機(jī)游走過程，因此實(shí)驗(yàn)結(jié)果并不穩(wěn)定.本文提出算法的時(shí)間復(fù)雜度與其他同類算法相同，都是O(N2k)，雖然略高于SR算法，但因?yàn)槠洳淮嬖陔S機(jī)過程，保證了結(jié)果的穩(wěn)定性，因此具有更好的適用性.

3 實(shí)驗(yàn)分析

3.1 相似性度量方法對(duì)比實(shí)驗(yàn)

本文選取不同領(lǐng)域的6個(gè)真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集:空手道俱樂部網(wǎng)絡(luò)(Karate)、海豚社會(huì)關(guān)系網(wǎng)絡(luò)(Dolphins)、911恐怖襲擊網(wǎng)絡(luò)(911data)、美國政治書籍網(wǎng)絡(luò)(Polbooks)、美國大學(xué)生足球俱樂部(Footballs)和科學(xué)家合作網(wǎng)絡(luò)(Scientists).6個(gè)真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集的統(tǒng)計(jì)特征見表2.

本文采用隨機(jī)抽樣法劃分網(wǎng)絡(luò)數(shù)據(jù)集，測試集的比例默認(rèn)設(shè)定為10%.選擇傳統(tǒng)的4個(gè)鏈路預(yù)測方法作為對(duì)比算法，分別是基于共同鄰居的CN指標(biāo)、Jaccard指標(biāo)(JC)、AA指標(biāo)、RA指標(biāo).循環(huán)重復(fù)實(shí)驗(yàn)多次，采用評(píng)價(jià)指標(biāo)AUC的平均值作為算法的評(píng)估結(jié)果，如表3所示.

表2 網(wǎng)絡(luò)的統(tǒng)計(jì)特征

注：|V|表示網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)；|E|表示網(wǎng)絡(luò)中的連邊數(shù)；k表示網(wǎng)絡(luò)的平均度；|C|為網(wǎng)絡(luò)的平均聚類系數(shù)；表示網(wǎng)絡(luò)的平均連通程度；|D|表示網(wǎng)絡(luò)的平均最短路徑的距離.

表3 不同網(wǎng)絡(luò)數(shù)據(jù)集的AUC值

注：表中黑體加下劃線標(biāo)注的是最大值，黑體標(biāo)注的是次大值.

由表3可知，對(duì)于Karate，Dolphins和911data這3個(gè)較小規(guī)模的網(wǎng)絡(luò)，AA和RA指標(biāo)具有較高的預(yù)測精確度，所提出的NCC和NCCP指標(biāo)表現(xiàn)也比較優(yōu)異.在Polbooks網(wǎng)絡(luò)數(shù)據(jù)集中，NCCP和RA指標(biāo)表現(xiàn)顯著，且平均AUC值達(dá)到了0.873.在Scientists網(wǎng)絡(luò)中AUC值達(dá)到了0.931，預(yù)測精確度高，NCCP指標(biāo)預(yù)測效果最好.實(shí)驗(yàn)結(jié)果表明，網(wǎng)絡(luò)鄰居節(jié)點(diǎn)的聚類系數(shù)可以提高預(yù)測精確度.

為了更加清晰地展現(xiàn)NCC和NCCP指標(biāo)的性能，做了以下顯著性檢驗(yàn)：本文采用皮爾遜相關(guān)系數(shù)進(jìn)行檢驗(yàn)，首先將NCC和NCCP指標(biāo)與CN，JC，AA，RA指標(biāo)進(jìn)行對(duì)比計(jì)算，分別得到相應(yīng)指標(biāo)的假設(shè)機(jī)率(p)，然后把分別得到的p加和取平均得到NCC指標(biāo)的p為0.000 6, NCCP指標(biāo)的p為0.000 8，均遠(yuǎn)小于0.05.所以本實(shí)驗(yàn)效果較顯著.

為了驗(yàn)證NCCP相似性指標(biāo)對(duì)CN指標(biāo)的增強(qiáng)效果，本文利用AUC值的對(duì)比情況來刻畫，實(shí)驗(yàn)得到如表4所示數(shù)據(jù).由后兩列計(jì)算結(jié)果可以看出，在添加鄰居節(jié)點(diǎn)的聚類系數(shù)后構(gòu)建的NCCP指標(biāo)比CN指標(biāo)預(yù)測效果有了普遍的提高，說明NCCP有一定的增強(qiáng)效果.

表4 NCCP指標(biāo)的增強(qiáng)效果

注：α表示NCCP比CN增強(qiáng)的部分與CN的百分比；β表示NCCP比NCC增強(qiáng)的部分與NCC的百分比.

根據(jù)表4結(jié)果可知，NCC指標(biāo)與NCCP指標(biāo)在整體上優(yōu)于CN指標(biāo).

3.2 時(shí)態(tài)網(wǎng)絡(luò)鏈路預(yù)測實(shí)驗(yàn)

為了驗(yàn)證時(shí)態(tài)網(wǎng)絡(luò)的鏈路預(yù)測算法的效果，本文使用Email-Eu-core temporal network時(shí)態(tài)網(wǎng)絡(luò)數(shù)據(jù)集[5].該網(wǎng)絡(luò)是根據(jù)歐洲某大型研究機(jī)構(gòu)內(nèi)部成員的電子郵件往來關(guān)系所構(gòu)建的，對(duì)所有接收和發(fā)出的郵件信息內(nèi)容作匿名處理.數(shù)據(jù)集不包含成員和其他地方地區(qū)的通信郵件，僅限于機(jī)構(gòu)內(nèi)部核心成員之間的通信，完整的數(shù)據(jù)集包含了來自4個(gè)部門成員之間的所有電子郵件，時(shí)間跨度為802天.本文所使用的網(wǎng)絡(luò)數(shù)據(jù)集來自第三個(gè)部門(Dept3)，該數(shù)據(jù)集有89個(gè)節(jié)點(diǎn)、12 216條時(shí)態(tài)邊，轉(zhuǎn)化為靜態(tài)網(wǎng)絡(luò)則有1 506條邊，時(shí)間跨度為802天.節(jié)點(diǎn)代表機(jī)構(gòu)內(nèi)部的部門成員，每條連邊代表他們之間有一次郵件往來，數(shù)據(jù)集中每條數(shù)據(jù)(u,v,t)表示在時(shí)間t從用戶u向用戶v發(fā)送了電子郵件.

利用精確度P、召回率R和F1指標(biāo)對(duì)預(yù)測結(jié)果進(jìn)行評(píng)價(jià)，如果按天劃分時(shí)態(tài)網(wǎng)絡(luò)，那么每日的郵件數(shù)量即代表每層網(wǎng)絡(luò)的連邊數(shù)目，得到如表5所示結(jié)果.

表5 按日劃分時(shí)態(tài)網(wǎng)絡(luò)預(yù)測結(jié)果的評(píng)價(jià)指標(biāo)值

由表5可知，NCC指標(biāo)的預(yù)測結(jié)果明顯優(yōu)于其他指標(biāo)，說明基于鄰居節(jié)點(diǎn)聚類的度量指標(biāo)可以提高鏈路預(yù)測精確度.表5中的P值都普遍偏低，究其原因，一方面時(shí)態(tài)網(wǎng)絡(luò)數(shù)據(jù)集本身較小，另一方面網(wǎng)絡(luò)劃分的層數(shù)過多.按天劃分時(shí)態(tài)網(wǎng)絡(luò)導(dǎo)致每層的連邊都特別稀疏，信息很零散，使所有指標(biāo)的預(yù)測效果都偏低.

如果按月劃分時(shí)態(tài)網(wǎng)絡(luò), 得到如表6所示結(jié)果，NCC指標(biāo)預(yù)測結(jié)果仍然優(yōu)于其他指標(biāo)，顯示其有效性；且3個(gè)評(píng)價(jià)指標(biāo)值比按天劃分的網(wǎng)絡(luò)的評(píng)價(jià)指標(biāo)值都有所提高，說明時(shí)態(tài)網(wǎng)絡(luò)鏈路預(yù)測的精確度還與網(wǎng)絡(luò)劃分的層數(shù)有關(guān)系，當(dāng)網(wǎng)絡(luò)劃分過細(xì)時(shí)，網(wǎng)絡(luò)分辨率很高，則預(yù)測效果不理想.

表6 按月劃分時(shí)態(tài)網(wǎng)絡(luò)預(yù)測結(jié)果的評(píng)價(jià)指標(biāo)值

選取目前公認(rèn)的比較好的RA指標(biāo)結(jié)合ARIMA模型作為基線算法，與本文提出的NCC指標(biāo)結(jié)合線性回歸模型進(jìn)行比較，使用按月劃分的網(wǎng)絡(luò)數(shù)據(jù)集，隨著層數(shù)的增加得到的AUC結(jié)果如圖2所示.

由圖2可看出，除了層數(shù)為4和13的時(shí)候本文提出的方法低于ARIMA_RA方法，其他情況均好于ARIMA_RA方法.

綜合以上實(shí)驗(yàn)結(jié)果，本文所提出的NCC指標(biāo)在對(duì)時(shí)態(tài)網(wǎng)絡(luò)的鏈路進(jìn)行預(yù)測時(shí)優(yōu)于其他相似性指標(biāo)，說明在考慮鄰居節(jié)點(diǎn)的聚集情況后，更貼近真實(shí)網(wǎng)絡(luò)中人們交流協(xié)作的過程，因此預(yù)測效果更好.并且，從以上兩種劃分形式可以看出，時(shí)態(tài)網(wǎng)絡(luò)的預(yù)測效率還與時(shí)間的劃分和時(shí)態(tài)網(wǎng)絡(luò)模型有密切關(guān)系.

將網(wǎng)絡(luò)劃分為m個(gè)時(shí)間快照，然后利用所有快照的歷史信息來預(yù)測未來時(shí)刻的網(wǎng)絡(luò)狀態(tài)是本文方法的研究思路.然而，在現(xiàn)實(shí)網(wǎng)絡(luò)中，不同時(shí)刻網(wǎng)絡(luò)狀態(tài)對(duì)預(yù)測未來時(shí)刻網(wǎng)絡(luò)狀態(tài)所貢獻(xiàn)的重要性是不同的，例如信息傳播過程中，最近時(shí)間節(jié)點(diǎn)的信息最重要，歷史時(shí)間中的過時(shí)信息的影響力不大.為了在本次時(shí)態(tài)網(wǎng)絡(luò)鏈路預(yù)測中驗(yàn)證該思想，選擇預(yù)測時(shí)刻(即第m層)的前n層網(wǎng)絡(luò)信息進(jìn)行預(yù)測.實(shí)驗(yàn)中n取1,2,4,7,9,10，得到如表7，表8所示的預(yù)測結(jié)果.

表7 預(yù)測結(jié)果精確度評(píng)價(jià)指標(biāo)值

由表7和表8中數(shù)據(jù)可知，n=1時(shí)所有預(yù)測算法的精確度都相同；當(dāng)n=2時(shí)，兩個(gè)評(píng)價(jià)指標(biāo)在所有算法中的值都開始減小，此時(shí)AA指標(biāo)預(yù)測效果最好；當(dāng)n逐漸增大時(shí)，兩個(gè)評(píng)價(jià)指標(biāo)都普遍呈減小的趨勢，這說明越貼近預(yù)測時(shí)間的網(wǎng)絡(luò)結(jié)構(gòu)對(duì)最終結(jié)果的影響越大.而且，在n增大的過程中，本文所提出的NCC和NCCP指標(biāo)對(duì)時(shí)態(tài)網(wǎng)絡(luò)的鏈路預(yù)測效果逐漸開始顯示其優(yōu)越性.

表8 預(yù)測結(jié)果F1值評(píng)價(jià)指標(biāo)值

4 結(jié) 語

本文將時(shí)態(tài)網(wǎng)絡(luò)劃分為一系列時(shí)間快照序列，利用所提出的度量指標(biāo)計(jì)算每一層網(wǎng)絡(luò)中的節(jié)點(diǎn)對(duì)相似性，構(gòu)建節(jié)點(diǎn)對(duì)相似性時(shí)間序列，然后，結(jié)合時(shí)間序列回歸模型預(yù)測節(jié)點(diǎn)對(duì)未來的相似性.實(shí)驗(yàn)結(jié)果表明，利用鄰居節(jié)點(diǎn)的聚類信息可以提高預(yù)測精度，利用真實(shí)郵件網(wǎng)絡(luò)數(shù)據(jù)集驗(yàn)證了所提出的指標(biāo)的預(yù)測效果優(yōu)越性，并且實(shí)驗(yàn)結(jié)果證明越接近預(yù)測時(shí)間的網(wǎng)絡(luò)結(jié)構(gòu)對(duì)預(yù)測結(jié)果影響越大.