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

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

0 引 言

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

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

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

1 相關(guān)工作

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

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

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

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

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

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

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

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

2.1 基本定義

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

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

圖2 二部圖G

圖3 二部圖投影圖

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

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

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

2.2 ILPExt算法描述

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

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

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

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

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

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

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

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

3 實(shí)驗(yàn)結(jié)果及分析

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

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

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

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

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

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

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

表2 Southern Women Data實(shí)驗(yàn)詳細(xì)結(jié)果

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

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

表4 Facebook－like Forum Network數(shù)據(jù)集實(shí)驗(yàn)詳細(xì)結(jié)果

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

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

4 結(jié)束語(yǔ)

在ILP算法中，只采用了底部節(jié)點(diǎn)投影，找出最有可能產(chǎn)生邊的節(jié)點(diǎn)對(duì)，因此丟失了頂部節(jié)點(diǎn)所包含的信息。本文針對(duì)ILP算法的這一不足，提出改進(jìn)的ILPExt算法，將底部節(jié)點(diǎn)和頂部節(jié)點(diǎn)都投影，投影后將2個(gè)部分的內(nèi)部鏈邊集合合并，然后產(chǎn)生出預(yù)測(cè)邊集。實(shí)驗(yàn)證明能夠找出更多可預(yù)測(cè)的邊，而且召回率甚至是原算法的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ù)測(cè)［J］.電子科技大學(xué)學(xué)報(bào)，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.