一種基于博弈論的時(shí)序網(wǎng)絡(luò)鏈路預(yù)測(cè)方法

劉 留 王煜堯 倪琦瑄 曹 杰 卜 湛

1(南京財(cái)經(jīng)大學(xué)信息工程學(xué)院 南京 210013)2(南京理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院 南京 210094)

許多現(xiàn)實(shí)世界的網(wǎng)絡(luò)系統(tǒng)是非靜態(tài)的，節(jié)點(diǎn)間的連接關(guān)系隨時(shí)間動(dòng)態(tài)變化，此類(lèi)網(wǎng)絡(luò)可由一系列包含時(shí)間戳的鏈路集合[1]表示.在動(dòng)態(tài)網(wǎng)絡(luò)研究領(lǐng)域中，除了研究最為廣泛的社區(qū)發(fā)現(xiàn)問(wèn)題[2-3]，鏈路預(yù)測(cè)問(wèn)題[4-6]研究如何利用網(wǎng)絡(luò)歷史拓?fù)湫畔㈩A(yù)測(cè)未來(lái)的鏈路存在情況，是一項(xiàng)具有重要研究意義的課題.鏈路預(yù)測(cè)對(duì)于人們理解網(wǎng)絡(luò)演化[7]規(guī)律至關(guān)重要，且在諸多實(shí)際應(yīng)用中發(fā)揮著重要作用，如預(yù)測(cè)蛋白質(zhì)間的相互作用[8]、社交網(wǎng)絡(luò)中的朋友推薦[9]和科研網(wǎng)絡(luò)的合作推薦[10]等.

區(qū)別于已有的鏈路預(yù)測(cè)研究，本文旨在研究時(shí)序網(wǎng)絡(luò)[11]的演化機(jī)制，即給定一組由固定節(jié)點(diǎn)集合構(gòu)成的靜態(tài)網(wǎng)絡(luò)序列，如g1,g2,…,gt,我們嘗試預(yù)測(cè)該網(wǎng)絡(luò)在未來(lái)時(shí)刻t+1到t+T的拓?fù)浣Y(jié)構(gòu).一方面，傳統(tǒng)的鏈路預(yù)測(cè)方法[12]多關(guān)注于靜態(tài)網(wǎng)絡(luò)的鏈路預(yù)測(cè)問(wèn)題，忽略了每條鏈路上的時(shí)間戳信息，故不能被直接應(yīng)用于解決時(shí)序網(wǎng)絡(luò)的鏈路預(yù)測(cè)問(wèn)題.另一方面，現(xiàn)實(shí)世界的網(wǎng)絡(luò)系統(tǒng)通常具有較大的規(guī)模，包含海量有復(fù)雜聯(lián)系的網(wǎng)絡(luò)參與者.例如，一個(gè)包含105個(gè)節(jié)點(diǎn)和106條鏈路的稀疏網(wǎng)絡(luò)，若預(yù)測(cè)未來(lái)可能生成的新鏈路，其搜索空間的數(shù)量級(jí)為1010；而預(yù)測(cè)未來(lái)可能消失鏈路的搜索空間的數(shù)量級(jí)為106，僅占前者的0.01%.受限于上述真實(shí)網(wǎng)絡(luò)的這種稀疏性特性，有監(jiān)督的鏈路預(yù)測(cè)方法會(huì)面臨不同程度的分類(lèi)樣本分布失衡問(wèn)題.

基于上述分析，本文構(gòu)建了一個(gè)高效的鏈路預(yù)測(cè)框架.首先，采用ε-鄰接網(wǎng)絡(luò)序列定義時(shí)序網(wǎng)絡(luò)的表示模型，從包含時(shí)間戳的鏈路集合中生成真實(shí)的網(wǎng)絡(luò)演化序列.另外，由于生存分析中的Cox比例風(fēng)險(xiǎn)模型不需對(duì)生存時(shí)間的分布作出假定，僅通過(guò)一個(gè)模型就可分析生存時(shí)間的分布規(guī)律.因此，我們?yōu)槊織l鏈路關(guān)聯(lián)一組基于拓?fù)湎嗨菩缘奶卣飨蛄?，并借助Cox比例風(fēng)險(xiǎn)模型分別學(xué)習(xí)鏈路的消失和重連概率.然而，現(xiàn)實(shí)中的大多數(shù)網(wǎng)絡(luò)為稀疏網(wǎng)絡(luò)，即大多數(shù)的節(jié)點(diǎn)對(duì)之間不存在鏈路.因此，為壓縮搜索空間，我們將節(jié)點(diǎn)對(duì)之間的連邊情況模擬為2個(gè)玩家之間的博弈，進(jìn)而提出一種基于動(dòng)態(tài)博弈的雙向選擇機(jī)制來(lái)預(yù)測(cè)未來(lái)的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu).除此之外，由于計(jì)算特征向量所采用的鄰近性指標(biāo)是基于每個(gè)節(jié)點(diǎn)的鄰居來(lái)計(jì)算得到的，故我們將可能與節(jié)點(diǎn)i發(fā)生重連的節(jié)點(diǎn)約束在距i的最短路徑距離不超過(guò)2的范圍內(nèi).此舉有效地壓縮了鏈路預(yù)測(cè)的搜索空間，提高了算法的計(jì)算效率，緩解了稀疏網(wǎng)絡(luò)帶來(lái)的分類(lèi)樣本分布失衡問(wèn)題.

1 相關(guān)工作

傳統(tǒng)的復(fù)雜網(wǎng)絡(luò)鏈路預(yù)測(cè)方法主要分為3類(lèi)：1)無(wú)監(jiān)督預(yù)測(cè)方法；2)有監(jiān)督預(yù)測(cè)方法；3)基于概率模型的預(yù)測(cè)方法.

無(wú)監(jiān)督預(yù)測(cè)方法，也被稱(chēng)為評(píng)分方法[13-14].此類(lèi)方法的基本假設(shè)是：若2個(gè)節(jié)點(diǎn)拓?fù)湎嗨贫仍酱螅鼈冊(cè)谖磥?lái)形成鏈路的概率越高.基于此假設(shè)，無(wú)監(jiān)督預(yù)測(cè)方法通過(guò)定義一系列節(jié)點(diǎn)對(duì)的相似性函數(shù)，來(lái)刻畫(huà)網(wǎng)絡(luò)中任一鏈路的存在概率.其中最常用的相似性函數(shù)包括CN(common neighbor index)[15]，JC(Jaccard coefficient)[16]，PA(preferential attach-ment index)[17]，AA(adamic-adar index)[18]等.由于這些相似性函數(shù)多采用網(wǎng)絡(luò)的局部拓?fù)湫畔?，故此?lèi)無(wú)監(jiān)督預(yù)測(cè)方法通常具有較低的時(shí)間復(fù)雜度.此外，一些無(wú)監(jiān)督預(yù)測(cè)方法則基于節(jié)點(diǎn)對(duì)連通路徑特征來(lái)定義節(jié)點(diǎn)對(duì)的相似性函數(shù).此類(lèi)方法的基本假設(shè)是：若2個(gè)節(jié)點(diǎn)間的距離越短，則它們?cè)谖磥?lái)形成鏈路的概率越高.例如，Katz[19]不僅考慮2個(gè)節(jié)點(diǎn)之間所有的路徑，同時(shí)還利用路徑的權(quán)重來(lái)計(jì)算它們之間的相似性.Lü等人[20]提出的局部路徑(local path, LP)指標(biāo)同時(shí)考慮直接鄰居和間接鄰居，獲取的路徑信息相對(duì)更為穩(wěn)定、可靠.Yang等人[21]提出了一種基于聚類(lèi)和決策樹(shù)的鏈路預(yù)測(cè)方法.基于隨機(jī)游走的鏈路預(yù)測(cè)算法的基本假設(shè)是：若某個(gè)節(jié)點(diǎn)進(jìn)行隨機(jī)游走，到達(dá)另外一個(gè)節(jié)點(diǎn)所需要的平均游走步數(shù)最少，此時(shí)2個(gè)節(jié)點(diǎn)的相似性最高.Lichtenwalter等人[22]在隨機(jī)游走的基礎(chǔ)上進(jìn)行了一定的改進(jìn)，提出了PropFlow方法.Tong等人[23]提出了一種新的隨機(jī)游走方法，充分考慮網(wǎng)絡(luò)中普遍存在的社區(qū)結(jié)構(gòu)特性.Jin等人[24]提出一種基于路徑反轉(zhuǎn)影響和隨機(jī)游走矩陣的鏈路預(yù)測(cè)方法.與經(jīng)典的基于鄰居相似度的無(wú)監(jiān)督預(yù)測(cè)方法相比，基于節(jié)點(diǎn)對(duì)連通路徑特征的無(wú)監(jiān)督預(yù)測(cè)方法考慮了網(wǎng)絡(luò)的全局拓?fù)涮卣?，其預(yù)測(cè)準(zhǔn)確率相對(duì)較高，但節(jié)點(diǎn)對(duì)路徑特征的計(jì)算過(guò)程具有較高的時(shí)間復(fù)雜度.

有監(jiān)督預(yù)測(cè)方法將鏈路預(yù)測(cè)問(wèn)題轉(zhuǎn)化為二進(jìn)制分類(lèi)問(wèn)題，根據(jù)歷史的網(wǎng)絡(luò)演化序列構(gòu)建訓(xùn)練樣本，并借助現(xiàn)有的分類(lèi)器，如邏輯回歸[25]、支持向量機(jī)[26]、決策樹(shù)[27]、多層感知器神經(jīng)網(wǎng)絡(luò)[28]和樸素貝葉斯[29]等，訓(xùn)練分類(lèi)器參數(shù)，進(jìn)而再利用訓(xùn)練好的分類(lèi)器進(jìn)行鏈路預(yù)測(cè).例如，Pujari等人[30]提出一種監(jiān)督式的排序融合方法對(duì)復(fù)雜網(wǎng)絡(luò)進(jìn)行鏈路預(yù)測(cè).Chen等人[31]利用正則化參數(shù)來(lái)完成貝葉斯推理，進(jìn)而提高學(xué)習(xí)潛在特性的辨別能力.Nguyen-Thi等人[32]提出一種基于徑向基函數(shù)(radial basis function, RBF)的支持向量機(jī)(support vector machine, SVM)分類(lèi)器，可有效提高預(yù)測(cè)精度且降低分類(lèi)器的訓(xùn)練時(shí)間.基于監(jiān)督學(xué)習(xí)的鏈路預(yù)測(cè)方法在構(gòu)建訓(xùn)練樣本時(shí)都不同程度地面臨樣本類(lèi)別分布失衡問(wèn)題.真實(shí)的網(wǎng)絡(luò)系統(tǒng)呈現(xiàn)極強(qiáng)的稀疏特征，假定時(shí)刻t存在一個(gè)包含n個(gè)節(jié)點(diǎn)和m條鏈路的無(wú)向網(wǎng)絡(luò)gt，其稀疏性表現(xiàn)為m?n(n-1)2，其中n(n-1)2表示gt網(wǎng)絡(luò)最大可能的無(wú)向鏈路數(shù)量.當(dāng)gt演化至?xí)r刻t′，我們可以根據(jù)網(wǎng)絡(luò)gt′與網(wǎng)絡(luò)gt的拓?fù)洳町?，分別構(gòu)建相應(yīng)的訓(xùn)練集來(lái)預(yù)測(cè)未來(lái)的消失鏈路和重連鏈路.以重連鏈路預(yù)測(cè)為例，我們可以將{eij|eij∈(gt′-gt)}中的鏈路標(biāo)記為正例樣本，將{eij|eij?(gt′-gt)}中的鏈路標(biāo)記為負(fù)例樣本.考慮到真實(shí)網(wǎng)絡(luò)的動(dòng)態(tài)演化呈現(xiàn)顯著的漸進(jìn)性，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的變化是一個(gè)相對(duì)緩慢的過(guò)程.由于|{eij|eij∈(gt′-gt)}|?|{eij|eij?(gt′-gt)}|，采用上述方法構(gòu)建的訓(xùn)練集中，正例樣本和負(fù)例樣本存在嚴(yán)重的分布失衡現(xiàn)象，傳統(tǒng)的機(jī)器學(xué)習(xí)分類(lèi)器難以訓(xùn)練出理想的重連鏈路預(yù)測(cè)模型.

基于概率模型的鏈路預(yù)測(cè)的基本思想是建立一個(gè)含有多個(gè)可調(diào)參數(shù)的模型，利用某種優(yōu)化策略尋找參數(shù)的最優(yōu)值，從而使得網(wǎng)絡(luò)的結(jié)構(gòu)和關(guān)系特征能夠在模型中得到更好的體現(xiàn).網(wǎng)絡(luò)中任意節(jié)點(diǎn)對(duì)的重連概率可表示為基于最優(yōu)參數(shù)配置的條件概率.Wang等人[33]提出了一個(gè)基于局部概率模型(local probabilistic model, LPM)的鏈路預(yù)測(cè)方法，可極大地降低大規(guī)模復(fù)雜網(wǎng)絡(luò)鏈路預(yù)測(cè)問(wèn)題的時(shí)間復(fù)雜度和空間復(fù)雜度.Coutant等人[34]提出了一種基于聚類(lèi)不確定性的概率關(guān)系模型(probabilistic relational models with clustering uncertainty, PRM-CU)用于分析復(fù)雜網(wǎng)絡(luò)的級(jí)聯(lián)失效，該概率模型能夠充分利用網(wǎng)絡(luò)的拓?fù)湫畔?，衡量?jié)點(diǎn)對(duì)的交互能力，能夠有效地提高鏈路預(yù)測(cè)的準(zhǔn)確性.由于網(wǎng)絡(luò)結(jié)構(gòu)本身較為復(fù)雜，為表示更高層次的非線(xiàn)性網(wǎng)絡(luò)結(jié)構(gòu)，Wang等人[35]提出了結(jié)構(gòu)化深層網(wǎng)絡(luò)嵌入模型(structural deep network embedding， SDNE).與傳統(tǒng)鏈路預(yù)測(cè)方法相比，SDNE模型能夠有效地提取網(wǎng)絡(luò)的局部和全局結(jié)構(gòu)信息，重構(gòu)網(wǎng)絡(luò)結(jié)構(gòu)，進(jìn)而得到更高的預(yù)測(cè)精度.

此外，還有一些鏈路預(yù)測(cè)方法考慮了鏈路的時(shí)間戳信息和網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)特征.例如，Sharan等人[36]提出了基于不同時(shí)間關(guān)系的分類(lèi)模型，采用2個(gè)實(shí)體間動(dòng)態(tài)關(guān)系信息的關(guān)系模型.Rossi等人[37]提出了基于時(shí)序關(guān)系從屬分類(lèi)的集成預(yù)測(cè)方法.Clauset等人[38]提出了一種利用網(wǎng)絡(luò)層次結(jié)構(gòu)進(jìn)行鏈路預(yù)測(cè)的方法，且在具有明顯層次結(jié)構(gòu)的網(wǎng)絡(luò)中，該方法能取得更好的預(yù)測(cè)性能.這些鏈路預(yù)測(cè)方法大多對(duì)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)有較高的要求，且計(jì)算時(shí)間復(fù)雜度普遍較高.

2 問(wèn)題定義

現(xiàn)實(shí)世界的時(shí)序網(wǎng)絡(luò)可表示為一個(gè)時(shí)序鏈路集γ={ip,jp,τp|p=1,2,…,M}，其中ip,jp,τp表示一個(gè)帶有時(shí)間戳的時(shí)序鏈路，表明節(jié)點(diǎn)ip和節(jié)點(diǎn)jp在時(shí)刻τp是連通的.當(dāng)忽略時(shí)序鏈路的時(shí)間戳和重復(fù)鏈路時(shí)，時(shí)序網(wǎng)絡(luò)就退化為一個(gè)靜態(tài)網(wǎng)絡(luò)g(γ)={eij|?ip,jp,τp∈γ}.

定義1.δ-時(shí)序范式.時(shí)刻t的δ-時(shí)序范式是一個(gè)有序鏈路序列Mt(δ)=its,jts,τts,…,ite,jte,τte，滿(mǎn)足(τts≤…≤τte)∧(δ=τte-τts)，且靜態(tài)網(wǎng)絡(luò)gt(δ)=(Vt(δ),Et(δ))，Et(δ)?Vt(δ)×Vt(δ)是連通的.

靜態(tài)網(wǎng)絡(luò)gt演化至與其ε-鄰接的網(wǎng)絡(luò)gt′包含3種可能情況：1)從gt中消失的鏈路；2)gt中任意2個(gè)不連通的節(jié)點(diǎn)形成的鏈路；3)至少有1個(gè)外部節(jié)點(diǎn)參與形成的鏈路.由于外部信息具有較大的隨機(jī)性，本文將重點(diǎn)關(guān)注前2種情況的鏈路預(yù)測(cè)問(wèn)題，并假設(shè)出現(xiàn)在所有周期的節(jié)點(diǎn)集合是固定的.

定義3.ε-鄰接網(wǎng)絡(luò)序列.從初始網(wǎng)絡(luò)g0(δ)=(V,E0)開(kāi)始，ε-鄰接網(wǎng)絡(luò)序列由一系列耦合的靜態(tài)網(wǎng)絡(luò)組成，即Gε(g0(δ))={g1,g2,…}，滿(mǎn)足?t≥1：1)gt-1和gt是ε-鄰接的；2)Vt?V，Et?V×V.

為強(qiáng)調(diào)從gt-1到gt的網(wǎng)絡(luò)演化過(guò)程，令Mt和Rt分別表示從gt-1消失的鏈路集合和在gt中新生成的鏈路集合.顯然，Mt=Et-1-Et和Rt=Et-Et-1.

定義4.多層網(wǎng)絡(luò)[39]序列.令ε-鄰接網(wǎng)絡(luò)序列Gε(g0(δ))={E1,E2,…}中任意第t個(gè)周期的靜態(tài)網(wǎng)絡(luò)都對(duì)應(yīng)一個(gè)多層網(wǎng)絡(luò)Mt(L)={Et,Pt(L)}，其中，Et?V×V是周期t中靜態(tài)網(wǎng)絡(luò)的鏈路集，Pt(L)?V×V是gt最近L個(gè)靜態(tài)網(wǎng)絡(luò)投影所得的鏈路集：

(1)

這樣，由任意周期窗口L導(dǎo)出的多層網(wǎng)絡(luò)序列表示為MNS(L)={M0(L),M1(L),…}.

定義5.拓?fù)湎嗨菩院瘮?shù).令Ni={j|eij∈E*}表示節(jié)點(diǎn)i在某個(gè)靜態(tài)網(wǎng)絡(luò)中的鄰居集合，鏈路ip,jp,τp的拓?fù)湎嗨菩钥捎梢恍┫嗨菩院瘮?shù)度量計(jì)算得到.例如，CN[15]，JC[16]，Sa(salton index)，So(sorensen index)，HP(hub promoted index)，HD(hub depressed index)，LN(Leicht-Newman index)，PA[17]，AA[18]等，具體為

定義6.消失鏈路序列(missing link sequence，MLS).給定一個(gè)ε-鄰接網(wǎng)絡(luò)序列Gε(g0(δ))，由此導(dǎo)出的消失鏈路序列表示為GM(g0(δ))={M1,M2,…}，滿(mǎn)足?t≥1,Mt=Et-1-Et.

定義7.重連鏈路序列(reconnected link sequ-ence， RLS).給定一個(gè)ε-鄰接網(wǎng)絡(luò)序列Gε(g0(δ))，由此導(dǎo)出的重連鏈路序列表示為GR(g0(δ))={R1,R2,…}，滿(mǎn)足?t≥1,Rt=Et-Et-1.

(2)

(3)

(4)

(5)

3 時(shí)序網(wǎng)絡(luò)鏈路預(yù)測(cè)模型

基于定義8和定義9，我們可借助于Cox比例風(fēng)險(xiǎn)模型分別學(xué)習(xí)鏈路消失和重連所對(duì)應(yīng)特征向量的權(quán)重系數(shù).Cox比例風(fēng)險(xiǎn)模型采用最大似然估計(jì)方法對(duì)模型參數(shù)進(jìn)行估計(jì)，上述2個(gè)事件對(duì)應(yīng)的協(xié)變量系數(shù)WM*和WR*可分別通過(guò)式(6)(7)學(xué)習(xí)得到：

(6)

(7)

(8)

(9)

(10)

Ψt對(duì)應(yīng)的納什均衡點(diǎn)集為

(11)

Et+1=Q(Et,Θt,Φt)=Et-Dt,M+Dt,R.

(12)

4 基于自治計(jì)算的網(wǎng)絡(luò)演化算法

算法1.網(wǎng)絡(luò)演化算法.

輸入：初始靜態(tài)網(wǎng)絡(luò)g0(δ)=(V,E0)、時(shí)間窗口長(zhǎng)度L、最大迭代次數(shù)I、消失鏈路的協(xié)變量系數(shù)WM*、重連鏈路的協(xié)變量系數(shù)WR*；

①t←0；

③ repeat

④ ?i∈V，并行計(jì)算：

基于上述定義的自治計(jì)算系統(tǒng)，本文提出了基于博弈論的時(shí)序網(wǎng)絡(luò)預(yù)測(cè)算法，具體過(guò)程見(jiàn)算法1.從單個(gè)節(jié)點(diǎn)智能體的角度來(lái)看，步驟初始化節(jié)點(diǎn)智能體vi的三元組為其中表示初始靜態(tài)網(wǎng)絡(luò)g0中節(jié)點(diǎn)i的鄰居集.在每輪迭代中，步驟⑤～并行化地計(jì)算和步驟～計(jì)算相應(yīng)收益矩陣Θt和Φt的納什均衡點(diǎn)集；步驟生成下一周期靜態(tài)網(wǎng)絡(luò)的鏈路集合.當(dāng)系統(tǒng)時(shí)間達(dá)到預(yù)設(shè)的最大迭代次數(shù)I時(shí)，算法將會(huì)輸出一個(gè)預(yù)測(cè)的網(wǎng)絡(luò)演化序列

5 實(shí)驗(yàn)和結(jié)果

5.1 實(shí)驗(yàn)設(shè)置

我們選擇斯坦福網(wǎng)絡(luò)分析平臺(tái)SNAP中的4個(gè)時(shí)序網(wǎng)絡(luò)Math，Ask，Super，Stack，生成4個(gè)ε-鄰接網(wǎng)絡(luò)序列.具體來(lái)說(shuō)，對(duì)于每個(gè)時(shí)序網(wǎng)絡(luò)，我們使用第1年的數(shù)據(jù)元組構(gòu)建一個(gè)無(wú)向網(wǎng)絡(luò)，并抽取該網(wǎng)絡(luò)的最大連通子圖生成初始的靜態(tài)網(wǎng)絡(luò)g0(初始靜態(tài)網(wǎng)絡(luò)的統(tǒng)計(jì)特征見(jiàn)表1).接下來(lái)，我們進(jìn)一步將ε設(shè)置為2%，生成相應(yīng)的ε-鄰接網(wǎng)絡(luò)序列.圖1分別記錄了4個(gè)ε-鄰接網(wǎng)絡(luò)序列中相應(yīng)的|Et|，|Mt|，|Rt|包含的鏈路數(shù)量.可見(jiàn)，隨著時(shí)間周期t的增加，|Et|，|Mt|，|Rt|都呈顯著的下降趨勢(shì).后續(xù)實(shí)驗(yàn)中，我們將這4個(gè)ε-鄰接網(wǎng)絡(luò)序列作為真實(shí)的網(wǎng)絡(luò)演化序列，并將算法1分別應(yīng)用于表1的4個(gè)初始靜態(tài)網(wǎng)絡(luò).通過(guò)對(duì)比預(yù)測(cè)得到的網(wǎng)絡(luò)演化序列和真實(shí)網(wǎng)絡(luò)演化序列的相似度，來(lái)評(píng)價(jià)鏈路預(yù)測(cè)算法的優(yōu)劣.

我們選擇5種基于監(jiān)督學(xué)習(xí)的鏈路預(yù)測(cè)方法，包括Logistic回歸(logistic regression， LR)、SVM、決策樹(shù)(C4.5)、多層感知器神經(jīng)網(wǎng)絡(luò)(multi-layer perception neural network， MPNN)和樸素貝葉斯(na?ve Bayes， NB)作為對(duì)比算法.針對(duì)每個(gè)耦合的靜態(tài)網(wǎng)絡(luò)對(duì)，如(Et-1,Et)，然后將所有Mt中的鏈路標(biāo)記為正例，并從Et-1-Mt中隨機(jī)選擇相同數(shù)量的鏈路標(biāo)記為反例.這些鏈路實(shí)例的特征向量基于相應(yīng)靜態(tài)網(wǎng)絡(luò)Et-1計(jì)算生成.這樣，我們可以選擇一種分類(lèi)器在上述訓(xùn)練集上進(jìn)行訓(xùn)練，并將訓(xùn)練好的分類(lèi)器用于消失鏈路預(yù)測(cè).采取相同的思路，我們可以構(gòu)建另一個(gè)訓(xùn)練樣本進(jìn)行重連鏈路預(yù)測(cè)，其中節(jié)點(diǎn)對(duì)的特征向量基于相應(yīng)的投影網(wǎng)絡(luò)Pt-1(L)計(jì)算生成.此外，我們還選擇了3種基于概率模型的鏈路預(yù)測(cè)方法，包括Wang等人[33]提出的LPM模型、Coutant等人[34]提出的PRM-CU模型、Wang等人[35]提出的SDNE模型.

(13)

5.2 基于Cox比例風(fēng)險(xiǎn)模型的參數(shù)學(xué)習(xí)

采用相同的分析過(guò)程，我們可以分別對(duì)其他3個(gè)時(shí)序網(wǎng)絡(luò)進(jìn)行類(lèi)似的分析，其結(jié)果見(jiàn)表4.其中，每個(gè)數(shù)據(jù)集中，加粗字體的協(xié)變量系數(shù)表示該特征與對(duì)應(yīng)事件是正相關(guān)，正常字體的協(xié)變量系數(shù)表示該特征與對(duì)應(yīng)事件是負(fù)相關(guān)，而缺失協(xié)變量系數(shù)表示該特征與對(duì)應(yīng)事件不相關(guān).在所有數(shù)據(jù)集中，PA特征[17]與鏈路的消失和重連都是獨(dú)立的.經(jīng)典的BA網(wǎng)絡(luò)演化模型[40]假設(shè)一個(gè)新的節(jié)點(diǎn)同已知網(wǎng)絡(luò)中的節(jié)點(diǎn)i連接的概率同ki呈正比.而本文考慮的網(wǎng)絡(luò)演化序列是基于固定節(jié)點(diǎn)集V生成的，排除了新節(jié)點(diǎn)加入對(duì)網(wǎng)絡(luò)演化的影響.在這種情境下，傳統(tǒng)的基于BA模型的無(wú)標(biāo)度網(wǎng)絡(luò)生成模型可能并不適用.

Table 2 Results of Survival Analysis on HM Dataset of theTemporal Network Math表2 基于Math時(shí)序網(wǎng)絡(luò)HM數(shù)據(jù)集的生存分析結(jié)果

Notes: Bold values represent a positive correlation between the feature and link missing event, while the regular ones represent a negative correlation. Sig. means significance.

Table 3 Results of Survival Analysis on HR Dataset of theTemporal Network Math表3 基于Math時(shí)序網(wǎng)絡(luò)HR數(shù)據(jù)集的生存分析結(jié)果

Notes: Bold values represent a positive correlation between the feature and link reconnection event, while the regular ones represent a negative correlation. Sig. means significance.

Table 4 Learning Results of the Covariate Coefficients Based on the Cox Proportional Hazards Model表4 Cox比例風(fēng)險(xiǎn)模型協(xié)變量系數(shù)學(xué)習(xí)結(jié)果

Notes: Bold values represent a positive correlation between the feature and link missing/reconnection event, the regular ones represent a negative correlation, while the missing values represent that the features are independent from the related events.

Fig. 2 The F1-score matrices between the predicted network evolution sequence and the ground-truth one圖2 真實(shí)網(wǎng)絡(luò)演化序列同預(yù)測(cè)網(wǎng)絡(luò)演化序列的F1-score矩陣

5.3 時(shí)序網(wǎng)絡(luò)鏈路預(yù)測(cè)結(jié)果

接下來(lái)，我們將算法1同其他鏈路預(yù)測(cè)方法進(jìn)行性能對(duì)比.從圖3中可觀察到，本文所提方法明顯優(yōu)于對(duì)比算法.其中，MPNN只在Stack網(wǎng)絡(luò)上有較好的表現(xiàn)，但無(wú)法準(zhǔn)確預(yù)測(cè)其他3個(gè)網(wǎng)絡(luò)的演化序列.多數(shù)基于監(jiān)督式學(xué)習(xí)的鏈路預(yù)測(cè)方法對(duì)訓(xùn)練樣本很敏感，受分類(lèi)樣本失衡問(wèn)題的影響，這些方法盡管在消失鏈路預(yù)測(cè)上可以取得不錯(cuò)效果，但難以準(zhǔn)確地預(yù)測(cè)重連鏈路.本文方法采用動(dòng)態(tài)博弈的雙向選擇機(jī)制，可以篩選出最可能消失的鏈路和最可能重連的節(jié)點(diǎn)對(duì).這種相對(duì)保守的預(yù)測(cè)方法盡管在召回率方面有所犧牲，但可以獲得更高的準(zhǔn)確率.因此，在AvgF1指標(biāo)上，本文方法要明顯優(yōu)于基于有監(jiān)督學(xué)習(xí)的鏈路預(yù)測(cè)方法.與基于概率模型的鏈路預(yù)測(cè)方法相比，本文方法在Super網(wǎng)絡(luò)上的預(yù)測(cè)性能稍遜于SDNE；而在其他網(wǎng)絡(luò)上，算法1得到的網(wǎng)絡(luò)演化序列能更好地模擬真實(shí)網(wǎng)絡(luò)的演化過(guò)程.

Fig. 3 Accuracy comparison of the network evolution sequences obtained by different link prediction algorithms圖3 不同算法對(duì)網(wǎng)絡(luò)演化序列的預(yù)測(cè)準(zhǔn)確性比較

最后，我們對(duì)比了不同鏈路預(yù)測(cè)算法在100次連續(xù)預(yù)測(cè)過(guò)程中的執(zhí)行效率，從圖4可以看出，不論在小規(guī)模的Math數(shù)據(jù)集上，還是在大規(guī)模的Stack數(shù)據(jù)集上，算法1的執(zhí)行效率都明顯優(yōu)于其他對(duì)比算法.由于本文采用了Cox比例風(fēng)險(xiǎn)模型對(duì)每個(gè)數(shù)據(jù)集中不相關(guān)的鏈路特征進(jìn)行了排序，因此在迭代預(yù)測(cè)過(guò)程中，每個(gè)節(jié)點(diǎn)對(duì)的特征向量更新耗時(shí)更少.在動(dòng)態(tài)博弈框架下，每個(gè)節(jié)點(diǎn)的特征向量更新和策略選擇是獨(dú)立的，故算法1可以很好地并行化.另外，我們發(fā)現(xiàn)本文所提方法的執(zhí)行效率比基于有監(jiān)督學(xué)習(xí)的鏈路預(yù)測(cè)算法提高了將近2倍，比基于概率模型的鏈路預(yù)測(cè)算法的執(zhí)行效率提高了將近10倍.

Fig. 4 Comparison of the total running time of differentlink prediction algorithms圖4 不同鏈路預(yù)測(cè)算法的執(zhí)行時(shí)間對(duì)比

6 總 結(jié)

本文提出了一種新穎的用于預(yù)測(cè)時(shí)序網(wǎng)絡(luò)的演化序列半監(jiān)督學(xué)習(xí)框架.為簡(jiǎn)化研究問(wèn)題，假設(shè)時(shí)序網(wǎng)絡(luò)的演化是在一組固定節(jié)點(diǎn)集中進(jìn)行的，此時(shí)網(wǎng)絡(luò)的演化預(yù)測(cè)問(wèn)題轉(zhuǎn)換為：如何根據(jù)歷史的網(wǎng)絡(luò)演化序列預(yù)測(cè)下一時(shí)刻靜態(tài)網(wǎng)絡(luò)的消失鏈路集和重連鏈路集.為解決此問(wèn)題，首先為每條鏈路定義一組基于鄰居相似度的特征向量，利用Cox比例風(fēng)險(xiǎn)模型學(xué)習(xí)對(duì)應(yīng)鏈路消失和重連事件的特征向量權(quán)重.為壓縮網(wǎng)絡(luò)演化預(yù)測(cè)的搜索空間，提出了一種基于動(dòng)態(tài)博弈的雙向選擇機(jī)制來(lái)預(yù)測(cè)未來(lái)的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu).在理論研究基礎(chǔ)上，提出了一種基于多智能體自治計(jì)算的鏈路預(yù)測(cè)算法，并在真實(shí)時(shí)序網(wǎng)絡(luò)數(shù)據(jù)集上驗(yàn)證了方法的有效性和高效性.未來(lái)將關(guān)注于如何將網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)信息融入預(yù)測(cè)模型，進(jìn)而提高預(yù)測(cè)算法的準(zhǔn)確性.