基于聚類系數(shù)的鏈路預(yù)測(cè)算法改進(jìn)

李星+陶漢

摘要： 鏈路預(yù)測(cè)是指通過(guò)已知的網(wǎng)絡(luò)信息來(lái)預(yù)測(cè)網(wǎng)絡(luò)中的丟失邊信息或者是錯(cuò)誤連邊信息，鏈路預(yù)測(cè)是對(duì)于網(wǎng)絡(luò)分析和數(shù)據(jù)挖掘的一項(xiàng)支撐學(xué)科。經(jīng)過(guò)數(shù)十年的學(xué)科發(fā)展，鏈路預(yù)測(cè)得到了長(zhǎng)足的發(fā)展，大量新的預(yù)測(cè)算法得以提出。本文提出了一種基于網(wǎng)絡(luò)節(jié)點(diǎn)中聚類系數(shù)的算法優(yōu)化思路，并將該優(yōu)化思路運(yùn)用到9種經(jīng)典的算法上，在5種真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)表明了該優(yōu)化思路的可行性。鏈路預(yù)測(cè)的準(zhǔn)確性研究多基于丟失邊的預(yù)測(cè)，對(duì)于錯(cuò)誤連邊的準(zhǔn)確性預(yù)測(cè)少有涉及，本文的實(shí)驗(yàn)部分同時(shí)涉及了丟失邊的預(yù)測(cè)以及錯(cuò)誤連邊的預(yù)測(cè)。傳統(tǒng)的鏈路預(yù)測(cè)比較實(shí)驗(yàn)，對(duì)于測(cè)試集多選取10%這一固定值，本文為了說(shuō)明算法的健壯性，針對(duì)不同大小的測(cè)試集進(jìn)行了廣泛的實(shí)驗(yàn)。

關(guān)鍵詞：復(fù)雜網(wǎng)絡(luò)；鏈路預(yù)測(cè)；聚類系數(shù)；錯(cuò)邊識(shí)別；局部相似性

中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2017）01-0239-05

Abstract： Link prediction is a subject which uses the current network information to predict the missing and spurious links， so it is a supporting discipline for network analysis and data mining. After decades of academic development， link prediction has achieve a lot of progress， a large number of algorithms have been proposed. In this paper， we have proposed an optimization thought which was inspired by clustering coefficient. We have applied this optimization methods to nine kinds of classical algorithms， results on five real data sets prove the feasibility of the optimization method. Former study on link prediction mainly focus on the prediction of missing links， while in this paper we have also concern the spurious links. Compared with the traditional research， we have doing experiments on varies ratio of training set， previous training set were fixed at 10% for the most conditions.

Key words： complex networks； link prediction； clustering coefficient； spurious links； local similarity

1 概述

關(guān)于網(wǎng)絡(luò)結(jié)構(gòu)的研究已有數(shù)百年的歷史，網(wǎng)絡(luò)學(xué)科的理論發(fā)展經(jīng)過(guò)了規(guī)則網(wǎng)絡(luò)，隨機(jī)網(wǎng)絡(luò)和復(fù)雜網(wǎng)絡(luò)三個(gè)階段。網(wǎng)絡(luò)上的首項(xiàng)研究可以追溯到1736年歐拉關(guān)于哥尼斯堡七橋問(wèn)題的提出與解決，這屬于規(guī)則網(wǎng)絡(luò)時(shí)代的研究。之后的很長(zhǎng)一段時(shí)間，網(wǎng)絡(luò)學(xué)科都沒(méi)有很大的發(fā)展。1959年，匈牙利的著名數(shù)學(xué)家Erd?s和Rényi建立了著名的隨機(jī)圖（ER）理論，這才將網(wǎng)絡(luò)研究帶入到了第二個(gè)階段[1]。隨機(jī)網(wǎng)絡(luò)的提出將網(wǎng)絡(luò)的理論研究拓展到了更為廣泛的科研領(lǐng)域，比如社會(huì)學(xué)家也可以利用隨機(jī)理論對(duì)于人類關(guān)系網(wǎng)絡(luò)進(jìn)行建模。復(fù)雜網(wǎng)絡(luò)的開啟主要?dú)w功于Watts和Strogatz在1998提出的小世界模型以及Barabási 在1999提出的無(wú)標(biāo)度網(wǎng)絡(luò)[2，3]。小世界網(wǎng)絡(luò)指網(wǎng)絡(luò)中大多數(shù)的節(jié)點(diǎn)不直接相連，但彼此之間只需通過(guò)少量節(jié)點(diǎn)即可以到達(dá)，即“六度分離”理論的詮釋。無(wú)標(biāo)度網(wǎng)絡(luò)指網(wǎng)絡(luò)中節(jié)點(diǎn)度的分布符合冪指數(shù)，即少數(shù)的節(jié)點(diǎn)具有很高的度分布而大多數(shù)節(jié)點(diǎn)的度相對(duì)較低。

近年來(lái)，隨著復(fù)雜網(wǎng)絡(luò)學(xué)科的快速發(fā)展，作為其分支之一的鏈路預(yù)測(cè)研究也得到了越來(lái)越廣泛的關(guān)注。網(wǎng)絡(luò)中的鏈路預(yù)測(cè)是指根據(jù)網(wǎng)絡(luò)現(xiàn)有的節(jié)點(diǎn)屬性以及網(wǎng)絡(luò)拓?fù)涞刃畔?lái)預(yù)測(cè)網(wǎng)絡(luò)中尚未產(chǎn)生連邊的兩個(gè)節(jié)點(diǎn)之間產(chǎn)生鏈接的可能性[4]。鏈路預(yù)測(cè)包含了對(duì)于未知邊的發(fā)掘以及網(wǎng)絡(luò)演化中即將產(chǎn)生的邊的預(yù)測(cè)。鏈路預(yù)測(cè)很好地將網(wǎng)絡(luò)與信息科學(xué)進(jìn)行了連接，可以很好地處理信息科學(xué)中缺失信息的還原與預(yù)測(cè)。

鏈路預(yù)測(cè)具有重要的實(shí)踐以及理論價(jià)值[5，6，7]。人類已知的蛋白質(zhì)相互作用網(wǎng)絡(luò)只占真實(shí)網(wǎng)絡(luò)的冰山一角，很多蛋白質(zhì)之間是否有相互作用需要大量的實(shí)驗(yàn)來(lái)驗(yàn)證。酵母細(xì)菌的相互作用網(wǎng)絡(luò)已被觀察到的只有20%，人類網(wǎng)絡(luò)更是只有0.3%。由于驗(yàn)證蛋白質(zhì)相互網(wǎng)絡(luò)將消耗巨大的人力以及時(shí)間的成本，所以如果能用鏈路預(yù)測(cè)的方式對(duì)可能存在的邊進(jìn)行預(yù)測(cè)，進(jìn)而指導(dǎo)實(shí)驗(yàn)，將對(duì)于人類的生命工程產(chǎn)生巨大的推動(dòng)作用。社交網(wǎng)絡(luò)中也存在信息丟失的情況。比如QQ當(dāng)中，我們好友列表中并不能涵蓋我們?nèi)康暮糜研畔ⅰｆ溌奉A(yù)測(cè)此時(shí)便可以根據(jù)現(xiàn)有好友列表向我們進(jìn)行推薦可能認(rèn)識(shí)的好友，進(jìn)一步完善我們的好友列表 以及增強(qiáng)用戶對(duì)于產(chǎn)品的忠誠(chéng)度。同樣的道理，鏈路預(yù)測(cè)的算法也可以在商品推薦中得以應(yīng)用。鏈路預(yù)測(cè)的理論價(jià)值主要在于幫助我們更好的認(rèn)識(shí)網(wǎng)絡(luò)的演化機(jī)制。針對(duì)某種或某類網(wǎng)絡(luò)，有許多模型都提供了可能的演化機(jī)制，但由于刻畫網(wǎng)絡(luò)性質(zhì)的統(tǒng)計(jì)變量很多，所以很難比較哪種演化機(jī)制更好。有了鏈路預(yù)測(cè)，我們便得到了一個(gè)統(tǒng)一量化的指標(biāo)，利用該演化機(jī)制構(gòu)建鏈路預(yù)測(cè)的算法，算法預(yù)測(cè)準(zhǔn)確率高者更符合網(wǎng)絡(luò)的演化，從而分析哪一個(gè)機(jī)制能夠更好的刻畫網(wǎng)絡(luò)的演化，這大大推進(jìn)了網(wǎng)絡(luò)演化機(jī)制的研究工作。

早期的鏈路預(yù)測(cè)主要基于機(jī)器學(xué)習(xí)和馬爾科夫鏈。該類方法雖然具有較高的預(yù)測(cè)準(zhǔn)確率，但較高的時(shí)間復(fù)雜度限制了被預(yù)測(cè)網(wǎng)絡(luò)的規(guī)模。同時(shí)，由于該類方法的分類往往需要獲取節(jié)點(diǎn)的屬性信息，節(jié)點(diǎn)的屬性信息往往很難獲取即使獲取節(jié)點(diǎn)信息也未必能保證信息的可靠性。比如在社交網(wǎng)絡(luò)之中，用戶的年齡、性別、住址未必會(huì)如實(shí)填寫，這便給該類基于節(jié)點(diǎn)屬性的算法造成了很大的障礙。由于基于馬爾科夫以及機(jī)器學(xué)習(xí)方法的弊端，最近幾年的鏈路預(yù)測(cè)更多轉(zhuǎn)移到了利用網(wǎng)絡(luò)的拓?fù)湫畔⑦M(jìn)行預(yù)測(cè)。利用網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行預(yù)測(cè)的方法主要分為基于相似性的鏈路預(yù)測(cè)和基于似然分析的鏈路預(yù)測(cè)?；谙嗨菩缘逆溌奉A(yù)測(cè)的前提假設(shè)是，如果兩個(gè)點(diǎn)越相似那么這兩個(gè)點(diǎn)存在連邊的可能性越大。相比較基于相似性的鏈路預(yù)測(cè)，基于思然分析的鏈路預(yù)測(cè)是一種更為復(fù)雜的框架，雖然可以取得較高的準(zhǔn)確率，但同基于機(jī)器學(xué)習(xí)的方法類似，當(dāng)網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)目達(dá)到數(shù)千個(gè)之時(shí)，算法處理起來(lái)之時(shí)便會(huì)感到吃力?？紤]到計(jì)算的復(fù)雜度以及通用性，本文所提出的算法可以歸納到基于相似性的鏈路預(yù)測(cè)框架之內(nèi)[8，9，10，11]。

在本文中，我們提出了利用網(wǎng)絡(luò)節(jié)點(diǎn)的聚類系數(shù)這一特征來(lái)提升基于相似性的鏈路預(yù)測(cè)算法的準(zhǔn)確性這一思路。我們將聚類系數(shù)這一特征引入到了9個(gè)經(jīng)典的鏈路預(yù)測(cè)算法之中并得到了9種新的鏈路預(yù)測(cè)算法，對(duì)此我們?cè)?個(gè)真實(shí)的數(shù)據(jù)集之上進(jìn)行了實(shí)驗(yàn)，實(shí)驗(yàn)表明算法中聚類系數(shù)的引入可以在一定程度上提升網(wǎng)絡(luò)的預(yù)測(cè)準(zhǔn)確性。由于過(guò)往鏈路預(yù)測(cè)的研究d多數(shù)只會(huì)進(jìn)行丟失邊的實(shí)驗(yàn)[12，13]，在此基礎(chǔ)上本文還添加了算法對(duì)于錯(cuò)誤邊糾錯(cuò)能力的實(shí)驗(yàn)，實(shí)驗(yàn)表明了我們新的算法在網(wǎng)絡(luò)噪聲糾錯(cuò)能力上的提升。除此之外，過(guò)往研究將測(cè)試集的比例固定在10%這一值之上，我們對(duì)此進(jìn)行了擴(kuò)展，我們將測(cè)試集的比例伸展到了4%到20%范圍之間，進(jìn)一步提升了實(shí)驗(yàn)的完整性，這一范圍的變化也驗(yàn)證了我們算法的健壯性。

2 問(wèn)題描述

定義G（V， E）為一個(gè)無(wú)向網(wǎng)絡(luò)，其中V為節(jié)點(diǎn)集合，E為邊集合。網(wǎng)絡(luò)總的節(jié)點(diǎn)數(shù)為N，邊數(shù)為E。若該網(wǎng)絡(luò)為一個(gè)全連通網(wǎng)絡(luò)，那么該網(wǎng)絡(luò)共有N（N ?1）/ 2條邊，即全集U。給定某個(gè)鏈路預(yù)測(cè)算法，該算法會(huì)對(duì)每對(duì)沒(méi)有連邊的節(jié)點(diǎn)對(duì)（x，y）進(jìn)行評(píng)分，賦予一個(gè)分?jǐn)?shù)值Sxy。將所有未連接的邊進(jìn)行評(píng)分，分?jǐn)?shù)高的邊出現(xiàn)的概率大[14]。

關(guān)于丟失邊和錯(cuò)誤連邊的預(yù)測(cè)稍有不同，下面對(duì)他們進(jìn)行分別描述：

2.1 丟失邊的預(yù)測(cè)

為了預(yù)測(cè)算法的準(zhǔn)確性，一般會(huì)將網(wǎng)絡(luò)中的邊劃分為兩個(gè)部分：訓(xùn)練集ET和測(cè)試集EP。顯然，ETEP=E，且ETEP=?。我們將屬于U但不屬于E的邊稱作不存在的邊。在對(duì)算法進(jìn)行準(zhǔn)確度的測(cè)試時(shí)，我們只會(huì)利用到訓(xùn)練集中的信息，即ET。

2.2 錯(cuò)誤邊的預(yù)測(cè)

為了預(yù)測(cè)算法對(duì)錯(cuò)誤連邊的識(shí)別率，我們將在現(xiàn)有網(wǎng)絡(luò)的基礎(chǔ)上增加一些連邊來(lái)模擬網(wǎng)絡(luò)中包含錯(cuò)誤連邊的情況?，F(xiàn)有網(wǎng)絡(luò)中的邊我們表示為E， 我們向網(wǎng)絡(luò)中添加的不存在的邊為EP，ET=EP+E， 在對(duì)算法進(jìn)行準(zhǔn)確度的測(cè)試時(shí)，我們同樣只會(huì)利用到訓(xùn)練集中的信息，即ET。

3 數(shù)據(jù)集劃分

為了測(cè)試特定鏈路預(yù)測(cè)算法的準(zhǔn)確性，我們需要從網(wǎng)絡(luò)之中選取一部分作為測(cè)試集，剩余部分作為訓(xùn)練集。不同的測(cè)試集的選取方法會(huì)對(duì)實(shí)驗(yàn)結(jié)果造成一定程度上的影響[15]。常見(jiàn)的測(cè)試集的選取方式主要有隨機(jī)抽取、逐項(xiàng)遍歷、k-折疊交叉實(shí)驗(yàn)、滾雪球抽樣、熟識(shí)者抽樣、隨機(jī)游走抽樣、基于路徑抽樣這7種。本文中采取最為常用的隨機(jī)抽樣法。對(duì)于數(shù)據(jù)集的劃分，丟失邊的預(yù)測(cè)和錯(cuò)誤邊的預(yù)測(cè)稍有區(qū)別。

3.1 丟失邊的預(yù)測(cè)

給定的網(wǎng)絡(luò)G中含有N個(gè)節(jié)點(diǎn)E條邊，現(xiàn)給定某一測(cè)試集的選取比例p，我們將等概率的從E條邊中選取p*E（若非整數(shù)，向上取整）條邊構(gòu)成測(cè)試集，E中的剩余邊作為訓(xùn)練集。一般的鏈路預(yù)測(cè)試驗(yàn)中p的選取比例為10%，為了驗(yàn)證本文算法的健壯性，我們將p設(shè)置為 [0.04，0.08，0.12，0.16，0.20] 這五個(gè)不同的值。

3.2 錯(cuò)邊的識(shí)別能力

若網(wǎng)絡(luò)G中含有E條邊，先給定某一測(cè)試集的選取比例，即錯(cuò)誤邊的比例。我們將等概率的從不存在的邊中選取p*E（若非整數(shù)，向上取整）條邊構(gòu)成測(cè)試集EP，ET= E+EP。為了便于比較，我們p的選值范圍與丟失邊的情況相同。

4 經(jīng)典算法

1） CN指標(biāo)（Common Neighbors）[16]。對(duì)于節(jié)點(diǎn)x，Γ（x）表示x的鄰居節(jié)點(diǎn)，同理Γ（y）表示y的鄰居節(jié)點(diǎn)，下式表示的便是x節(jié)點(diǎn)和y節(jié)點(diǎn)的共同鄰居數(shù)。該算法認(rèn)為兩個(gè)節(jié)點(diǎn)擁有越多的共同鄰居數(shù)，越可能相連接。

2） Salton指標(biāo)[17]。kx、ky分別表示節(jié)點(diǎn)x和節(jié)點(diǎn)y度的大小，salton指標(biāo)也被人們稱作余弦相似度指標(biāo)。

3） Jaccard指標(biāo)[18]。該指標(biāo)是Jaccard一百多年前所提出來(lái)的

4） Sorensen指標(biāo)[19]。該指標(biāo)主要用于生態(tài)網(wǎng)絡(luò)系統(tǒng)的預(yù)測(cè)。

5） 大度節(jié)點(diǎn)有利指標(biāo)（hub promoted index， HPI）[20]。根據(jù)式子中的分母部分，我們知道該算法認(rèn)為度較大的節(jié)點(diǎn)更有利于網(wǎng)絡(luò)的連接。

6） 大度節(jié)點(diǎn)不利指標(biāo)（hub depressed index， HDI）[10]。相比較于上式，該算法認(rèn)為度較大的節(jié)點(diǎn)不利于網(wǎng)絡(luò)的連接。

7） LHN指標(biāo)[21]。與Sorensen指標(biāo)類似，僅將分母元素的相加改為相乘。

8） AA指標(biāo)（Adamic-Adar）[22]。這是對(duì)于CN指標(biāo)的一種改進(jìn)，該算法認(rèn)為共同鄰居中，度較小的更利于網(wǎng)絡(luò)的連接。

9） RA指標(biāo)（Resource Allocation）[10]。形式上類似于AA，但該算法是受到網(wǎng)絡(luò)中資源分配模型的啟發(fā)。

5 基于節(jié)點(diǎn)聚類系數(shù)的算法改進(jìn)

5.1 聚類系數(shù)的定義

網(wǎng)絡(luò)中節(jié)點(diǎn)的聚類系數(shù)由Watts和Strogatz在1998年所提出。針對(duì)網(wǎng)絡(luò)中的某一個(gè)節(jié)點(diǎn)vi，其聚類系數(shù)定義為其鄰居間的連邊數(shù)量占可能連邊的比例，數(shù)學(xué)表示為：

其中ki表示節(jié)點(diǎn)vi的度，li表示節(jié)點(diǎn)vi的ki個(gè)鄰居之間的連邊數(shù)量[23]。

聚類系數(shù)表示了節(jié)點(diǎn)鄰居之間的連接緊密程度。在生活中，若將人類的生活抽象為社交網(wǎng)絡(luò)，若某人的聚類系數(shù)較大，那么該人的朋友之間相互認(rèn)識(shí)的可能性越大，那么我們認(rèn)為該人的好友之間產(chǎn)生連邊的概率較大。基于大的聚類系數(shù)促進(jìn)網(wǎng)絡(luò)的連接，所以本文認(rèn)為可將聚類系數(shù)這一特征融入到現(xiàn)有算法之中，提升算法對(duì)于部分網(wǎng)絡(luò)的預(yù)測(cè)準(zhǔn)確度。

5.2 算法改進(jìn)

對(duì)于以上提到的9種鏈路預(yù)測(cè)算法，加入節(jié)點(diǎn)的聚類系數(shù)這一特性之后，得到的改進(jìn)算法如下所示：

6 實(shí)驗(yàn)分析

本章的實(shí)驗(yàn)部分，我們重點(diǎn)比較了9種經(jīng)典的鏈路預(yù)測(cè)算法與我們改進(jìn)后的9種算法，在5類真實(shí)的數(shù)據(jù)集之上我們不僅比較了丟失邊預(yù)測(cè)的準(zhǔn)確性同時(shí)比較了錯(cuò)誤邊的恢復(fù)效果。本章將對(duì)數(shù)據(jù)集，評(píng)價(jià)指教，實(shí)驗(yàn)結(jié)果三方面進(jìn)行介紹。

6.1 實(shí)驗(yàn)數(shù)據(jù)

6.1.1 數(shù)據(jù)說(shuō)明

本文實(shí)驗(yàn)中的數(shù)據(jù)是在pajek和stanford兩個(gè)數(shù)據(jù)集當(dāng)中收集而來(lái)。USAir表示的是美國(guó)的航線信息，節(jié)點(diǎn)表示機(jī)場(chǎng)，若兩個(gè)機(jī)場(chǎng)之間有直達(dá)航線，那么該兩點(diǎn)之間存在一條連接邊。Elegans表示的是線蟲的神經(jīng)網(wǎng)絡(luò)，節(jié)點(diǎn)表示線蟲的神經(jīng)元，突觸或間隙表示為連邊。Footbal數(shù)據(jù)中的節(jié)點(diǎn)代表國(guó)家隊(duì)，這些國(guó)家中的球員頻繁參加國(guó)外聯(lián)賽，若國(guó)家隊(duì)中有成員在另外一個(gè)國(guó)家的聯(lián)賽中踢球，那么這兩個(gè)國(guó)家隊(duì)之間存在連邊信息。Jazz表示jazz演奏家之間的合作網(wǎng)絡(luò)。Karate是社會(huì)網(wǎng)絡(luò)分析領(lǐng)域中的經(jīng)典數(shù)據(jù)集，該網(wǎng)絡(luò)構(gòu)造了美國(guó)一所大學(xué)空手道俱樂(lè)部中34名成員的社會(huì)關(guān)系，若兩人在現(xiàn)實(shí)之中是好友關(guān)系，那么該兩人之間存在一條連邊。

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

|V|代表網(wǎng)絡(luò)中節(jié)點(diǎn)的數(shù)目。|E|代表網(wǎng)絡(luò)中邊的數(shù)目。D表示網(wǎng)絡(luò)的密度，計(jì)算公式為。C表示節(jié)點(diǎn)的聚類系數(shù)，上文已經(jīng)給出了計(jì)算公式。表示網(wǎng)絡(luò)中節(jié)點(diǎn)度的平均值。表示網(wǎng)絡(luò)的平均最短距離，該值需要計(jì)算所有節(jié)點(diǎn)對(duì)之間的最短距離再求平均。H表示網(wǎng)絡(luò)節(jié)點(diǎn)度之間的異質(zhì)性，若節(jié)點(diǎn)的度分布越不平均，該值則越大。計(jì)算公式為 ，分母部分先求所有節(jié)點(diǎn)度的平均值再平方，分子部分是先求各個(gè)節(jié)點(diǎn)度的平方再求平均值。

6.2 評(píng)價(jià)指標(biāo)

常見(jiàn)的鏈路預(yù)測(cè)算法的衡量指標(biāo)有AUC（area under the receiver operating characteristic curve），Precision和Ranking Score三種。Precision考慮的是排在前K位的預(yù)測(cè)是否準(zhǔn)確，Ranking Score側(cè)重于所預(yù)測(cè)邊的排序，AUC是三種當(dāng)中最為常用的一種指標(biāo)，他可以很好的從整體上衡量算法的準(zhǔn)確度。

在丟失邊的預(yù)測(cè)之中，每次從測(cè)試集和不存在的邊當(dāng)中分別取出一條邊，鏈路預(yù)測(cè)算法根據(jù)訓(xùn)練集信息分別對(duì)兩條邊進(jìn)行評(píng)分，如果測(cè)試集中邊的評(píng)分大于不存在的邊，那么加1，如果測(cè)試集中邊的評(píng)分等于不存在的邊，那么加0.5，如果測(cè)試集中邊的評(píng)分大于不存在的邊，那么加0。如此往復(fù)比較n次，若測(cè)試集中的邊分值大于不存在的邊的次數(shù)為n'，測(cè)試集中的邊分值等于不存在的邊的次數(shù)為n''。

在錯(cuò)誤邊的預(yù)測(cè)中，每次從E和EP當(dāng)中分別取出一條邊，如果E中邊的評(píng)分大于EP中的評(píng)分，那么加1，如果相等加0.5，否則加0。如此往復(fù)比較n次，若E中的邊分值大于EP邊的次數(shù)為n'，等于的次數(shù)為n''。

根據(jù)先前的劃分，網(wǎng)絡(luò)中的未知邊分為不存在的邊和測(cè)試集當(dāng)中的邊。雖然測(cè)試集中的邊被劃分在了未知邊中，但好的算法是應(yīng)該可以區(qū)分出不存在的邊和測(cè)試集當(dāng)中的邊的，即根據(jù)算法測(cè)試集中邊出現(xiàn)的概率要高于不存在的邊。現(xiàn)，那么AUC值的計(jì)算公式為：

顯然，如果鏈路預(yù)測(cè)的算法不具備預(yù)測(cè)能力， AUC=0.5。因此AUC大于0.5的程度衡量了算法在多大程度上比隨機(jī)預(yù)測(cè)的方法精確。

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

為了保證試驗(yàn)的準(zhǔn)確定，當(dāng)我們確定某一個(gè)p值之后，我們會(huì)對(duì)測(cè)試集進(jìn)行100次劃分，劃分之間彼此不關(guān)聯(lián)，這主要是防止測(cè)試集的隨機(jī)性對(duì)試驗(yàn)結(jié)果造成的誤差。測(cè)試集劃分好之后，我們將內(nèi)層循環(huán)次數(shù)確定為1000次，也就是說(shuō)總循環(huán)比較的次數(shù)為100000次，該次數(shù)對(duì)應(yīng)于上述AUC指標(biāo)中的n。

以下便是實(shí)驗(yàn)的結(jié)果：

1） Elegans網(wǎng)絡(luò)中缺失邊的發(fā)現(xiàn)與錯(cuò)誤邊的糾正，左側(cè)為缺失邊的發(fā)現(xiàn)，右側(cè)為錯(cuò)誤邊的糾正。下圖中共18種算法進(jìn)行比較，其中原算法9種，加入聚類系數(shù)改進(jìn)后的算法9種。為了便于比較，我們將某一算法和改進(jìn)后的算法一一對(duì)應(yīng)，這主要體現(xiàn)在繪圖時(shí)線段的顏色，如下圖所示CN和加入聚類系數(shù)后的CCN算法均由黑色線段表示，RA和CRA均由紅色表示。此外，原算法用虛線表示，改進(jìn)后的算法用實(shí)線表示。結(jié)果圖的橫坐標(biāo)表示所選取的訓(xùn)練集的比例p，縱坐標(biāo)表示算法的預(yù)測(cè)準(zhǔn)確度。

從Elegans的實(shí)驗(yàn)結(jié)果圖可以看出改進(jìn)后的算法相比較原算法在準(zhǔn)確率上有所提升，該效果的提升不僅在于發(fā)現(xiàn)丟失邊的情況同時(shí)適用于錯(cuò)誤連邊的糾正。隨著測(cè)試集比例的提升，改進(jìn)后的方法同樣優(yōu)于原算法。

2） Football網(wǎng)絡(luò)的實(shí)驗(yàn)結(jié)果如下圖所示。實(shí)驗(yàn)結(jié)果表明改進(jìn)后的算法在整體上明顯優(yōu)于原先的算法，此外在鏈路預(yù)測(cè)的過(guò)程中我們發(fā)現(xiàn)當(dāng)p=0.08時(shí)，預(yù)測(cè)的準(zhǔn)確率達(dá)到最高值。

3） Jazz網(wǎng)絡(luò)的實(shí)驗(yàn)結(jié)果如下圖所示。改進(jìn)后的算法只在少數(shù)幾個(gè)點(diǎn)之上不能超越原算法，整體表現(xiàn)仍然十分優(yōu)異。

4） USAir網(wǎng)絡(luò)的實(shí)驗(yàn)結(jié)果如下圖所示。該實(shí)驗(yàn)結(jié)果分層現(xiàn)象十分明顯，改進(jìn)后的算法曲線明顯在改進(jìn)前算法的曲線之上，這表明加入聚類系數(shù)這一節(jié)點(diǎn)的局部信息之后，該

9種算法在美國(guó)航空網(wǎng)絡(luò)的預(yù)測(cè)上效果明顯提升。

5） Karate網(wǎng)絡(luò)的實(shí)驗(yàn)結(jié)果如下圖所示。與上述四種網(wǎng)絡(luò)結(jié)果共同驗(yàn)證了算法改進(jìn)的有效性，此外我們發(fā)現(xiàn)這些鏈路預(yù)測(cè)算法對(duì)錯(cuò)誤連邊的發(fā)現(xiàn)要略優(yōu)于預(yù)測(cè)不存在的邊。

7 總結(jié)與展望

聚類系數(shù)表示節(jié)點(diǎn)鄰居之間聯(lián)系的緊密程度，較高的聚類系數(shù)表明鄰居間較高的連接概率。受該指標(biāo)的影響，我們將其特性添加到現(xiàn)有的9種鏈路預(yù)測(cè)算法之中得到了我們改進(jìn)后的9種算法。通過(guò)在5種真實(shí)網(wǎng)絡(luò)上的實(shí)驗(yàn)，我們發(fā)現(xiàn)了改進(jìn)后的算法在這5種網(wǎng)絡(luò)上有著更好的表現(xiàn)。除此之外，針對(duì)不同大小的訓(xùn)練集劃分比例，我們進(jìn)行了大量的比較實(shí)驗(yàn)，過(guò)往研究很少會(huì)探討訓(xùn)練集p的大小對(duì)于實(shí)驗(yàn)結(jié)果的影響。我們發(fā)現(xiàn)不同大小的訓(xùn)練集對(duì)于實(shí)驗(yàn)結(jié)果會(huì)產(chǎn)生影響，但改進(jìn)后的算法與原算法的相對(duì)大小不變。最后，我們的鏈路預(yù)測(cè)實(shí)驗(yàn)還包含了算法在錯(cuò)誤連邊上的發(fā)掘能力，實(shí)驗(yàn)表明，若我們有算法A、B，算法A相比B在丟失邊的發(fā)掘能力上可能會(huì)更好，但若換做是錯(cuò)誤邊的發(fā)現(xiàn)，那么B算法可能會(huì)優(yōu)于A算法。

本研究只簡(jiǎn)單地考慮了節(jié)點(diǎn)的聚類系數(shù)對(duì)于鏈路預(yù)測(cè)算法的影響，除此之外，在未來(lái)的研究當(dāng)中我們可將更多的網(wǎng)絡(luò)特征融入到算法之中來(lái)進(jìn)行算法的提升。本次實(shí)驗(yàn)的網(wǎng)絡(luò)只有5種，更多數(shù)據(jù)的實(shí)驗(yàn)有待補(bǔ)充，我們不排除特定網(wǎng)絡(luò)之上，改進(jìn)后算法的準(zhǔn)確率不如原算法。本次實(shí)驗(yàn)網(wǎng)絡(luò)的節(jié)點(diǎn)只有幾百個(gè)，更大規(guī)模網(wǎng)絡(luò)的鏈路預(yù)測(cè)研究有待進(jìn)一步深入。

參考文獻(xiàn)：

[1] Erd?s P， Rényi A. On Random Graphs[J]. Publicationes Mathematicae， 1959， 6：290-291.

[2] Watts D J， Strogatz S H. Collective dynamics of ‘small-worldnetworks[J]. nature， 1998， 393（6684）： 440-442.

[3] Barabási A L， Albert R. Emergence of scaling in random networks[J]. science， 1999， 286（5439）： 509-512.

[4] Lü L， Zhou T. Link prediction in complex networks： A survey[J]. Physica A： Statistical Mechanics and its Applications， 2011， 390（6）： 1150-1170.

[5] Gao F， Musial K， Cooper C， et al. Link prediction methods and their accuracy for different social networks and network metrics[J]. Scientific Programming， 2015， 2015： 1.

[6] Li D， Zhang Y， Xu Z， et al. Exploiting Information Diffusion Feature for Link Prediction in Sina Weibo[J]. Scientific reports， 2016， 6.

[7] 劉宏鯤， 呂琳媛， 周濤. 利用鏈路預(yù)測(cè)推斷網(wǎng)絡(luò)演化機(jī)制[J]. 中國(guó)科學(xué)： 物理學(xué) 力學(xué) 天文學(xué)， 2011， 41（7）： 81.

[8] Lü L， Pan L， Zhou T， et al. Toward link predictability of complex networks[J]. Proceedings of the National Academy of Sciences， 2015， 112（8）： 2325-2330.

[9] Chen B， Chen L. A link prediction algorithm based on ant colony optimization[J]. Applied Intelligence， 2014， 41（3）： 694-708.

[10] Zhou T， Lü L， Zhang Y C. Predicting missing links via local information[J]. The European Physical Journal B， 2009， 71（4）： 623-630.

[11] Liu Z， Dong W， Fu Y. Local degree blocking model for link prediction in complex networks[J]. Chaos： An Interdisciplinary Journal of Nonlinear Science， 2015， 25（1）： 013115.

[12] Guimerà R， Sales-Pardo M. Missing and spurious interactions and the reconstruction of complex networks[J]. Proceedings of the National Academy of Sciences， 2009， 106（52）： 22073-22078.

[13] Zhang P， Wang X， Wang F， et al. Measuring the robustness of link prediction algorithms under noisy environment[J]. Scientific reports， 2016， 6.

[14] 呂琳媛. 復(fù)雜網(wǎng)絡(luò)鏈路預(yù)測(cè)[J]. 電子科技大學(xué)學(xué)報(bào)， 2010， 39（5）： 651-661.

[15] Zhu Y X， Lü L， Zhang Q M， et al. Uncovering missing links with cold ends[J]. Physica A： Statistical Mechanics and its Applications， 2012， 391（22）： 5769-5778.

[16] Lorrain F， White H C. Structural equivalence of individuals in social networks[J]. The Journal of mathematical sociology， 1971， 1（1）： 49-80.

[17] Salton G， McGill M J. Introduction to modern information retrieval[J]. 1986.

[18] Jaccard P. Etude comparative de la distribution florale dans une portion des Alpes et du Jura[M]. Impr. Corbaz， 1901.

[19] Sorensen T. {A method of establishing groups of equal amplitude in plant sociology based on similarity of species and its application to analyses of the vegetation on Danish commons}[J]. Biol. Skr.， 1948（5）： 1-34.

[20] Ravasz E， Somera A L， Mongru D A， et al. Hierarchical organization of modularity in metabolic networks[J]. science， 2002， 297（5586）： 1551-1555.

[21] Leicht E A， Holme P， Newman M E J. Vertex similarity in networks[J]. Physical Review E， 2006， 73（2）： 026120.

[22] Adamic L A， Adar E. Friends and neighbors on the web[J]. Social networks， 2003， 25（3）： 211-230.

[23] 李建， 鄭曉艷. 復(fù)雜網(wǎng)絡(luò)聚類算法綜述[J]. 電腦知識(shí)與技術(shù)， 2015（5）： 019.