基于四階模體的有向網(wǎng)絡(luò)鏈路預(yù)測方法

常 圣 馬 宏 劉樹新 朱宇航

(中國人民解放軍戰(zhàn)略支援部隊(duì)信息工程大學(xué) 河南 鄭州 450002)

0 引 言

鏈路預(yù)測作為復(fù)雜網(wǎng)絡(luò)研究的一個(gè)重要分支，是指通過已知的網(wǎng)絡(luò)信息，預(yù)測網(wǎng)絡(luò)中兩個(gè)節(jié)點(diǎn)之間存在連邊的可能性[1]。鏈路預(yù)測是從連邊這個(gè)微觀角度探究網(wǎng)絡(luò)的結(jié)構(gòu)特點(diǎn)以及演化規(guī)律。鏈路預(yù)測技術(shù)可以解決缺失信息的還原、錯(cuò)誤信息的糾正、未來信息的預(yù)測等問題[2]。網(wǎng)絡(luò)技術(shù)的發(fā)展使網(wǎng)絡(luò)數(shù)據(jù)的獲取變得越來越容易，同時(shí)門戶網(wǎng)站、社交平臺(tái)和網(wǎng)上購物等新興事物的出現(xiàn)也使得對于推薦系統(tǒng)的需求變得更加迫切。如何吸引更多的用戶、創(chuàng)造更多的流量、提高自己的知名度等一直是各大平臺(tái)關(guān)注的焦點(diǎn)。通過鏈路預(yù)測技術(shù)，可以基于已有的用戶信息和網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，發(fā)現(xiàn)用戶潛在的朋友、興趣圈子、感興趣的商品等，將此類信息推送給用戶。如果推薦內(nèi)容與用戶的興趣一致性較高，將會(huì)極大地改善用戶的使用體驗(yàn)并增加用戶對于平臺(tái)的忠誠度。

鏈路預(yù)測不僅在現(xiàn)實(shí)世界中有著廣泛的應(yīng)用價(jià)值，在理論研究中也具有重要的意義。預(yù)測效果較好的方法在一定程度上反映了網(wǎng)絡(luò)的內(nèi)在特性和演化機(jī)制，為網(wǎng)絡(luò)演化理論提供思路，從而可以推動(dòng)相關(guān)理論研究的進(jìn)展。O’Madadhain等[3]曾使用鏈路預(yù)測方法對電話呼叫網(wǎng)絡(luò)進(jìn)行建模，進(jìn)而模擬社區(qū)的形成。Leicht等[4]提出了刻畫節(jié)點(diǎn)相似性的理論問題，而鏈路預(yù)測技術(shù)中基于相似性的指標(biāo)[5]就是從不同角度刻畫節(jié)點(diǎn)間的關(guān)系，這些方法可為該理論問題提供重要的研究依據(jù)。

1 相關(guān)研究

研究者們從不同的角度出發(fā)，對網(wǎng)絡(luò)中的結(jié)構(gòu)特征進(jìn)行刻畫，提出了豐富的鏈路預(yù)測算法。當(dāng)前鏈路預(yù)測方法通?？梢苑譃槿怺6]：基于相似度的方法、概率和統(tǒng)計(jì)方法、分類器方法。基于相似度的方法僅利用網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)對連邊進(jìn)行預(yù)測，具有簡單易懂，在集聚系數(shù)較高的網(wǎng)絡(luò)上預(yù)測效果好的特點(diǎn)，因此受到了學(xué)者們的廣泛關(guān)注。概率和統(tǒng)計(jì)方法通常根據(jù)已知的網(wǎng)絡(luò)結(jié)構(gòu)特點(diǎn)對網(wǎng)絡(luò)進(jìn)行建模。此類方法主要包括層次結(jié)構(gòu)模型[7]和隨機(jī)分塊模型[8]等。這些方法雖然預(yù)測精度較好，但是計(jì)算復(fù)雜度較高，難以應(yīng)用于規(guī)模較大的網(wǎng)絡(luò)。最后一類是分類器方法，連邊的存在與否可以看作為一個(gè)二分類問題，所以支持向量機(jī)(SVM)[9]、K近鄰算法(KNN)[10]和多層感知器[11]等方法都可以應(yīng)用到鏈路預(yù)測問題中。同時(shí)，節(jié)點(diǎn)的屬性信息也可以作為特征向量應(yīng)用到預(yù)測中，從而提高預(yù)測精確度，不過引入節(jié)點(diǎn)屬性會(huì)帶來復(fù)雜度增加和虛假信息等問題。此類方法預(yù)測效果通常較好，不過分類器本身的復(fù)雜性在一定程度上限制了其在現(xiàn)實(shí)場景中的廣泛應(yīng)用。

在鏈路預(yù)測領(lǐng)域的研究中，通常會(huì)把復(fù)雜網(wǎng)絡(luò)作為無向無權(quán)的同質(zhì)網(wǎng)絡(luò)研究。抽象和簡化便于我們在復(fù)雜多樣的外表下捕捉到一些不變的性質(zhì)，加深對系統(tǒng)的理解，加快研究的進(jìn)程。但是，當(dāng)前對于無向網(wǎng)絡(luò)已經(jīng)進(jìn)行了較為充分的研究，提出了很多重要的研究成果和預(yù)測方法，然而對于有向網(wǎng)絡(luò)的關(guān)注相對較少。現(xiàn)實(shí)世界中存在大量的有向關(guān)系，例如萬維網(wǎng)(WWW)、細(xì)胞內(nèi)化學(xué)反應(yīng)網(wǎng)絡(luò)、食物鏈網(wǎng)絡(luò)、引文網(wǎng)絡(luò)、微博網(wǎng)絡(luò)和知識(shí)圖譜等。以海洋生物的捕食關(guān)系為例(虎鯨→海豹→烏賊→魚類→軟體動(dòng)物→浮游生物)，如果忽略捕食關(guān)系的方向性，將其作為無向網(wǎng)絡(luò)處理，將無法知道是魚類吃軟體動(dòng)物，還是軟體動(dòng)物吃魚類，建模會(huì)出現(xiàn)較大的失真，僅預(yù)測連邊的存在與否而忽略連邊的方向性也會(huì)降低預(yù)測結(jié)果的意義。針對有向網(wǎng)絡(luò)的特征，結(jié)合有向網(wǎng)絡(luò)的連邊機(jī)理和演化模型，提出符合有向網(wǎng)絡(luò)內(nèi)在特點(diǎn)的預(yù)測算法具有重要意義。

少數(shù)學(xué)者已經(jīng)開始關(guān)注有向網(wǎng)絡(luò)的鏈路預(yù)測問題。文獻(xiàn)[12-13]曾把部分相似性指標(biāo)直接應(yīng)用于有向網(wǎng)絡(luò)。Narayanan等[12]將局部隨機(jī)游走推廣到了有向網(wǎng)絡(luò)，并取得了較好的預(yù)測效果。Lichtenwalter等[14]基于隨機(jī)游走提出了PropFlow方法。Wang等[15]提出了有向局部路徑指標(biāo)。

網(wǎng)絡(luò)模體是復(fù)雜網(wǎng)絡(luò)演化的重要拓?fù)浣Y(jié)構(gòu)，是指出現(xiàn)頻次較高的子圖模式[16]。模體代表了復(fù)雜系統(tǒng)中的重要功能單元或者某種特定的組織結(jié)構(gòu)，反映了復(fù)雜網(wǎng)絡(luò)中子圖形成的偏好性。近些年，部分學(xué)者開始嘗試基于子圖模式的方法來解決有向網(wǎng)絡(luò)中的鏈路預(yù)測問題。Brzozowski等[17]統(tǒng)計(jì)了社交網(wǎng)絡(luò)中三階子圖的閉合比例，并基于此進(jìn)行了好友推薦。Zhang等[18]提出了勢理論，篩選出了預(yù)測精度較高的雙風(fēng)扇模體(Bifan[19])。文獻(xiàn)[20]提出了三階子圖相似度指標(biāo)(TS)，其主要思想是計(jì)算13個(gè)三階子圖在整個(gè)網(wǎng)絡(luò)中出現(xiàn)的頻次，以此來計(jì)算節(jié)點(diǎn)間的相似性。Bütün等[21]分別計(jì)算9個(gè)非閉合三階子圖的相似性，而后將其組成一個(gè)9維特征向量作為機(jī)器學(xué)習(xí)的輸入。

四階模體作為復(fù)雜網(wǎng)絡(luò)的基礎(chǔ)結(jié)構(gòu)單元之一，普遍存在于各種類型的復(fù)雜系統(tǒng)中。當(dāng)前的方法通常忽略四階模體在相似性計(jì)算中的作用。針對上述現(xiàn)狀，本文提出一種基于四階模體的有向網(wǎng)絡(luò)鏈路預(yù)測方法。該方法首先提出了限定條件，對四階子圖進(jìn)行簡化，而后使用Z-score對四階子圖組進(jìn)行篩選，使用勝出的四階模體構(gòu)造預(yù)測算法。通過在9個(gè)不同性質(zhì)的真實(shí)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，并與基準(zhǔn)方法進(jìn)行比較，證明該方法預(yù)測精度更高。

2 基于四階模體的鏈路預(yù)測方法

非同構(gòu)子圖在有向網(wǎng)絡(luò)和無向網(wǎng)絡(luò)上的數(shù)量如表1所示。一些學(xué)者已經(jīng)基于三階模體進(jìn)行了鏈接預(yù)測的相關(guān)研究，但是很少有學(xué)者將四階模體應(yīng)用到鏈路預(yù)測中去，常見的相似性方法通常忽略了四階子圖在相似性中的貢獻(xiàn)。從表1可以看出，有向網(wǎng)絡(luò)中三階子圖僅有13個(gè)，而四階子圖則多達(dá)199個(gè)。如果計(jì)算所有的四階子圖，一方面計(jì)算復(fù)雜度很高，另一方面不同子圖之間的權(quán)重比不好衡量。所以要提出一個(gè)基于四階模體的預(yù)測方法，首要的事情是通過約束條件對四階子圖進(jìn)行篩選和簡化。

表1 無向和有向網(wǎng)絡(luò)中的非同構(gòu)子圖的數(shù)量[22]

2.1 四階模體篩選

首先，這里給出了閉合四階子圖、非閉合四階子圖和非交叉閉合四階子圖在有向網(wǎng)絡(luò)中的定義?？紤]有向網(wǎng)絡(luò)G(V，E)，其中：V是節(jié)點(diǎn)的集合；E代表連邊的集合。exy表示由節(jié)點(diǎn)x指向節(jié)點(diǎn)y的有向邊。以x為源節(jié)點(diǎn)的鄰居集合記為Γout(x)，x的出度記為|Γout(x)|(簡記為kout(x))。以x為目的節(jié)點(diǎn)的鄰居集合記為Γin(x)，x的入度表示為|Γin(x)|(簡記為kin(x))，x節(jié)點(diǎn)的所有鄰居集合記為Γin(x)∪Γout(x)(簡記為kall(x))。閉合四階子圖和非閉合四階子圖如圖1所示。

圖1 閉合四階子圖和非閉合四階子圖

定義1閉合四階子圖：對于一個(gè)給定的四階子圖Qabcd，如果存在eab,ebc,ecd,ead∈E，則稱Qabcd為閉合四階子圖。

定義2非閉合四階子圖：對于一個(gè)給定的四階子圖Qabcd，如果存在eab,ebc,ecd∈E并且ead?E，則稱Qabcd為非閉合四階子圖。

當(dāng)某個(gè)閉合四階子圖比較顯著的時(shí)候，其對應(yīng)的非閉合四階子圖可用于計(jì)算節(jié)點(diǎn)間的相似性。如果兩個(gè)節(jié)點(diǎn)之間存在的非閉合結(jié)構(gòu)數(shù)量越多，那么這兩個(gè)節(jié)點(diǎn)間產(chǎn)生連邊的可能性就越高。但是對于非閉合四階子圖，如圖2所示，無法計(jì)算非閉合子圖對應(yīng)結(jié)構(gòu)中節(jié)點(diǎn)x和y之間的相似性，因?yàn)閺南嗨频慕嵌瘸霭l(fā)，兩個(gè)節(jié)點(diǎn)沒有直接或間接的聯(lián)系，不存在結(jié)構(gòu)相似性。所以在本文中將閉合四階子圖作為分析對象。

圖2 為何選擇閉合模體

定義3非交叉閉合四階子圖：對于一個(gè)給定的四階子圖Qabcd，如果存在eab,ebc,ecd,ead∈E，并且eac,ebd?E，則稱Qabcd為非交叉閉合四階子圖。交叉四階模體和非交叉四階模體如圖3所示。

圖3 交叉四階模體和非交叉四階模體

交叉四階子圖在結(jié)構(gòu)上包含三階子圖，面對交叉四階子圖，可以用三階子圖的方法來進(jìn)行相似度計(jì)算。基于以上考慮，199個(gè)四階子圖中只有15個(gè)閉合且非交叉子圖，如圖4所示。

圖4 15個(gè)閉合非交叉四階子圖

Milo等[19]對有向網(wǎng)絡(luò)中的模體重要性進(jìn)行了分析，并提出了Z-score方法。該方法統(tǒng)計(jì)有向網(wǎng)絡(luò)中某一子圖的數(shù)目以及隨機(jī)網(wǎng)絡(luò)中該子圖的數(shù)目。在隨機(jī)網(wǎng)絡(luò)中，網(wǎng)絡(luò)的規(guī)模和連邊總數(shù)與現(xiàn)實(shí)網(wǎng)絡(luò)是一樣的，同時(shí)每個(gè)節(jié)點(diǎn)的出入度和原網(wǎng)絡(luò)保持一致。子圖顯著程度可以表示為：

(1)

子圖遍歷和Z-score的計(jì)算成本是非常高昂的，學(xué)者們對如何降低其復(fù)雜度做出了許多努力：從最初的ESU[23]全遍歷，到RAND-ESU部分遍歷，以及提高內(nèi)存使用率的Kavosh[24]等。在這個(gè)過程中，學(xué)者們不僅不斷改進(jìn)已有的算法、提出新的算法，并提供了很多實(shí)用的模體識(shí)別工具，例如MFinder[25]、Mavisto[26]、FANMOD[27]和Kavosh等等。FANMOD雖然提出得較早，但是其簡單易用，遍歷的效率也較高，是被普遍認(rèn)可的一款工具，本文使用FANMOD來實(shí)現(xiàn)顯著模體的篩選。

圖5顯示了9個(gè)網(wǎng)絡(luò)上15個(gè)四階子圖的平均Z-score結(jié)果，橫坐標(biāo)表示四階子圖，縱坐標(biāo)表示Z-score的值。為了使結(jié)果更加清晰明了，僅將兩個(gè)最為顯著的模體進(jìn)行了標(biāo)注，其余的子圖并未具體指出。可以清楚地看出，有兩個(gè)模體比其他子圖顯著程度要高出很多，這意味著這兩個(gè)模體在實(shí)際網(wǎng)絡(luò)出現(xiàn)得更加頻繁。

圖5 9個(gè)網(wǎng)絡(luò)中15個(gè)子圖的Z-score結(jié)果

2.2 方法設(shè)計(jì)

模體的Z-score值越高，在現(xiàn)實(shí)網(wǎng)絡(luò)中出現(xiàn)的頻次就越高。兩個(gè)節(jié)點(diǎn)之間的相似性可以通過四階模體對應(yīng)的非閉合結(jié)構(gòu)的數(shù)量來計(jì)算：如果一條連邊的出現(xiàn)可以產(chǎn)生更多的顯著模體，那么這條邊出現(xiàn)的概率就越大。如圖6所示，從兩個(gè)最為顯著的四階模體中各去除一條邊，得到其對應(yīng)的非閉合子圖，即三個(gè)預(yù)測器：P1、P2和F1。

圖6 預(yù)測器的構(gòu)造

其中基于P1結(jié)構(gòu)的相似性可表示為：

(2)

預(yù)測器P2和F1的相似度公式可以參照式(2)。

函數(shù)g(z1,z2)表示特定共同鄰居節(jié)點(diǎn)對于相似度的貢獻(xiàn)。如果忽略節(jié)點(diǎn)的度數(shù)，不考慮度數(shù)對相似度的影響，可以定義g(z1,z2)=1。本文將使用鄰居節(jié)點(diǎn)的局部信息對相似度計(jì)算進(jìn)行進(jìn)一步優(yōu)化。如圖6所示，在兩個(gè)模體的非閉合結(jié)構(gòu)中，有3種不同類型的節(jié)點(diǎn)。對于P1中的節(jié)點(diǎn)z1，模體的結(jié)構(gòu)僅與該節(jié)點(diǎn)的出度有關(guān)，而與其入度無關(guān)，所以以該節(jié)點(diǎn)的出度的倒數(shù)為相似度的權(quán)重。類似地，對于P2中節(jié)點(diǎn)z2，以該節(jié)點(diǎn)的入度的倒數(shù)作為權(quán)重。而對于P1中的節(jié)點(diǎn)z2來說，模體的頻次與該節(jié)點(diǎn)的出度和入度均有關(guān)，同時(shí)為了與其他兩種節(jié)點(diǎn)的權(quán)重保持一致性，則以該節(jié)點(diǎn)出入度之和的一半的倒數(shù)作為計(jì)算相似度?；谝陨峡紤]，g(z1,z2)的表達(dá)式表示為：

(3)

Z-score從統(tǒng)計(jì)的角度量化了模體的重要程度，但是對于鏈路預(yù)測問題，新連邊出現(xiàn)的概率和Z-score的值并不一定是線性關(guān)系，所以難以直接確定兩個(gè)模體之間的關(guān)系。這里引入了一個(gè)可變參數(shù)α，后續(xù)會(huì)通過實(shí)驗(yàn)來探討其最優(yōu)的取值。預(yù)測器P1和P2是由同一個(gè)模體衍生出來的，其地位是相等的，給它們分配相同的權(quán)重。QMI(Quad Motifs Index)可以由P1、P2和F1三個(gè)預(yù)測器的相似性函數(shù)之和的形式表示。基于四階模體的相似性函數(shù)可以表示為：

(4)

根據(jù)前面的論述，最終的相似度計(jì)算可以展開為：

(5)

3 仿真實(shí)驗(yàn)

3.1 基準(zhǔn)方法

為了了解基于四階模體的預(yù)測方法QMI的實(shí)際預(yù)測效果，本文選取了8個(gè)經(jīng)典預(yù)測指標(biāo)與QMI的預(yù)測結(jié)果進(jìn)行對比，簡介如下：

(1) 共同鄰居指標(biāo)(CN)：該方法認(rèn)為如果兩個(gè)節(jié)點(diǎn)的共同鄰居越多，則它們之間存在連邊的可能性就越大。

s(x,y)=|Γout(x)∩Γin(y)|

(6)

(2) Adamic-Adar指標(biāo)(AA)[28]：該方法在CN的基礎(chǔ)上，加入了對于節(jié)點(diǎn)度數(shù)的考慮，認(rèn)為低度數(shù)節(jié)點(diǎn)對于相似度貢獻(xiàn)較大。

(7)

(3) 資源分配指標(biāo)(RA)[29]：該指標(biāo)受到資源分配過程的啟發(fā)，給高度數(shù)節(jié)點(diǎn)較少的權(quán)重。

(8)

(4) S?rensen指標(biāo)(SO)[30]：該指標(biāo)常用于生態(tài)系統(tǒng)的數(shù)據(jù)集中。

(9)

(5) Leicht-Holme-Newman指標(biāo)(LHN)[31]：該方法在CN的基礎(chǔ)上加入了對節(jié)點(diǎn)度數(shù)的考慮。

(10)

(6) 全路徑指標(biāo)(Katz)[32]：Katz計(jì)算整個(gè)網(wǎng)絡(luò)中所有路徑的長度，并根據(jù)路徑的長度給予不同的權(quán)重，路徑越長分配的權(quán)重越低。Katz的相似度矩陣可以寫為：

S=(I-αA)-1-I

(11)

式中：A表示網(wǎng)絡(luò)的鄰接矩陣；I表示單位矩陣；α為可調(diào)參數(shù)，控制不同路徑的權(quán)重。

(7) 局部路徑指標(biāo)(LP)[33]：該方法與Katz指標(biāo)類似，但是只考慮有限長度的路徑。LP的相似度可以表示為：

S=A2+αA3

(12)

(8) 矩陣森林指數(shù)(MFI)[34]：該方法基于矩陣森林理論，其相似性矩陣可表示為：

S=(I+L)-1

(13)

式中：L表示網(wǎng)絡(luò)的拉普拉斯矩陣。

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

本文選擇的9個(gè)公開網(wǎng)絡(luò)數(shù)據(jù)集如下。

(1) 醫(yī)生網(wǎng)絡(luò)(Physicians)[35]：這個(gè)有向網(wǎng)絡(luò)描述的是4個(gè)城鎮(zhèn)中246名醫(yī)生之間創(chuàng)新思想的傳播關(guān)系。

(2) 電子郵件網(wǎng)絡(luò)(Email)[36]：歐洲研究機(jī)構(gòu)的電子郵件網(wǎng)絡(luò)，節(jié)點(diǎn)代表用戶，有向邊代表用戶發(fā)送過的郵件。

(3) 郵件網(wǎng)絡(luò)(DNC)[37]：這是民主黨全國委員會(huì)(DNC)的電子郵件網(wǎng)絡(luò)。有向邊表示人員之間的郵件往來。

(4) 食物鏈網(wǎng)絡(luò)(FWMW)[38]:雨季的食物鏈網(wǎng)絡(luò)，節(jié)點(diǎn)表示物種，有向邊代表捕食關(guān)系。

(5) 線蟲代謝網(wǎng)絡(luò)(CElegans)[39]：該數(shù)據(jù)集是秀麗隱桿線蟲的代謝網(wǎng)絡(luò)。節(jié)點(diǎn)是代謝物(如蛋白質(zhì))，連邊是代謝物之間的相互作用。

(6) 象棋比賽網(wǎng)絡(luò)(Chess)[37]：該網(wǎng)絡(luò)是國際象棋比賽的結(jié)果。每個(gè)節(jié)點(diǎn)是國際象棋棋手，有向邊代表棋手之間的比賽。

(7) 政治博客網(wǎng)絡(luò)(PB)[40]：這是美國政治博客之間的超鏈接網(wǎng)絡(luò)。對于博客A和博客B，由A指向B的有向邊表示同方向的超鏈接。原網(wǎng)絡(luò)是含有自環(huán)和多連邊的，本文會(huì)忽略這些特殊情況。

(8) 青少年網(wǎng)絡(luò)(Adolescent)[41]：節(jié)點(diǎn)代表學(xué)生，兩個(gè)學(xué)生之間的有向邊表明左邊的學(xué)生選擇了右邊的學(xué)生作為朋友。

(9) 維基百科(Wikivote)[42]：這是維基百科中的用戶選舉管理員的投票網(wǎng)絡(luò)。節(jié)點(diǎn)代表用戶，邊代表投票。原網(wǎng)絡(luò)的連邊是有正負(fù)邊兩種情況的，本文也對其進(jìn)行歸一化處理。

每個(gè)網(wǎng)絡(luò)的統(tǒng)計(jì)特征如表2所示。其中：|V|是整個(gè)網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)目，|E|表示有向邊的數(shù)量，Kout是最大出度，Kin是最大入度，k是平均度數(shù)，d代表網(wǎng)絡(luò)直徑，C為聚集系數(shù)。

表2 數(shù)據(jù)集的統(tǒng)計(jì)特征

3.3 評價(jià)指標(biāo)

實(shí)驗(yàn)度量指標(biāo)采用AUC[43]和Precision[44]對預(yù)測效果進(jìn)行評價(jià)。AUC是坐標(biāo)圖中ROC曲線以下的面積，其具體含義是正確預(yù)測測試集中邊的分?jǐn)?shù)值大于不存在邊的概率。AUC的計(jì)算通常采用隨機(jī)抽樣的方式進(jìn)行。每次隨機(jī)從測試集中選取一條邊，并隨機(jī)選一條不存在的邊，如果測試集中的邊分?jǐn)?shù)值較大，就加1分，相等就加0.5分。AUC的計(jì)算為：

(14)

式中：n1表示測試集中的邊的分?jǐn)?shù)大于不存在的邊的分?jǐn)?shù)的次數(shù)；n2代表分?jǐn)?shù)值相等的次數(shù)。

Precision表示排名靠前的L個(gè)預(yù)測邊中，正確預(yù)測的比例。如果在前L個(gè)預(yù)測邊中，有m條邊是正確的預(yù)測，則：

(15)

3.4 預(yù)測結(jié)果

為了衡量基于四階模體的預(yù)測方法QMI的實(shí)際表現(xiàn)，本節(jié)以AUC和Precision兩個(gè)指標(biāo)作為評價(jià)標(biāo)準(zhǔn)，在9個(gè)不同性質(zhì)的真實(shí)數(shù)據(jù)集上進(jìn)行100次獨(dú)立實(shí)驗(yàn)(每次實(shí)驗(yàn)都會(huì)重新劃分訓(xùn)練集和預(yù)測集，從而保證結(jié)果的可靠性)，并對實(shí)驗(yàn)結(jié)果的平均值進(jìn)行比較分析。具體包括：① QMI在不同局部信息情況下的預(yù)測效果； ② QMI在不同α取值條件下的預(yù)測結(jié)果；③ QMI與經(jīng)典相似性方法結(jié)果對比。

(1) 局部信息的影響。首先，給出QMI在考慮不同的節(jié)點(diǎn)度信息情況下的預(yù)測結(jié)果之間的差異，從而驗(yàn)證本文提出的對于節(jié)點(diǎn)度的考慮能否提高預(yù)測的效果。QMI0表示忽略共同鄰居節(jié)點(diǎn)的度信息，此時(shí)g(z1,z2)=1。QIMIM代表考慮共同鄰居節(jié)點(diǎn)的出度和入度信息，但是不考慮不同模體間的區(qū)別，對所有模體同等對待，此時(shí)g()定義為：

(16)

圖7展示了在不同局部信息的情況下QMI的AUC結(jié)果。橫坐標(biāo)表示9個(gè)數(shù)據(jù)集，縱坐標(biāo)表示AUC的結(jié)果?？梢钥闯?，QMI的AUC值在所有數(shù)據(jù)集中都是最高的。部分?jǐn)?shù)據(jù)集，例如CElegans對于共同鄰居的度信息更加敏感，AUC的差異稍大，而剩余網(wǎng)絡(luò)的預(yù)測結(jié)果較為接近。具體到個(gè)別網(wǎng)絡(luò)又表現(xiàn)出不同的特點(diǎn)。對于Email來說，QMIM和QMI0的AUC結(jié)果差異很小，但是和QMI的差異較大，這說明不加區(qū)分地考慮度信息對于預(yù)測是沒有實(shí)質(zhì)性提升的。在PB中，QMI和QMI0又比較接近，QMIM表現(xiàn)較差一些，這意味著不區(qū)分入度和出度對于預(yù)測甚至是有反作用的。

圖7 QMI在不同局部信息下的AUC結(jié)果對比

圖8展示的是在考慮不同的局部信息情況下QMI的Precision結(jié)果。總體上看，QMI和QMI0在9個(gè)網(wǎng)絡(luò)中的有著類似的走勢，而QMIM的Precision一直處于較低水平，這再次說明了入度和出度在有向網(wǎng)絡(luò)中有著不同的地位和作用。在FWMW網(wǎng)絡(luò)中，QMI的Precision高于0.8，而QMIM不到0.2，提升0.6以上。在大多數(shù)網(wǎng)絡(luò)中，QMI的預(yù)測精度相對于QMIM提升都達(dá)到了2倍以上。CElegans網(wǎng)絡(luò)是個(gè)例外，在這一網(wǎng)絡(luò)中QMIM的預(yù)測精度最高，達(dá)到了0.233，但是QMI的預(yù)測結(jié)果與QMIM相差不大。

圖8 QMI在不同局部信息下的Precision結(jié)果對比

總的來說，對于不同情況的共同鄰居，加以區(qū)分對待，考慮其出度和入度與所在模體之間的具體關(guān)系，可以提高預(yù)測的準(zhǔn)確度。

(2)α取值的影響。首先分析QMI在不同α取值條件下的AUC結(jié)果。如圖9所示，每幅子圖表示一個(gè)數(shù)據(jù)集。在所有數(shù)據(jù)集中，α=0或α=1時(shí)，AUC均沒有達(dá)到最大值，這表明兩個(gè)模體都是不可或缺的，它們對于相似度結(jié)果的影響都很大。此時(shí)需要考慮的問題是如何確定兩者之間的比例。在不同的數(shù)據(jù)集中，AUC曲線的走勢有較大的差異。在Email網(wǎng)絡(luò)中，AUC結(jié)果出現(xiàn)了一定程度的震蕩，其余網(wǎng)絡(luò)AUC曲線的走勢較為清晰。在FWMW、CElegans和PB中，AUC值隨著α的增大穩(wěn)定增長，在α=0附近增速稍快，后續(xù)相對平緩，說明這些網(wǎng)絡(luò)對于P1和P2結(jié)構(gòu)的敏感性不強(qiáng)。CElegans網(wǎng)絡(luò)在α達(dá)到0.7以后有小幅下降。當(dāng)α在0到0.1的區(qū)間時(shí)，Wikivote和DNC的AUC曲線非常陡峭，這說明預(yù)測器P1在這些網(wǎng)絡(luò)中起到了明顯的作用。在Physicians網(wǎng)絡(luò)中，AUC曲線在α取0和1附近均有大幅度的變化，而其余情況相對穩(wěn)定，說明預(yù)測效果同時(shí)依賴兩個(gè)模體，但是它們之間的比例關(guān)系對于預(yù)測影響有限?？v觀所有數(shù)據(jù)集，α在0.4到0.8之間時(shí)，AUC都達(dá)到了最優(yōu)值。同時(shí)在該區(qū)域，AUC值是較為穩(wěn)定的，浮動(dòng)很小。因此，在進(jìn)行預(yù)測時(shí)，最好將α的取值限定在0.4～0.8范圍內(nèi)。

圖9 不同α取值條件下QMI指標(biāo)的AUC結(jié)果

圖10是QMI在不同α取值條件下的Precision結(jié)果，每幅子圖表示一個(gè)數(shù)據(jù)集。除了Chess之外，其他網(wǎng)絡(luò)的Precision在α=0附近都有明顯的提高，這意味著預(yù)測器F1在Precision方面發(fā)揮著重要作用。在Email、Physicians、Adolescent和Chess中，Precision在達(dá)到峰值后都有一定程度的回落，回落的速率代表了對于P1和P2結(jié)構(gòu)的敏感程度。在FWMW、CElegans和Wikivote中，Precision曲線走勢穩(wěn)定，預(yù)測精度隨著α的增大穩(wěn)定增長，到達(dá)最優(yōu)值之后趨于穩(wěn)定，說明F1在這幾個(gè)網(wǎng)絡(luò)中作用更加重要。Adolescent和Chess在α取0.3 達(dá)到最高精度，Physicians在α約為0.6時(shí)獲得最好預(yù)測結(jié)果，其余網(wǎng)絡(luò)的都在α大于0.8之后達(dá)到峰值。不同于AUC，Precision曲線隨著α的變化浮動(dòng)較大。在FWMW中，Precision的最大值和最小值之間存在差異高達(dá)0.7，其余網(wǎng)絡(luò)的曲線相對穩(wěn)定許多。

圖10 不同α取值條件下QMI指標(biāo)的Precision結(jié)果

根據(jù)實(shí)驗(yàn)結(jié)果，并兼顧所有數(shù)據(jù)集的AUC和Precision，建議α取0.6。

(3) 與基準(zhǔn)方法的對比。為了進(jìn)一步了解QMI的預(yù)測效果，本文選取了8個(gè)經(jīng)典預(yù)測指標(biāo)與其進(jìn)行對比分析。表3中給出了QMI和基準(zhǔn)方法在9個(gè)數(shù)據(jù)集中的AUC結(jié)果。可以看出，在大多數(shù)數(shù)據(jù)集中，本文方法QMI的預(yù)測效果都是優(yōu)于其他方法的。除了Physicians和Adolescent，QMI在剩余的網(wǎng)絡(luò)中均取得了最高的AUC值。即使在這兩個(gè)網(wǎng)絡(luò)中，QMI的AUC值也非常接近最佳值，在Adolescent中與最高預(yù)測結(jié)果僅相差0.003，Physicians中相差0.02。除FWMW 和Adolescent網(wǎng)絡(luò)之外，大多數(shù)網(wǎng)絡(luò)中QMI的AUC值均高于0.91，由此可以看出該方法的預(yù)測效果較好。由于考慮了更多信息，全局方法Katz效果通常好于局部方法CN等，半局部方法略差于全局方法，但是相對于局部方法也有所提升。在局部性方法中，RA方法比CN多了對節(jié)點(diǎn)度數(shù)的考慮之后，預(yù)測精度有小幅提升，這說明節(jié)點(diǎn)的度數(shù)對相似度是有影響的。同樣考慮的是節(jié)點(diǎn)度數(shù)，但是RA考慮的是共同鄰居節(jié)點(diǎn)的度數(shù)信息，SO和LHN等考慮的是被預(yù)測節(jié)點(diǎn)的度數(shù)信息，相比而言，RA的效果是好于SO和LHN的，可以推測，共同鄰居節(jié)點(diǎn)的度數(shù)與相似度的關(guān)系更加緊密。在有些網(wǎng)絡(luò)中，SO和LHN甚至還略差于CN，這說明被預(yù)測節(jié)點(diǎn)的度數(shù)并不總能提升預(yù)測效果，在計(jì)算相似度時(shí)，最好是考慮共同鄰居節(jié)點(diǎn)的度數(shù)。

表3 QMI與基準(zhǔn)方法的AUC結(jié)果對比(可調(diào)參數(shù)α=0.6)

續(xù)表3

表4給出了QMI與基準(zhǔn)方法在9個(gè)數(shù)據(jù)集中Precision的比較結(jié)果。對比可知，基于四階模體方法的預(yù)測精度在7個(gè)數(shù)據(jù)集中達(dá)到了最優(yōu)。在PB和Email網(wǎng)絡(luò)中，QMI的效果與最優(yōu)值也比較接近。全局方法雖然考慮了更多的拓?fù)湫畔ⅲ瞧銹recision效果并不理想。在一半的網(wǎng)絡(luò)中，局部方法CN的預(yù)測精度高于全局方法Katz，這可能是因?yàn)镵atz對于AUC的關(guān)注更多。在局部方法中，RA等方法比CN多了對節(jié)點(diǎn)度數(shù)的考慮之后，Precision反而有所下降，而AA的預(yù)測結(jié)果有所提升，這說明AA指標(biāo)對于度數(shù)的處理(取對數(shù))更契合Precision。與其他指標(biāo)相比，MFI的預(yù)測結(jié)果在不同網(wǎng)絡(luò)中浮動(dòng)較大。在FWMW和CElegans中，MFI接近最高的Precision值，但在其他網(wǎng)絡(luò)中，MFI的精度又異常低。

表4 QMI與基準(zhǔn)方法的Precision結(jié)果對比(可調(diào)參數(shù)α=0.6)

4 結(jié) 語

為了從為數(shù)眾多的四階子圖中選出顯著模體，從而提出一個(gè)預(yù)測效果較好的方法，本文在閉合四階子圖和非交叉四階子圖兩個(gè)條件下，過濾了大量的四階子圖，在此基礎(chǔ)上又使用FANMOD計(jì)算了四階子圖在9個(gè)不同性質(zhì)網(wǎng)絡(luò)中的顯著程度，從中選取了2個(gè)最為顯著的模體。以顯著模體對應(yīng)的非閉合結(jié)構(gòu)作為相似度計(jì)算的依據(jù)，討論了共同鄰居節(jié)點(diǎn)的度信息在預(yù)測中的作用，通過實(shí)驗(yàn)確定了可調(diào)參數(shù)建議的取值區(qū)間。通過與8個(gè)經(jīng)典預(yù)測指標(biāo)的對比，結(jié)果表明本文方法可以同時(shí)提高AUC和Precision的結(jié)果。

除了四階模體以外，還存在很多高階模體，高階模體在相似性計(jì)算中起到何種作用還有待研究，不同階模體之間的關(guān)系如何衡量等都是今后值得研究的問題。