一種改進的二分網(wǎng)絡(luò)鏈路預(yù)測算法

馬吳迪， 胡學(xué)鋼， 何 偉

（合肥工業(yè)大學(xué) 計算機與信息學(xué)院，安徽 合肥 230009）

0 引 言

復(fù)雜網(wǎng)絡(luò)是由數(shù)量巨大的節(jié)點和節(jié)點之間錯綜復(fù)雜的關(guān)系共同構(gòu)成的網(wǎng)絡(luò)結(jié)構(gòu)。復(fù)雜網(wǎng)絡(luò)中節(jié)點之間關(guān)系會隨時間的流逝不斷變化，這種動態(tài)特性，使網(wǎng)絡(luò)整體的拓撲結(jié)構(gòu)不斷進行著演化。鏈路預(yù)測［1］是利用網(wǎng)絡(luò)的拓撲結(jié)構(gòu)來預(yù)測網(wǎng)絡(luò)中節(jié)點對之間缺失［2－4］或可能產(chǎn)生的鏈接，是探索和分析網(wǎng)絡(luò)結(jié)構(gòu)演化的重要手段。如在社交網(wǎng)絡(luò)中好友關(guān)系鏈路預(yù)測利用已存在的好友關(guān)系預(yù)測將來哪些用戶會成為好友；會員參與互動話題的關(guān)系網(wǎng)絡(luò)［5］通過目前會員參與話題的情況預(yù)測會員未來會參與哪些話題等。

根據(jù)目標(biāo)網(wǎng)絡(luò)中的節(jié)點類型，已有的復(fù)雜網(wǎng)絡(luò)研究可以分為單分網(wǎng)絡(luò)和二分網(wǎng)絡(luò)2類。如果一個網(wǎng)絡(luò)中包含2類節(jié)點，并且網(wǎng)絡(luò)中的邊只存在于不同類型的節(jié)點間，稱為二分網(wǎng)絡(luò)［6］，其抽象的拓撲圖為二部圖。現(xiàn)實世界中二分網(wǎng)絡(luò)的普遍性，使得針對二分網(wǎng)絡(luò)不同類型節(jié)點間的鏈路預(yù)測具有廣泛的應(yīng)用價值。單分網(wǎng)絡(luò)中的鏈路預(yù)測算法往往是基于節(jié)點對的結(jié)構(gòu)相似度來進行預(yù)測的［7］。二部圖中產(chǎn)生鏈接的節(jié)點對屬于不同類別，其鄰居節(jié)點也分別屬于不同類別，這使得單分網(wǎng)絡(luò)的鏈路預(yù)測算法無法直接應(yīng)用在二分網(wǎng)絡(luò)中。

ILP［8］是一種有效的二分網(wǎng)絡(luò)鏈路預(yù)測方法，但是由于其采用單向的投影策略即底部投影，容易導(dǎo)致信息丟失。本文在內(nèi)部鏈路預(yù)測算法ILP的基礎(chǔ)上，提出一種改進的鏈路預(yù)測算法ILPExt，采用底部和頂部雙向投影策略，避免了丟失信息，從而提高了鏈路預(yù)測的精度。

1 相關(guān)工作

已有的二分網(wǎng)絡(luò)鏈路預(yù)測算法中，大都是通過計算節(jié)點之間的相似性進行預(yù)測，主要分為2類，如圖1所示。

圖1 二分網(wǎng)絡(luò)鏈路預(yù)測算法類別

（1）基于圖鄰接矩陣的代數(shù)運算［9］。通過對整個網(wǎng)絡(luò)的鄰接矩陣分解［10］，不僅僅得到節(jié)點近鄰的信息，還能夠計算整個網(wǎng)絡(luò)的信息，在圖鄰接矩陣的轉(zhuǎn)換中能夠用來進行鏈路預(yù)測，該類方法稱為代數(shù)鏈路預(yù)測算法。假設(shè)A代表圖的鏈接矩陣，在Ai中（u，v）位置代表了節(jié)點u到節(jié)點v的步數(shù)為i的路徑數(shù)。在二分網(wǎng)絡(luò)中鏈接的節(jié)點對都是奇數(shù)個，因此i都取奇數(shù)。

代數(shù)鏈路預(yù)測算法由于其可擴展性和可學(xué)習(xí)性的特點，得到廣泛的關(guān)注。其可伸縮性特點是由于其依賴的鄰接矩陣模型只需要一次建立，在推薦算法中速度較快，模型對應(yīng)的矩陣分解能夠通過迭代計算進行更新。其可學(xué)習(xí)性表現(xiàn)在其參數(shù)都用相同的方法訓(xùn)練得到。但是該類算法在計算時內(nèi)存開銷比較大。

（2）基于局部信息的方法，采用與節(jié)點度有關(guān)聯(lián)的指標(biāo)。單分網(wǎng)絡(luò)中提出來的基于局部信息的指標(biāo)中，有限鏈接PA（Preferential Attachment）是唯一應(yīng)用在二分網(wǎng)絡(luò)中的鏈路預(yù)測算法。它基于這樣的假設(shè)：若2個節(jié)點的鄰居越多，則它們之間越有可能產(chǎn)生連邊。節(jié)點對（u，v）的相似度計算為2個節(jié)點度的乘積除以邊數(shù)：d（u）×d（v）／2｜E｜，其中，d（u）表示節(jié)點u的鄰居個數(shù)；E表示網(wǎng)絡(luò)中已有的邊數(shù)。PA算法的特點在于所需要的信息較少，但其適用的網(wǎng)絡(luò)具有一定的局限性。

除了基于相似性的算法，一些更復(fù)雜的算法不斷地被提出。文獻［2］提出了一個基于層次化網(wǎng)絡(luò)結(jié)構(gòu)的算法，根據(jù)節(jié)點在層次網(wǎng)絡(luò)中的深度預(yù)測其橫向連接概率的依賴性，并對其進行排序來預(yù)測缺失邊；文獻［11－12］分別將物理過程中的能量擴散和熱傳導(dǎo)引入信息推薦方面，雖然相關(guān)的問題還沒有被充分研究，但為提高鏈路預(yù)測算法的精度和效率提供了一種有效的途徑。

本文基于內(nèi)部鏈路的算法與上述所列的算法不同，它們是計算節(jié)點對的相似度值，然后根據(jù)值的大小排序，值越大的越有可能產(chǎn)生鏈接。內(nèi)部鏈路預(yù)測算法是通過定義內(nèi)部鏈邊，找出所有的內(nèi)部鏈邊，這些內(nèi)部鏈邊就是所要預(yù)測的邊。內(nèi)部鏈接的定義是基于如下假設(shè)：如果2個底部節(jié)點有共同鄰居，那么它們以后會有更多的共同鄰居；否則，如果它們沒有共同鄰居，那么它們將來也不會有共同鄰居。

2 改進的內(nèi)部鏈路預(yù)測ILPExt算法

2.1 基本定義

一個動態(tài)變化的二部圖，在n個時間點能夠得到一個鏈邊集合：D＝｛（ti，ui，vi），i＝1，…，n｝。用G＝（⊥，T，E）表示一個從時刻a到時刻b（b＞a）的二部圖，其中，⊥＝｛u，?（t，u，v）∈D，a≤t＜b｝為底部節(jié)點集合，Τ＝｛v，?（t，u，v）∈D，a≤t＜b｝為頂部節(jié)點集合，以E＝｛（u，v），?（t，u，v）∈D，a≤t＜b｝為邊集。G是參考圖，［a，b］為參考時段，是研究問題需要利用的信息。在之后的任一時刻c（c＞b），［b，c］這段時間內(nèi)，圖G中將出現(xiàn)一個新邊集E′＝｛（u，v），?（t，u，v）∈D，b≤t＜c｝∩（⊥×Τ－E）為測試邊集，也就是只考慮（⊥×Τ－E）中的節(jié)點對哪些會生成連邊，忽略在［b，c］時間段新出現(xiàn)的節(jié)點。

二部圖是由1個頂部節(jié)點集合（用符號⊥表示）、1個底部節(jié)點集合（用符號Τ表示）和1個由頂部節(jié)點和底部節(jié)點的鏈接邊集（用符號E表示）組成的圖。二部圖中節(jié)點的鄰居，定義為N（u）＝｛v∈（⊥∪Τ），（u，v）∈E｝，節(jié)點u的鄰居是在二部圖中所有與u相連的節(jié)點。在二部圖投影的圖中如果2個節(jié)點有至少1個共同鄰居，它們在投影的圖中就產(chǎn)生鏈接，那么二部圖G投影的節(jié)點由底部節(jié)點構(gòu)成，用G⊥表示，頂部節(jié)點的投影用GΤ表示。例如，圖2所示為二部圖，圖3所示為二部圖投影。

圖2 二部圖G

圖3 二部圖投影圖

基于內(nèi)部鏈邊的鏈路預(yù)測算法ILP首先找出所有可能的內(nèi)部鏈邊（internal link），然后通過附加的權(quán)值函數(shù)以及權(quán)值閾值過濾掉權(quán)值較低的邊。剩下的邊即是要預(yù)測的邊。它基于的思想是如果2個底部節(jié)點有共同鄰居，那么它們會有越來越多的共同鄰居。ILP算法在第1步節(jié)點投影過程中，通過投影利用了網(wǎng)絡(luò)中底部節(jié)點的拓撲信息，沒有對頂部節(jié)點投影，從而丟失了頂部節(jié)點所包含的信息。

下面來說明丟失頂部信息的情況。觀察圖2中節(jié)點對（B，l），首先，對二部圖底部投影，投影圖如圖3a，（B，l）誘導(dǎo)的節(jié)點對集｛（B，C），（B，D），（B，E）｝在圖3a中都有連邊，因此（B，l）在底部投影時是內(nèi)部鏈邊。然后對圖2進行頂部節(jié)點投影，投影出來的拓撲圖如圖3b所示，由節(jié)點對（B，l）誘導(dǎo)的節(jié)點對集｛（i，l），（j，l），（k，l），（m，l）｝，前面3個投影圖中都有連邊，而節(jié)點對（m，l）由于在圖2中沒有共同鄰居，在投影圖中不存在這個邊，所以節(jié)點對（B，l）就不是內(nèi)部連邊。

節(jié)點對（B，l）在采用底部節(jié)點投影時是內(nèi)部鏈邊，而采用頂部節(jié)點投影時不是內(nèi)部鏈邊。同理，這種情況節(jié)點對也可能在頂部投影中是內(nèi)部鏈邊，而在底部投影中卻不是內(nèi)部鏈邊。因此采取單一類節(jié)點投影總會丟失另一類節(jié)點所包含的信息。

2.2 ILPExt算法描述

本文提出改進的基于內(nèi)部鏈邊鏈路預(yù)測ILPExt算法，將同時采用頂部節(jié)點投影和底部節(jié)點投影，由此產(chǎn)生頂部內(nèi)部鏈邊集合和底部內(nèi)部鏈邊集合，將這2個集合合并，相同的邊只保留1條，運算的結(jié)果即是要預(yù)測的邊集。ILPExt算法步驟描述如下：

（1）對二部圖G分別進行頂部和底部投影，得到頂部投影邊集E⊥和底部投影邊集EΤ。

（2）在G中遍歷所有未鏈接的節(jié)點對，找出所有的內(nèi)部鏈邊，集合記為Ei1。

（3）過濾2個投影邊集EΤ和E⊥，將權(quán)值小于指定閾值的邊都刪除，得到EΤ和E⊥。

（4）過濾內(nèi)部鏈邊集合Ei1：如果內(nèi)部鏈邊的引起邊至少有1條屬于（E⊥∪EΤ） ，則保留該邊，否則刪除。

（5）篩選出來的內(nèi)部鏈邊集合Ei1就是該算法的預(yù)測邊集。

假設(shè)網(wǎng)絡(luò)中頂部節(jié)點數(shù)為N，底部節(jié)點數(shù)為M，邊數(shù)為R。ILPExt算法總的時間復(fù)雜度由投影和內(nèi)部鏈邊的查找構(gòu)成。

計算頂部和底部投影，需要分別遍歷頂部節(jié)點和底部節(jié)點的鄰居來生成投影圖的邊。對頂部節(jié)點投影時，判斷頂部節(jié)點對是否有共同鄰居，如果有則在投影圖中有邊；反之，則沒有。底部節(jié)點的鄰居是頂部節(jié)點，一個底部節(jié)點的鄰居之間，都擁有該底部節(jié)點作為共同鄰居，這樣一個底部節(jié)點的鄰居中隨機取2個節(jié)點在頂部投影中都會有邊。在頂部節(jié)點投影中，只要遍歷底部節(jié)點的鄰居就可以產(chǎn)生頂部節(jié)點的投影圖，時間復(fù)雜度是O（M）。同樣，底部節(jié)點投影的時間復(fù)雜度是O（N）。故頂部和底部節(jié)點投影的時間復(fù)雜度為O（N＋M）。所有未連邊的節(jié)點對為N×MR個，找出內(nèi)部鏈邊過程的時間復(fù)雜度為O（N×M）。過濾2個投影邊集的時間復(fù)雜度為O（R）。過濾內(nèi)部鏈邊集合，遍歷所有內(nèi)部鏈邊，找出每一條鏈邊是否在過濾后的邊集EΤ和E⊥中，因此遍歷內(nèi)部鏈邊集合的同時會遍歷過濾后的邊集EΤ和E⊥，因此時間復(fù)雜度為O（R×2）。所以，整個算法的時間復(fù)雜度為O（N×M＋R×2＋N＋M）。

3 實驗結(jié)果及分析

本文的實驗采用2個數(shù)據(jù)集，一個是Southern Women Data，另一個是類似facebook社交網(wǎng)站的用戶話題網(wǎng)絡(luò)。

（1）Southern Women Data［13］。該數(shù)據(jù)集由Davis在1930年收集，他采集了18個南部女性參加社會活動的情況。網(wǎng)絡(luò)結(jié)構(gòu)如圖4所示，其中圓點代表女性個體，方點代表社會活動，節(jié)點間的邊表示女性參加了活動。網(wǎng)絡(luò)中代表婦女的節(jié)點數(shù)為18，代表活動的節(jié)點數(shù)為14，邊數(shù)為89。

圖4 Southern Women Data數(shù)據(jù)集的網(wǎng)絡(luò)圖

在此網(wǎng)絡(luò)上進行鏈路預(yù)測，首先選出10條邊作為測試集，還剩下79條邊，見表1所列。

該實驗分別做了20次，每次都隨機抽取10條作為測試邊集，實驗結(jié)果見表2所列，表2中加星號的數(shù)字表示ILPExt比ILP算法效果好。每行有2個加星號表示效果一樣。從實驗結(jié)果中可以看出，采用頂部和底部投影產(chǎn)生出的內(nèi)部鏈邊并集時（ILPExt）預(yù)測出來的邊較多，而采用交集時預(yù)測效果比較差。這很容易理解，內(nèi)部鏈邊并集時同時包含了2類節(jié)點的內(nèi)部鏈邊，比僅采用一類節(jié)點投影時加上了另外一類節(jié)點所產(chǎn)生的內(nèi)部鏈邊預(yù)測出來的也多，而交集則取2個集合的共同部分的邊集僅僅是采用一類節(jié)點的一部分，預(yù)測出來的因而會少。

（2）Facebook－like Forum Network，該數(shù)據(jù)集是like－Facebook在線社交網(wǎng)絡(luò)網(wǎng)站數(shù)據(jù)，該網(wǎng)絡(luò)是由會員參與話題的關(guān)系而不是會員之間發(fā)送信息的行為來形成。網(wǎng)絡(luò)中有899個會員和522個主題，網(wǎng)絡(luò)中的權(quán)值是會員在參與主題中發(fā)布的消息數(shù)目，見表3所列。

表1 Southern Women Data數(shù)據(jù)集概況

表2 Southern Women Data實驗詳細結(jié)果

實驗做了20次，實驗結(jié)果見表4所列，表4中加星號的數(shù)字表示ILPExt比ILP算法效果好，每行有2個加星號表示效果一樣。從表4中可以看到取2個集合的并集時（ILPExt）準確預(yù)測的邊數(shù)要比分別用底部或者頂部節(jié)點投影 （ILP）準確預(yù)測出來的邊要多。

表3 Facebook－like Forum Network數(shù)據(jù)集概況及結(jié)果

表4 Facebook－like Forum Network數(shù)據(jù)集實驗詳細結(jié)果

通過上述2組實驗的結(jié)果可以看出，相比于ILP算法，改進后的ILPExt算法由于結(jié)合了2類節(jié)點的投影圖，能夠更加充分地利用網(wǎng)絡(luò)蘊含的拓撲結(jié)構(gòu)信息，從而能夠找出更多的邊，這一優(yōu)勢在節(jié)點較多的網(wǎng)絡(luò)中體現(xiàn)更加明顯。

該算法的改進是通過增大內(nèi)部鏈邊的范圍，因此搜索遍歷的范圍增大了不少，相應(yīng)的時間方面消耗過多，因此時間性能有待提高。

4 結(jié)束語

在ILP算法中，只采用了底部節(jié)點投影，找出最有可能產(chǎn)生邊的節(jié)點對，因此丟失了頂部節(jié)點所包含的信息。本文針對ILP算法的這一不足，提出改進的ILPExt算法，將底部節(jié)點和頂部節(jié)點都投影，投影后將2個部分的內(nèi)部鏈邊集合合并，然后產(chǎn)生出預(yù)測邊集。實驗證明能夠找出更多可預(yù)測的邊，而且召回率甚至是原算法的2倍多。

［1］ LüL，Zhou T.Link prediction in complex networks：a survey［J］.Physica A：Statistical Mechanics and its Applications，2011，390（6）：1150－1170.

［2］ Clauset A，Moore C，Newman M E J.Hierarchical structure and the prediction of missing links in networks［J］.Nature，2008，453（7191）：98－101.

［3］ Liben－Nowell D，Kleinberg J.The link－prediction problem for social networks［J］.J Am Soc Inf Sci，2007，58：1019－1031.

［4］ Getoor L，Diehl C P.Link mining：a survey［J］.ACM SIGKDD Explorations Newsletter，2005，7（2）：3－12.

［5］ 吳亞晶，張 鵬，狄增如，等.二分網(wǎng)絡(luò)研究［J］.復(fù)雜系統(tǒng)與復(fù)雜性科學(xué)，2010，7（1）：1－12.

［6］ Holme P，Liljeros F，Edling C R，et al.Network bipartivity［J］.Physical Review E，2003，68（5）：056107.

［7］ 呂琳媛.復(fù)雜網(wǎng)絡(luò)鏈路預(yù)測［J］.電子科技大學(xué)學(xué)報，2010，39（5）：651－661.

［8］ Allali O，Magnien C，Latapy M.Link prediction in bipartite graphs using internal links and weighted projection［C］／／Computer Communications Workshops （INFOCOM WKSHPS），2011IEEE Conference on，2011：936－941.

［9］ Kunegis J，De Luca E W，Albayrak S.The link prediction problem in bipartite networks［C］／／Computational Intelligence for Knowledge－based Systems Design.Berlin：Springer，2010：380－389.

［10］ Chung F.Spectral graph theory［M］.Providence，Rhode Island：American Mathematical Society，1997.

［11］ Zhou T，Ren J，Medo M，et al.Bipartite network projection and personal recommendation［J］.Physical Review E，2007，76（4）：5－7.

［12］ Zhang Y C，Blattner M，Yu Y K.Heat conduction process on community networks as a recommendation model［J］.Physical Review Letters，2007，99（15）：154301（1－5）.

［13］ Freeman L C.Finding social groups：a meta－analysis of the southern women data［J］.Dynamic Social Network Modeling and Analysis，2003：39－97.