融合多元影響力節(jié)點(diǎn)識(shí)別指標(biāo)MPR的鏈接預(yù)測(cè)

伍杰華,熊云艷,張 頂,陳嘉志

(1.廣東工貿(mào)職業(yè)技術(shù)學(xué)院 計(jì)算機(jī)與信息工程學(xué)院,廣州 510510; 2.華南理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院,廣州 510641)

0 概述

在現(xiàn)實(shí)生活中,各類實(shí)體之間的復(fù)雜關(guān)系均可表示為網(wǎng)絡(luò)結(jié)構(gòu),而節(jié)點(diǎn)之間的鏈接是該結(jié)構(gòu)的基礎(chǔ)和核心組成部分[1]。因此,對(duì)鏈接形成規(guī)律進(jìn)行挖掘和分析具有重大意義,鏈接預(yù)測(cè)是其中一個(gè)重要的研究方向[2]。

鏈接預(yù)測(cè)技術(shù)基于已觀察到的復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)屬性預(yù)測(cè)節(jié)點(diǎn)之間是否存在鏈接[3],或者通過挖掘網(wǎng)絡(luò)的歷史結(jié)構(gòu)信息預(yù)測(cè)節(jié)點(diǎn)之間未來發(fā)生鏈接的可能性[4]。該技術(shù)能夠幫助研究人員分析知識(shí)圖譜實(shí)體之間的關(guān)聯(lián)[5],理解科研合作者之間的合作關(guān)系變化,剖析生物蛋白質(zhì)功能網(wǎng)絡(luò)中蛋白質(zhì)之間的隱含功能關(guān)系[6]等。此外,該技術(shù)還能夠從理論層面幫助研究者劃分社交網(wǎng)絡(luò)圈,把握用戶影響的演化規(guī)律[7],為網(wǎng)絡(luò)表示學(xué)習(xí)提供評(píng)估指標(biāo)[8]。隨著網(wǎng)絡(luò)復(fù)雜性的提高和規(guī)模的擴(kuò)大,鏈接預(yù)測(cè)的研究熱點(diǎn)從同質(zhì)網(wǎng)絡(luò)轉(zhuǎn)移到異質(zhì)多元網(wǎng)絡(luò)。本文結(jié)合影響節(jié)點(diǎn)識(shí)別技術(shù),提出一種適用于多元復(fù)雜網(wǎng)絡(luò)的鏈接預(yù)測(cè)算法。

1 相關(guān)工作

鏈接預(yù)測(cè)算法一般分為基于網(wǎng)絡(luò)結(jié)構(gòu)相似度的學(xué)習(xí)與預(yù)測(cè)和基于網(wǎng)絡(luò)特征的學(xué)習(xí)與預(yù)測(cè)2類[3]?；诰W(wǎng)絡(luò)特征的學(xué)習(xí)與預(yù)測(cè)算法的相關(guān)工作可參考文獻(xiàn)[3-4],此處不再敘述。對(duì)于基于網(wǎng)絡(luò)結(jié)構(gòu)相似度的學(xué)習(xí)與預(yù)測(cè)算法,其基本思想是結(jié)合統(tǒng)計(jì)學(xué)、社會(huì)學(xué)、圖論和拓?fù)鋵W(xué)等領(lǐng)域的概念,挖掘網(wǎng)絡(luò)的結(jié)構(gòu)信息,計(jì)算2個(gè)潛在節(jié)點(diǎn)對(duì)之間的鏈接概率(相似度得分)。一般來講,2個(gè)潛在節(jié)點(diǎn)對(duì)的相似度越大,其產(chǎn)生鏈接的可能性越高。由于網(wǎng)絡(luò)的結(jié)構(gòu)信息可以表示為不同的類型,因此鏈接預(yù)測(cè)算法可以分為基于鄰接節(jié)點(diǎn)相似度、基于共鄰節(jié)點(diǎn)相似度、基于路徑信息相似度、基于隨機(jī)游走相似度、基于社交結(jié)構(gòu)信息相似度等。同時(shí),由于網(wǎng)絡(luò)結(jié)構(gòu)信息的表示方式有無限可能,因此目前仍有許多工作圍繞如何挖掘網(wǎng)絡(luò)的結(jié)構(gòu)信息展開。

隨著網(wǎng)絡(luò)結(jié)構(gòu)的不斷變化,其節(jié)點(diǎn)也變得更加復(fù)雜,出現(xiàn)了鏈接屬于不同類型或者存在多元關(guān)系的網(wǎng)絡(luò),稱為多元(多維度、多維)網(wǎng)絡(luò)[9],每一個(gè)維度的網(wǎng)絡(luò)稱為子網(wǎng)絡(luò)。以實(shí)驗(yàn)數(shù)據(jù)集Student為例[10],該數(shù)據(jù)集利用本-古里安大學(xué)的必修課程“計(jì)算機(jī)與網(wǎng)絡(luò)安全”收集的數(shù)據(jù),構(gòu)建多元社交網(wǎng)絡(luò)。該網(wǎng)絡(luò)包含以下3個(gè)維度的關(guān)系:

1)Partner鏈接關(guān)系,定義為學(xué)生作為合作伙伴一起完成理論或編碼的作業(yè)任務(wù)。

2)Computer鏈接關(guān)系,定義為2名學(xué)生使用同一臺(tái)電腦完成在線作業(yè)。

3)Time鏈接關(guān)系,其為學(xué)生之間的第2個(gè)隱式連接,定義為學(xué)生通過不同的計(jì)算機(jī)共同提交解決方案。

上述3個(gè)維度的關(guān)系不僅在邏輯上存在關(guān)聯(lián),在顯式結(jié)構(gòu)上也有關(guān)系,因此,在多元網(wǎng)絡(luò)中,傳統(tǒng)的基于單一維度網(wǎng)絡(luò)(或稱同構(gòu)網(wǎng)絡(luò))的相似度算法并不能反映這種多元屬性。圖1展示了Student數(shù)據(jù)集中的2個(gè)維度(A,B)的局部網(wǎng)絡(luò)結(jié)構(gòu),其中,虛線表示不同維度之間節(jié)點(diǎn)的鏈接關(guān)系,實(shí)線表示單一維度子網(wǎng)絡(luò)內(nèi)部的鏈接關(guān)系?？梢钥闯?一個(gè)維度節(jié)點(diǎn)(A子網(wǎng)絡(luò)的實(shí)心節(jié)點(diǎn))的屬性不僅受其所處維度子網(wǎng)絡(luò)中其他節(jié)點(diǎn)(A子網(wǎng)絡(luò)的空心節(jié)點(diǎn))的影響,也受其他維度子網(wǎng)絡(luò)節(jié)點(diǎn)(B子網(wǎng)絡(luò)的實(shí)心節(jié)點(diǎn))的影響。因此,在設(shè)計(jì)相似度鏈接預(yù)測(cè)算法時(shí),應(yīng)該把多元屬性考慮進(jìn)去。同時(shí),由于鏈接的2個(gè)相同節(jié)點(diǎn)之間的多樣化關(guān)系會(huì)產(chǎn)生多個(gè)互相影響的子網(wǎng)絡(luò),即一個(gè)子網(wǎng)絡(luò)的拓?fù)鋵傩宰兓ǔ?huì)影響其他網(wǎng)絡(luò)的屬性變化,因此一種類型的子網(wǎng)絡(luò)可以成為另一類型子網(wǎng)絡(luò)關(guān)系變化的約束或推動(dòng)力量[11]。圖2和圖3給出Querylog數(shù)據(jù)集的度和聚類系數(shù)分布關(guān)系,可以看出,不同子網(wǎng)絡(luò)的結(jié)構(gòu)存在相似性,可以充分利用多元屬性各維度的相似性結(jié)構(gòu)設(shè)計(jì)預(yù)測(cè)指標(biāo),這在單一同構(gòu)網(wǎng)絡(luò)中是無法實(shí)現(xiàn)的。

圖1 多元網(wǎng)絡(luò)局部結(jié)構(gòu)示意圖Fig.1 Schematic diagram of local structure inmultiplex network

圖2 Querylog數(shù)據(jù)集的度分布Fig.2 Degree distribution of Querylog dataset

圖3 Querylog數(shù)據(jù)集的聚類系數(shù)分布Fig.3 Clustering coefficient distribution of Querylog dataset

多元鏈接預(yù)測(cè)算法主要通過對(duì)維度之間的關(guān)聯(lián)關(guān)系進(jìn)行建模實(shí)現(xiàn)。文獻(xiàn)[12]通過引入多元網(wǎng)絡(luò)維度之間的相關(guān)性構(gòu)建度相關(guān)、邊相關(guān)等屬性,拓展了CN、AA、RA等傳統(tǒng)的相似度度量,設(shè)計(jì)了一系列新的預(yù)測(cè)指標(biāo)。文獻(xiàn)[13]定義了影響力傳播和時(shí)序信息2種多維度特性,并由此構(gòu)造出多維度鏈接預(yù)測(cè)指標(biāo)MRIP(Multi-Relational Influence Propagation)和MRT(Multi-Relational Temporal Link Prediction)。文獻(xiàn)[14]采用隱含空間網(wǎng)絡(luò)模型提取子網(wǎng)絡(luò)的低維因子,通過似然比來檢驗(yàn)因子的相關(guān)性,并建立了一個(gè)冷啟動(dòng)的多維網(wǎng)絡(luò)鏈接預(yù)測(cè)模型。但是,由于異構(gòu)網(wǎng)絡(luò)節(jié)點(diǎn)和鏈接的類型較為復(fù)雜,直接采用相似度計(jì)算方式進(jìn)行鏈接預(yù)測(cè)比較困難。文獻(xiàn)[15]模型雖然基于局部指標(biāo)提供了快速的解決方案并取得了可接受的結(jié)果,但它并沒有在多元網(wǎng)絡(luò)全局視角下確定不同共同鄰居各自的貢獻(xiàn)度。此外,該模型利用路徑和隨機(jī)游走指標(biāo),根據(jù)節(jié)點(diǎn)之間較長(zhǎng)的鏈接屬性進(jìn)行預(yù)測(cè),其優(yōu)點(diǎn)在于可從網(wǎng)絡(luò)的準(zhǔn)局部/全局視角構(gòu)建,缺點(diǎn)是可能會(huì)忽略共同鄰居的局部結(jié)構(gòu)。一些基于鄰接矩陣的全局指標(biāo)能夠充分利用網(wǎng)絡(luò)全局屬性,但是此類算法運(yùn)行速度慢,難以平衡預(yù)測(cè)性能和計(jì)算效率。

影響節(jié)點(diǎn)識(shí)別(Influential Node Identification,INI)[16]是網(wǎng)絡(luò)分析的一個(gè)重要方向。本文針對(duì)多元網(wǎng)絡(luò)鏈接預(yù)測(cè)任務(wù),提出一種基于多元PageRank(Multiplex PageRank,MPR)[17]的鏈接預(yù)測(cè)算法。該算法給出MPR指標(biāo)詳細(xì)的定義和計(jì)算方法,通過MPR為每個(gè)節(jié)點(diǎn)定義一個(gè)多元排名函數(shù)并分配一個(gè)評(píng)分來量化節(jié)點(diǎn)的重要性,然后把該全局得分集成到微觀層面的基于共鄰節(jié)點(diǎn)的相似框架中,從而得到預(yù)測(cè)結(jié)果。

2 問題描述

2.1 問題定義

給定一個(gè)多元網(wǎng)絡(luò)G=(V,E)。其中,G={G1,G2,…,GL}表示該多元網(wǎng)絡(luò)共有L個(gè)維度的子網(wǎng)絡(luò),稱為L(zhǎng)個(gè)層,V定義為節(jié)點(diǎn)集合,|V|=N,E={E1,E2,…,EL}表示每個(gè)維度子網(wǎng)絡(luò)的鏈接集合。第個(gè)維度的子網(wǎng)絡(luò)定義為G=(V,E),=1,2,…,L。同時(shí),G的鄰接矩陣可定義為A,其中每一項(xiàng)或者分別表示在該子網(wǎng)絡(luò)中的鏈接是否存在。

2.2 預(yù)測(cè)過程

鏈接預(yù)測(cè)算法首先隨機(jī)選取其中一個(gè)層次的子網(wǎng)絡(luò)G,按照比例r把其劃分為訓(xùn)練網(wǎng)絡(luò)和預(yù)測(cè)網(wǎng)絡(luò)其中,且然后,結(jié)合其他層次子網(wǎng)絡(luò)的關(guān)聯(lián)影響以及所處子網(wǎng)絡(luò)的結(jié)構(gòu)屬性,對(duì)中所有潛在節(jié)點(diǎn)對(duì)計(jì)算相似度得分,實(shí)現(xiàn)如下映射:

3 基于PageRank的鏈接預(yù)測(cè)算法

3.1 PageRank算法

PageRank[18]算法由Google的兩位創(chuàng)始人于1998年4月舉行的第七屆國(guó)際萬維網(wǎng)會(huì)議上提出。該算法的初始目的是對(duì)網(wǎng)站進(jìn)行排名,通過計(jì)算頁(yè)面鏈接的數(shù)量和質(zhì)量粗略估計(jì)和確定網(wǎng)站的重要性,并把相關(guān)排序結(jié)果應(yīng)用在Google的搜索引擎中。隨著研究的不斷深入,PageRank算法及其變體已被廣泛應(yīng)用于挖掘具備互聯(lián)結(jié)構(gòu)的信息網(wǎng)絡(luò)的重要性節(jié)點(diǎn)[16]。

給定一個(gè)節(jié)點(diǎn)i,該節(jié)點(diǎn)的得分xi可表示為如下形式:

(1)

其中,N(j)表示節(jié)點(diǎn)j的鄰接節(jié)點(diǎn)集合,αA是一個(gè)阻尼因子,即一個(gè)隨機(jī)游走節(jié)點(diǎn)j跳到其任意一個(gè)鄰居節(jié)點(diǎn)的概率是αA,而其隨機(jī)均勻選擇跳躍到其他任意節(jié)點(diǎn)的概率為1-αA。因此,PageRank可以理解為具有額外隨機(jī)跳躍能力的靜止分布。

3.2 基于PageRank的鏈接預(yù)測(cè)指標(biāo)

網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)對(duì)基于相似度的鏈接預(yù)測(cè)方法至關(guān)重要。局部的、準(zhǔn)局部/全局的和全局的鏈接預(yù)測(cè)算法的目的,是為每個(gè)相關(guān)的鄰接節(jié)點(diǎn)賦予一個(gè)量化的區(qū)別性的影響力(貢獻(xiàn))。例如,經(jīng)典的RA指標(biāo)使用1/|N(ω)|確定共鄰節(jié)點(diǎn)ω的不同影響力。其中,1/|N(ω)|表示如果鄰接節(jié)點(diǎn)度較大,那么其對(duì)鏈接生成的影響力較小。在微博社交網(wǎng)絡(luò)中,共同朋友的影響力大小在用戶關(guān)系預(yù)測(cè)問題上具有重要的作用,度越大的節(jié)點(diǎn)表示影響力越大的用戶(權(quán)威用戶)[16]。假設(shè)存在2對(duì)尚未存在關(guān)系的用戶有相同數(shù)目的共同朋友,其中一對(duì)用戶的共同朋友權(quán)威用戶多,另一對(duì)用戶的共同朋友權(quán)威用戶少。實(shí)驗(yàn)結(jié)果表明,后一對(duì)朋友產(chǎn)生關(guān)系的可能性要比前一對(duì)高,即共同朋友影響力大小對(duì)關(guān)系的產(chǎn)生起反作用。根據(jù)上述討論,任意2個(gè)節(jié)點(diǎn)u和v,其基于PageRank的相似度得分PR(u,v)計(jì)算過程如下:

(2)

式(2)的核心思想是一個(gè)共鄰節(jié)點(diǎn)的影響力越大,潛在預(yù)測(cè)節(jié)點(diǎn)對(duì)提供的貢獻(xiàn)就越小,即兩者成反比關(guān)系。雖然現(xiàn)有的研究把一些重要性節(jié)點(diǎn)發(fā)現(xiàn)指標(biāo)引入鏈接預(yù)測(cè)問題中[2],但其基本思想是不同的。本文將影響力放在分母上,可更直觀地表示上述反比關(guān)系。節(jié)點(diǎn)影響力排名得分的優(yōu)勢(shì)主要體現(xiàn)在以下2個(gè)方面:

1)判別性。影響力節(jié)點(diǎn)識(shí)別方法已成功應(yīng)用于各種基于信息網(wǎng)絡(luò)結(jié)構(gòu)的實(shí)際分析任務(wù),如控制疾病和謠言動(dòng)態(tài)、跟蹤意見傳輸和促進(jìn)信息傳播等,其可以有效地衡量一個(gè)共同鄰居如何影響潛在節(jié)點(diǎn)。

2)全局性。許多重要性節(jié)點(diǎn)發(fā)現(xiàn)指標(biāo)均考慮了路徑或擴(kuò)散信息的影響,同時(shí)對(duì)網(wǎng)絡(luò)中節(jié)點(diǎn)的擴(kuò)展能力進(jìn)行排序,從而更準(zhǔn)確快速地捕捉共同鄰居的整體貢獻(xiàn)。

4 基于MPR的鏈接預(yù)測(cè)方案

由于基于PageRank的鏈接預(yù)測(cè)算法僅針對(duì)單一維度的同構(gòu)網(wǎng)絡(luò),因此當(dāng)其應(yīng)用于多元網(wǎng)絡(luò)的鏈接預(yù)測(cè)場(chǎng)景時(shí),也僅考慮其中一個(gè)維度的子網(wǎng)絡(luò)。根據(jù)前文所述,當(dāng)同一對(duì)節(jié)點(diǎn)可以通過鏈接連接不同維度的子網(wǎng)絡(luò)時(shí),擴(kuò)展PageRank以捕獲一個(gè)層中節(jié)點(diǎn)的排名,可以影響并受其他層中相同節(jié)點(diǎn)的排名影響的程度,即定義一個(gè)考慮網(wǎng)絡(luò)多元關(guān)系的節(jié)點(diǎn)影響力鑒定指標(biāo)MPR[19]。

為了將PageRank影響力節(jié)點(diǎn)度量擴(kuò)展到多元網(wǎng)絡(luò),本文假設(shè)節(jié)點(diǎn)在一個(gè)維度的子網(wǎng)絡(luò)中具有的中心性影響節(jié)點(diǎn)在另一維度中也具備中心性。各維度子網(wǎng)絡(luò)之間的這種相互作用具有雙重性質(zhì)[19]。首先,一個(gè)子網(wǎng)絡(luò)中節(jié)點(diǎn)的重要性可能會(huì)增加該節(jié)點(diǎn)在另一子網(wǎng)絡(luò)中的重要性。其次,節(jié)點(diǎn)在一個(gè)子網(wǎng)絡(luò)中的重要性能夠放大節(jié)點(diǎn)的能力,并從另一子網(wǎng)絡(luò)中指向它的節(jié)點(diǎn)的重要性中獲益。例如,在YouTube社交網(wǎng)絡(luò)中,網(wǎng)絡(luò)數(shù)據(jù)集包含朋友、訂閱和視頻3個(gè)子維度的網(wǎng)絡(luò)。如果2個(gè)用戶在朋友子網(wǎng)絡(luò)中是朋友,他們很有可能在訂閱子網(wǎng)絡(luò)中也存在訂閱關(guān)系,即如果一個(gè)用戶在朋友子網(wǎng)絡(luò)中是中心節(jié)點(diǎn),其影響力大,則該用戶在訂閱子網(wǎng)絡(luò)中也有可能是核心傳播用戶。因此,如何充分挖掘不同子網(wǎng)絡(luò)之間的隱含關(guān)聯(lián),并定義多元PageRank得分是設(shè)計(jì)多元網(wǎng)絡(luò)鏈接預(yù)測(cè)算法的核心。

針對(duì)上述問題,本文基于一個(gè)子網(wǎng)絡(luò)中節(jié)點(diǎn)的中心性可能受到另一個(gè)子網(wǎng)絡(luò)中同一節(jié)點(diǎn)的中心性的影響這一特點(diǎn),提出一種融合多元影響力節(jié)點(diǎn)指標(biāo)的鏈接預(yù)測(cè)算法。為簡(jiǎn)便起見,本文首先將多元網(wǎng)絡(luò)分為子網(wǎng)絡(luò)A和子網(wǎng)絡(luò)B。定義Aij和Bij分別是子網(wǎng)絡(luò)A和子網(wǎng)絡(luò)B的鄰接矩陣,并通過式(1)計(jì)算子網(wǎng)絡(luò)A所有節(jié)點(diǎn)在參數(shù)αA>0時(shí)的PageRank值pr={x1,x2,…,xN}。然后根據(jù)該值將多元PageRank中心性[20],即X={X1,X2,…,XN}賦值給子網(wǎng)絡(luò)B的各節(jié)點(diǎn)。因此,節(jié)點(diǎn)i的MPR得分如下:

(3)

1)式(3)的第1部分表示節(jié)點(diǎn)i的中心性貢獻(xiàn),它來自子網(wǎng)絡(luò)B中指向節(jié)點(diǎn)i的節(jié)點(diǎn)的中心性。與單維度PageRank度量相同,該貢獻(xiàn)與節(jié)點(diǎn)i的鄰居出入度成反比。不同于PageRank,式(3)使得該貢獻(xiàn)得分受到子網(wǎng)絡(luò)B中的節(jié)點(diǎn)i及其鄰居在子網(wǎng)絡(luò)A中的中心性影響。兩個(gè)網(wǎng)絡(luò)之間的相互作用對(duì)節(jié)點(diǎn)的中心性具有雙重影響。首先,隨著子網(wǎng)絡(luò)A中節(jié)點(diǎn)i的中心性變大,其可以從子網(wǎng)絡(luò)B中鄰居的中心性獲得某些優(yōu)勢(shì),并使其自身的中心性變大。其在一個(gè)子網(wǎng)絡(luò)中中心性越大,節(jié)點(diǎn)就越有可能吸引另一子網(wǎng)絡(luò)中的其他重要節(jié)點(diǎn),提高相似性得分。其次,每個(gè)鄰接節(jié)點(diǎn)j對(duì)子網(wǎng)絡(luò)B中節(jié)點(diǎn)i的中心性貢獻(xiàn),通過將節(jié)點(diǎn)j的中心性除以子網(wǎng)絡(luò)B中節(jié)點(diǎn)j的鄰居在子網(wǎng)絡(luò)A中的中心性總和得到。換句話說,節(jié)點(diǎn)i的相似度得分來源于子網(wǎng)絡(luò)B中任何鄰接節(jié)點(diǎn)j的中心性,且該中心性被稀釋到與子網(wǎng)絡(luò)A中的高中心性相關(guān)聯(lián)的許多其他節(jié)點(diǎn)中。綜上所述,一個(gè)子網(wǎng)絡(luò)中的重要節(jié)點(diǎn)可以吸引不同子網(wǎng)絡(luò)中的重要節(jié)點(diǎn),但是如果存在許多具有相似吸引能力的其他節(jié)點(diǎn),則會(huì)削弱其優(yōu)勢(shì)。

2)式(3)中的第2部分反映了子網(wǎng)絡(luò)B中節(jié)點(diǎn)i的中心性貢獻(xiàn),它來源于子網(wǎng)絡(luò)A中節(jié)點(diǎn)i的中心性。這一部分內(nèi)容可以使那些不能吸引子網(wǎng)絡(luò)B中重要鄰接節(jié)點(diǎn)的節(jié)點(diǎn)通過在子網(wǎng)絡(luò)A中的重要性獲得優(yōu)勢(shì)。在極端情況下,如果節(jié)點(diǎn)在子網(wǎng)絡(luò)A中具有非零中心性,則子網(wǎng)絡(luò)B中具有零度數(shù)的節(jié)點(diǎn)仍然可以與非零中心性值相關(guān)聯(lián)。該中心性組成部分的假設(shè)是不管節(jié)點(diǎn)吸引前一子網(wǎng)絡(luò)中其他重要節(jié)點(diǎn)的能力如何,其重要性受到同一節(jié)點(diǎn)在另一子網(wǎng)絡(luò)中的重要性的正面影響。

根據(jù)式(3)中的參數(shù)變化,本文給出以下2個(gè)極限情況下的MPR指標(biāo):

1)MPR(β=1,γ=0)

(4)

2)MPR(β=1,γ=1)

(5)

(6)

(7)

通過上述步驟可獲得每一個(gè)節(jié)點(diǎn)在各個(gè)維度子網(wǎng)絡(luò)中的多元影響力得分。對(duì)于第維度子網(wǎng)絡(luò)中的任意2個(gè)節(jié)點(diǎn)u和v,其基于MPR的相似度得分如下:

(8)

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

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

根據(jù)第2節(jié)的問題定義,本文把比例r設(shè)置為90%,然后對(duì)Gα進(jìn)行10次劃分并取平均值。本文選用Precision作為評(píng)價(jià)度量。Precision表示如果給定候選的預(yù)測(cè)鏈接數(shù)目為N,且在其預(yù)測(cè)結(jié)果中有M個(gè)正確或者存在(即M條邊屬于集合E),則Precision=M/N。該指標(biāo)主要側(cè)重于衡量相似度排序前N個(gè)結(jié)果的命中比率。在實(shí)驗(yàn)中,Precision有時(shí)稱為Prec或者Prec@N。

5.2 數(shù)據(jù)集

本文實(shí)驗(yàn)采用以下2個(gè)數(shù)據(jù)集:

1)Student數(shù)據(jù)集[10]。利用本-古里安大學(xué)的計(jì)算機(jī)與網(wǎng)絡(luò)安全課程收集的數(shù)據(jù),構(gòu)建學(xué)生合作社交網(wǎng)絡(luò)。這個(gè)社交網(wǎng)絡(luò)包含來自2個(gè)部門的185名學(xué)生的數(shù)據(jù)。課程的社交網(wǎng)絡(luò)通過分析學(xué)生在做家庭作業(yè)時(shí)的內(nèi)隱合作關(guān)系和外顯合作關(guān)系而建立。學(xué)生合作圖包含185個(gè)節(jié)點(diǎn)、360個(gè)鏈接和3種鏈接類型。

2)QueryLog數(shù)據(jù)集[21]。這是一個(gè)共同查詢的網(wǎng)絡(luò),其節(jié)點(diǎn)表示查詢術(shù)語(字段),如果2個(gè)節(jié)點(diǎn)在同一查詢中同時(shí)使用,則它們之間存在鏈接。該數(shù)據(jù)集共有6個(gè)維度,每個(gè)維度表示用戶從查詢結(jié)果中單擊的排名,具體關(guān)系如下:排名(維度)1 → 1,排名2～3 → 2,排名4～6 → 3,排名7～10 → 4,排名11～58 → 5,排名59～500 → 6。為了簡(jiǎn)化操作,本文實(shí)驗(yàn)取前3個(gè)維度開展。

上述2個(gè)數(shù)據(jù)集的具體信息如表1所示。

表1 多元網(wǎng)絡(luò)結(jié)構(gòu)屬性Table 1 Structure attributes of multiplex network

5.3 對(duì)比方法

實(shí)驗(yàn)采用基于以下3類指標(biāo)的鏈接預(yù)測(cè)算法與本文基于2種MPR指標(biāo)的算法進(jìn)行對(duì)比:

1)單維度局部或者半全局指標(biāo),主要包括基于聚類系數(shù)的預(yù)測(cè)算法Cluster Coefficient Link Prediction(CC)[22]、基于共鄰節(jié)點(diǎn)影響的樸素貝葉斯鏈接預(yù)測(cè)算法Local Na?ve Bayes based on Common Neighbors(LNBCN)[23]和基于局部隨機(jī)游走的預(yù)測(cè)算法Local Random Walk(LRW)[24]。

2)多源局部指標(biāo)[12],主要包括基于邊維度鏈接度的預(yù)測(cè)算法Edge Dimension Connectivity(EDC)和基于平均度關(guān)聯(lián)的預(yù)測(cè)算法Average Node Correlation(ANC)。

3)影響力節(jié)點(diǎn)指標(biāo),本文選用單維度的節(jié)點(diǎn)影響力算法PageRank(PR)進(jìn)行對(duì)比。

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

表2給出在不同訓(xùn)練集規(guī)模下(r=0.7、0.8、0.9),各種算法在2個(gè)真實(shí)多元數(shù)據(jù)集中的預(yù)測(cè)效果,最優(yōu)結(jié)果加粗表示?？梢钥闯?最優(yōu)結(jié)果基本都出現(xiàn)在MPR算法中。例如,在r=0.9時(shí),與CC、LNBCN、EDC和ANC算法相比,MPR算法在Student數(shù)據(jù)集上的Precision值分別提高106.592%、69.033%、69.033%和69.033%,在QueryLog數(shù)據(jù)集上分別提高17.965%、16.758%、13.978%和14.329%。上述結(jié)果表明,MPR算法對(duì)于多元網(wǎng)絡(luò)鏈接預(yù)測(cè)的效果更好。同時(shí),在該規(guī)模訓(xùn)練集下,MPR算法在兩個(gè)數(shù)據(jù)集上的Precision值比PR算法分別提高37.728%和16.575%,表明本文算法充分考慮了多個(gè)維度子網(wǎng)絡(luò)之間的關(guān)聯(lián),能夠有效地把單維度的PR拓展到多元網(wǎng)絡(luò)的應(yīng)用場(chǎng)景。同時(shí),從表2可以看出,部分指標(biāo)(尤其是LRW算法)在Student數(shù)據(jù)集上沒有效果,部分算法(例如EDC和ANC)效果一致。這是因?yàn)樵摂?shù)據(jù)集過于稀疏,共鄰節(jié)點(diǎn)過少,節(jié)點(diǎn)之間的鏈接不能實(shí)現(xiàn)隨機(jī)游走和形成局部三角形結(jié)構(gòu)。例如,在Student的各個(gè)維度中,平均有95%以上的節(jié)點(diǎn)對(duì)沒有共鄰節(jié)點(diǎn),因此,LRW算法、EDC算法和ANC算法的預(yù)測(cè)效果不理想。然而,MPR算法能保持最優(yōu)性能,表明該算法具備在網(wǎng)絡(luò)非常稀疏的情況下進(jìn)行預(yù)測(cè)的能力。隨著訓(xùn)練集規(guī)模不斷下降,各種算法的預(yù)測(cè)效果逐漸提高,這是因?yàn)楹蜻x的集合變少,使得精確度的判斷更加容易。值得注意的是,在不同的訓(xùn)練集規(guī)模下,MPR算法均取得最優(yōu)結(jié)果,進(jìn)一步證明了該算法的穩(wěn)定性和魯棒性。

表2 在多元網(wǎng)絡(luò)3個(gè)維度下的預(yù)測(cè)性能Table 2 Prediction performance in three dimensions of the multivariate network

5.5 結(jié)果分析

Precision指標(biāo)是對(duì)潛在預(yù)測(cè)節(jié)點(diǎn)對(duì)的相似度評(píng)分,然后進(jìn)行排序并取前TopN個(gè)潛在節(jié)點(diǎn)對(duì),判斷鏈接是否存在并考慮命中率。在本文實(shí)驗(yàn)中,取不同的N值,輸出結(jié)果也會(huì)存在區(qū)別。需要注意的是,由于對(duì)比算法太多,圖4僅給出QueryLog數(shù)據(jù)集上每一類算法的最優(yōu)指標(biāo)。同時(shí),由于Student數(shù)據(jù)集上的預(yù)測(cè)效果差別較大,且部分指標(biāo)沒有Precision值,曲線圖不清晰,因此通過表3給出不同N值下的預(yù)測(cè)效果。從圖4和表3可以看出,TopN值越大,對(duì)應(yīng)的預(yù)測(cè)準(zhǔn)確率越高。由圖4可知,MPR算法的準(zhǔn)確率在每一個(gè)TopN步長(zhǎng)上幾乎都高于對(duì)比算法。由表3可知,無論TopN的值如何變化,最優(yōu)的結(jié)果基本都出現(xiàn)在MPR算法中。上述結(jié)果均表明,本文算法的整體性能優(yōu)于其他對(duì)比算法。此外,MPR算法在網(wǎng)絡(luò)結(jié)構(gòu)稀疏、缺乏共鄰節(jié)點(diǎn)結(jié)構(gòu)的情況下,其優(yōu)勢(shì)更明顯。例如,對(duì)于Student數(shù)據(jù)集的Time子網(wǎng)絡(luò),其聚類系數(shù)只有0.012 8,鏈接數(shù)目只有23,潛在節(jié)點(diǎn)對(duì)的共鄰節(jié)點(diǎn)非常少,且很多共鄰節(jié)點(diǎn)是孤立的。在這種情況下,不能發(fā)揮基于共鄰節(jié)點(diǎn)結(jié)構(gòu)指標(biāo)的優(yōu)勢(shì),因此對(duì)應(yīng)算法的預(yù)測(cè)準(zhǔn)確率不理想,而MPR算法的預(yù)測(cè)性能是對(duì)比算法的近10倍,原因在于MPR算法把共鄰節(jié)點(diǎn)的貢獻(xiàn)定義為該節(jié)點(diǎn)在整個(gè)網(wǎng)絡(luò)全局的排序得分,該得分不受制于網(wǎng)絡(luò)的稀疏性,因此可以獲得較優(yōu)的預(yù)測(cè)性能。

圖4 QueryLog數(shù)據(jù)集中各維度的Top N預(yù)測(cè)性能Fig.4 Top N prediction performance in each dimension on the QueryLog dataset

表3 Student數(shù)據(jù)集中各維度的Top N預(yù)測(cè)效果Table 3 Top N prediction performance in each dimension on the Student dataset

為揭示基于多元網(wǎng)絡(luò)的MPR算法和基于同構(gòu)網(wǎng)絡(luò)的PR算法的敏感性和特異性關(guān)系,同時(shí)驗(yàn)證MPR算法的優(yōu)越性,圖5給出MPR算法和PR算法在QueryLog數(shù)據(jù)集的3個(gè)維度子網(wǎng)絡(luò)上的接受者工作特性(Receiver Operating Characteristic Curve,ROC)曲線。ROC曲線以敏感性(真正率)為縱坐標(biāo)、特異性(假正率)為橫坐標(biāo),曲線下面積越大表明預(yù)測(cè)性能越好。由圖5可以看出,盡管2條曲線比較接近,但是MPR算法始終優(yōu)于PR算法,該結(jié)果表明,在多元網(wǎng)絡(luò)結(jié)構(gòu)下從PR算法拓展到MPR算法是合理的。

圖5 QueryLog數(shù)據(jù)集各維度的ROC曲線Fig.5 ROC curves in each dimension of QueryLog dataset

為驗(yàn)證本文算法的可擴(kuò)展性和穩(wěn)定性,對(duì)QueryLog數(shù)據(jù)集進(jìn)行不同規(guī)模的采樣,并輸出節(jié)點(diǎn)數(shù)目在2 500、3 000、3 500和4 000時(shí)不同算法的性能對(duì)比,如圖6所示。其中,Best-Baseline表示除MPR算法和PR算法外,效果最優(yōu)的對(duì)比算法。從圖6結(jié)果可以看出,在Bin2、Bin3子網(wǎng)絡(luò)的全部節(jié)點(diǎn)規(guī)模和Bin1子網(wǎng)絡(luò)的3 000、3 500節(jié)點(diǎn)規(guī)模下,MPR算法的預(yù)測(cè)結(jié)果最優(yōu)。上述結(jié)果表明,從整體上看,本文算法獨(dú)立于數(shù)據(jù)規(guī)模,即對(duì)數(shù)據(jù)規(guī)模的變化不敏感,是可擴(kuò)展的。同時(shí),隨著采樣規(guī)模的增大,各子網(wǎng)絡(luò)中MPR算法的性能表現(xiàn)比較穩(wěn)定,不是線性變化的,從而證明本文默認(rèn)節(jié)點(diǎn)規(guī)模2 000能夠反映算法的性能。

圖6 QueryLog數(shù)據(jù)集中不同采樣規(guī)模下的性能對(duì)比Fig.6 Performance comparison at different sampling sizes on the QueryLog dataset

6 結(jié)束語

多元網(wǎng)絡(luò)鏈接預(yù)測(cè)對(duì)于真實(shí)應(yīng)用場(chǎng)景下的知識(shí)圖譜關(guān)系推斷、社交網(wǎng)絡(luò)朋友推薦等具有重要的應(yīng)用價(jià)值。本文提出一種基于多元影響力節(jié)點(diǎn)識(shí)別指標(biāo)MPR的鏈接預(yù)測(cè)算法。給出多維度節(jié)點(diǎn)影響力排序指標(biāo)的定義和計(jì)算方法,通過該指標(biāo)為每個(gè)節(jié)點(diǎn)定義多元排名函數(shù)并給出量化節(jié)點(diǎn)重要性的評(píng)分。在此基礎(chǔ)上,將全局得分融入基于共鄰節(jié)點(diǎn)的相似度計(jì)算框架中,得到鏈接預(yù)測(cè)結(jié)果。實(shí)驗(yàn)結(jié)果表明,該算法的預(yù)測(cè)準(zhǔn)確率高于PR、EDC、ANC等對(duì)比算法。下一步將把其他節(jié)點(diǎn)影響力鑒定指標(biāo)納入到多元網(wǎng)絡(luò)鏈接預(yù)測(cè)算法中,并在超大規(guī)模的多元網(wǎng)絡(luò)中進(jìn)行實(shí)驗(yàn),驗(yàn)證本文算法的可擴(kuò)展性。