基于四階模體的有向網絡鏈路預測方法

常 圣 馬 宏 劉樹新 朱宇航

(中國人民解放軍戰略支援部隊信息工程大學 河南 鄭州 450002)

0 引 言

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

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

1 相關研究

研究者們從不同的角度出發，對網絡中的結構特征進行刻畫，提出了豐富的鏈路預測算法。當前鏈路預測方法通常可以分為三類[6]：基于相似度的方法、概率和統計方法、分類器方法?；谙嗨贫鹊姆椒▋H利用網絡的拓撲結構對連邊進行預測，具有簡單易懂，在集聚系數較高的網絡上預測效果好的特點，因此受到了學者們的廣泛關注。概率和統計方法通常根據已知的網絡結構特點對網絡進行建模。此類方法主要包括層次結構模型[7]和隨機分塊模型[8]等。這些方法雖然預測精度較好，但是計算復雜度較高，難以應用于規模較大的網絡。最后一類是分類器方法，連邊的存在與否可以看作為一個二分類問題，所以支持向量機(SVM)[9]、K近鄰算法(KNN)[10]和多層感知器[11]等方法都可以應用到鏈路預測問題中。同時，節點的屬性信息也可以作為特征向量應用到預測中，從而提高預測精確度，不過引入節點屬性會帶來復雜度增加和虛假信息等問題。此類方法預測效果通常較好，不過分類器本身的復雜性在一定程度上限制了其在現實場景中的廣泛應用。

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

少數學者已經開始關注有向網絡的鏈路預測問題。文獻[12-13]曾把部分相似性指標直接應用于有向網絡。Narayanan等[12]將局部隨機游走推廣到了有向網絡，并取得了較好的預測效果。Lichtenwalter等[14]基于隨機游走提出了PropFlow方法。Wang等[15]提出了有向局部路徑指標。

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

四階模體作為復雜網絡的基礎結構單元之一，普遍存在于各種類型的復雜系統中。當前的方法通常忽略四階模體在相似性計算中的作用。針對上述現狀，本文提出一種基于四階模體的有向網絡鏈路預測方法。該方法首先提出了限定條件，對四階子圖進行簡化，而后使用Z-score對四階子圖組進行篩選，使用勝出的四階模體構造預測算法。通過在9個不同性質的真實數據集上進行實驗，并與基準方法進行比較，證明該方法預測精度更高。

2 基于四階模體的鏈路預測方法

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

表1 無向和有向網絡中的非同構子圖的數量[22]

2.1 四階模體篩選

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

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

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

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

當某個閉合四階子圖比較顯著的時候，其對應的非閉合四階子圖可用于計算節點間的相似性。如果兩個節點之間存在的非閉合結構數量越多，那么這兩個節點間產生連邊的可能性就越高。但是對于非閉合四階子圖，如圖2所示，無法計算非閉合子圖對應結構中節點x和y之間的相似性，因為從相似的角度出發，兩個節點沒有直接或間接的聯系，不存在結構相似性。所以在本文中將閉合四階子圖作為分析對象。

圖2 為何選擇閉合模體

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

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

交叉四階子圖在結構上包含三階子圖，面對交叉四階子圖，可以用三階子圖的方法來進行相似度計算?；谝陨峡紤]，199個四階子圖中只有15個閉合且非交叉子圖，如圖4所示。

圖4 15個閉合非交叉四階子圖

Milo等[19]對有向網絡中的模體重要性進行了分析，并提出了Z-score方法。該方法統計有向網絡中某一子圖的數目以及隨機網絡中該子圖的數目。在隨機網絡中，網絡的規模和連邊總數與現實網絡是一樣的，同時每個節點的出入度和原網絡保持一致。子圖顯著程度可以表示為：

(1)

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

圖5顯示了9個網絡上15個四階子圖的平均Z-score結果，橫坐標表示四階子圖，縱坐標表示Z-score的值。為了使結果更加清晰明了，僅將兩個最為顯著的模體進行了標注，其余的子圖并未具體指出?？梢郧宄乜闯?，有兩個模體比其他子圖顯著程度要高出很多，這意味著這兩個模體在實際網絡出現得更加頻繁。

圖5 9個網絡中15個子圖的Z-score結果

2.2 方法設計

模體的Z-score值越高，在現實網絡中出現的頻次就越高。兩個節點之間的相似性可以通過四階模體對應的非閉合結構的數量來計算：如果一條連邊的出現可以產生更多的顯著模體，那么這條邊出現的概率就越大。如圖6所示，從兩個最為顯著的四階模體中各去除一條邊，得到其對應的非閉合子圖，即三個預測器：P1、P2和F1。

圖6 預測器的構造

其中基于P1結構的相似性可表示為：

(2)

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

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

(3)

Z-score從統計的角度量化了模體的重要程度，但是對于鏈路預測問題，新連邊出現的概率和Z-score的值并不一定是線性關系，所以難以直接確定兩個模體之間的關系。這里引入了一個可變參數α，后續會通過實驗來探討其最優的取值。預測器P1和P2是由同一個模體衍生出來的，其地位是相等的，給它們分配相同的權重。QMI(Quad Motifs Index)可以由P1、P2和F1三個預測器的相似性函數之和的形式表示?；谒碾A模體的相似性函數可以表示為：

(4)

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

(5)

3 仿真實驗

3.1 基準方法

為了了解基于四階模體的預測方法QMI的實際預測效果，本文選取了8個經典預測指標與QMI的預測結果進行對比，簡介如下：

(1) 共同鄰居指標(CN)：該方法認為如果兩個節點的共同鄰居越多，則它們之間存在連邊的可能性就越大。

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

(6)

(2) Adamic-Adar指標(AA)[28]：該方法在CN的基礎上，加入了對于節點度數的考慮，認為低度數節點對于相似度貢獻較大。

(7)

(3) 資源分配指標(RA)[29]：該指標受到資源分配過程的啟發，給高度數節點較少的權重。

(8)

(4) S?rensen指標(SO)[30]：該指標常用于生態系統的數據集中。

(9)

(5) Leicht-Holme-Newman指標(LHN)[31]：該方法在CN的基礎上加入了對節點度數的考慮。

(10)

(6) 全路徑指標(Katz)[32]：Katz計算整個網絡中所有路徑的長度，并根據路徑的長度給予不同的權重，路徑越長分配的權重越低。Katz的相似度矩陣可以寫為：

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

(11)

式中：A表示網絡的鄰接矩陣；I表示單位矩陣；α為可調參數，控制不同路徑的權重。

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

S=A2+αA3

(12)

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

S=(I+L)-1

(13)

式中：L表示網絡的拉普拉斯矩陣。

3.2 數據集

本文選擇的9個公開網絡數據集如下。

(1) 醫生網絡(Physicians)[35]：這個有向網絡描述的是4個城鎮中246名醫生之間創新思想的傳播關系。

(2) 電子郵件網絡(Email)[36]：歐洲研究機構的電子郵件網絡，節點代表用戶，有向邊代表用戶發送過的郵件。

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

(4) 食物鏈網絡(FWMW)[38]:雨季的食物鏈網絡，節點表示物種，有向邊代表捕食關系。

(5) 線蟲代謝網絡(CElegans)[39]：該數據集是秀麗隱桿線蟲的代謝網絡。節點是代謝物(如蛋白質)，連邊是代謝物之間的相互作用。

(6) 象棋比賽網絡(Chess)[37]：該網絡是國際象棋比賽的結果。每個節點是國際象棋棋手，有向邊代表棋手之間的比賽。

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

(8) 青少年網絡(Adolescent)[41]：節點代表學生，兩個學生之間的有向邊表明左邊的學生選擇了右邊的學生作為朋友。

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

每個網絡的統計特征如表2所示。其中：|V|是整個網絡中節點數目，|E|表示有向邊的數量，Kout是最大出度，Kin是最大入度，k是平均度數，d代表網絡直徑，C為聚集系數。

表2 數據集的統計特征

3.3 評價指標

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

(14)

式中：n1表示測試集中的邊的分數大于不存在的邊的分數的次數；n2代表分數值相等的次數。

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

(15)

3.4 預測結果

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

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

(16)

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

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

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

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

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

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

圖9 不同α取值條件下QMI指標的AUC結果

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

圖10 不同α取值條件下QMI指標的Precision結果

根據實驗結果，并兼顧所有數據集的AUC和Precision，建議α取0.6。

(3) 與基準方法的對比。為了進一步了解QMI的預測效果，本文選取了8個經典預測指標與其進行對比分析。表3中給出了QMI和基準方法在9個數據集中的AUC結果?？梢钥闯觯诖蠖鄶禂祿校疚姆椒≦MI的預測效果都是優于其他方法的。除了Physicians和Adolescent，QMI在剩余的網絡中均取得了最高的AUC值。即使在這兩個網絡中，QMI的AUC值也非常接近最佳值，在Adolescent中與最高預測結果僅相差0.003，Physicians中相差0.02。除FWMW 和Adolescent網絡之外，大多數網絡中QMI的AUC值均高于0.91，由此可以看出該方法的預測效果較好。由于考慮了更多信息，全局方法Katz效果通常好于局部方法CN等，半局部方法略差于全局方法，但是相對于局部方法也有所提升。在局部性方法中，RA方法比CN多了對節點度數的考慮之后，預測精度有小幅提升，這說明節點的度數對相似度是有影響的。同樣考慮的是節點度數，但是RA考慮的是共同鄰居節點的度數信息，SO和LHN等考慮的是被預測節點的度數信息，相比而言，RA的效果是好于SO和LHN的，可以推測，共同鄰居節點的度數與相似度的關系更加緊密。在有些網絡中，SO和LHN甚至還略差于CN，這說明被預測節點的度數并不總能提升預測效果，在計算相似度時，最好是考慮共同鄰居節點的度數。

表3 QMI與基準方法的AUC結果對比(可調參數α=0.6)

續表3

表4給出了QMI與基準方法在9個數據集中Precision的比較結果。對比可知，基于四階模體方法的預測精度在7個數據集中達到了最優。在PB和Email網絡中，QMI的效果與最優值也比較接近。全局方法雖然考慮了更多的拓撲信息，但是其Precision效果并不理想。在一半的網絡中，局部方法CN的預測精度高于全局方法Katz，這可能是因為Katz對于AUC的關注更多。在局部方法中，RA等方法比CN多了對節點度數的考慮之后，Precision反而有所下降，而AA的預測結果有所提升，這說明AA指標對于度數的處理(取對數)更契合Precision。與其他指標相比，MFI的預測結果在不同網絡中浮動較大。在FWMW和CElegans中，MFI接近最高的Precision值，但在其他網絡中，MFI的精度又異常低。

表4 QMI與基準方法的Precision結果對比(可調參數α=0.6)

4 結 語

為了從為數眾多的四階子圖中選出顯著模體，從而提出一個預測效果較好的方法，本文在閉合四階子圖和非交叉四階子圖兩個條件下，過濾了大量的四階子圖，在此基礎上又使用FANMOD計算了四階子圖在9個不同性質網絡中的顯著程度，從中選取了2個最為顯著的模體。以顯著模體對應的非閉合結構作為相似度計算的依據，討論了共同鄰居節點的度信息在預測中的作用，通過實驗確定了可調參數建議的取值區間。通過與8個經典預測指標的對比，結果表明本文方法可以同時提高AUC和Precision的結果。

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