高 楊，張燕平，錢付蘭，趙 姝

安徽大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，合肥 230601

基于三元閉包的節(jié)點(diǎn)相似性鏈路預(yù)測算法*

高 楊，張燕平，錢付蘭+，趙 姝

安徽大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，合肥 230601

復(fù)雜網(wǎng)絡(luò)；鏈路預(yù)測；三元閉包；節(jié)點(diǎn)權(quán)重

1 引言

很多復(fù)雜系統(tǒng)都可以用網(wǎng)絡(luò)的形式來描述，節(jié)點(diǎn)可以表示一個(gè)人、一座城市或者一個(gè)機(jī)構(gòu)等，邊可以表示節(jié)點(diǎn)之間的聯(lián)系、關(guān)系或相互作用等。復(fù)雜網(wǎng)絡(luò)涉及的領(lǐng)域非常廣泛，在社會、技術(shù)、生物等領(lǐng)域都有關(guān)于復(fù)雜網(wǎng)絡(luò)的研究。復(fù)雜網(wǎng)絡(luò)研究對探索網(wǎng)絡(luò)生成機(jī)制具有重要的意義。

鏈路預(yù)測作為復(fù)雜網(wǎng)絡(luò)的重要研究方向越來越受到研究者們的關(guān)注。網(wǎng)絡(luò)中的鏈路預(yù)測是指如何通過已知的網(wǎng)絡(luò)節(jié)點(diǎn)和網(wǎng)絡(luò)結(jié)構(gòu)等信息，預(yù)測網(wǎng)絡(luò)中尚未連接的兩個(gè)節(jié)點(diǎn)之間產(chǎn)生鏈接的可能性[1-3]。這種預(yù)測既包含對未知鏈接的預(yù)測，也包含對未來鏈接的預(yù)測。

鏈路預(yù)測問題因其重大的實(shí)際應(yīng)用價(jià)值，受到不同領(lǐng)域不同背景的科學(xué)家的廣泛關(guān)注。在生物領(lǐng)域研究中，例如蛋白質(zhì)相互作用網(wǎng)絡(luò)和新陳代謝網(wǎng)絡(luò)，利用鏈路預(yù)測技術(shù)，可以指導(dǎo)其實(shí)驗(yàn)，降低實(shí)驗(yàn)成本，提高實(shí)驗(yàn)的成功率。在社會網(wǎng)絡(luò)分析中遇到數(shù)據(jù)不全的情況時(shí)，鏈路預(yù)測同樣可以作為準(zhǔn)確分析社會網(wǎng)絡(luò)結(jié)構(gòu)的有力輔助工具[4-5]。鏈路預(yù)測技術(shù)可以應(yīng)用于將實(shí)體及其之間關(guān)系抽象為網(wǎng)絡(luò)的系統(tǒng)中，如在線社交網(wǎng)絡(luò)、電子商務(wù)網(wǎng)站等，從而產(chǎn)生可觀的商業(yè)價(jià)值。在不斷發(fā)展的社交網(wǎng)絡(luò)中，鏈路預(yù)測根據(jù)現(xiàn)有的網(wǎng)絡(luò)結(jié)構(gòu)來預(yù)測哪些尚未結(jié)交的用戶“應(yīng)該是朋友”，并將結(jié)果作為“朋友推薦”發(fā)給用戶，可以提高相關(guān)網(wǎng)絡(luò)在用戶心目中的地位，從而提高用戶對該網(wǎng)站的忠誠度。

本文組織結(jié)構(gòu)如下：第1章介紹鏈路預(yù)測的研究目的與意義；第2章討論相關(guān)工作；第3章介紹本文提出的鏈路預(yù)測算法；第4章給出實(shí)驗(yàn)結(jié)果并進(jìn)行算法效率分析；第5章是結(jié)束語，總結(jié)本文工作以及對下一步研究進(jìn)行展望。

2 相關(guān)工作

網(wǎng)絡(luò)中的鏈路預(yù)測，既包含對未知鏈路的預(yù)測，也包括對未來鏈路的預(yù)測?；诠?jié)點(diǎn)相似性的鏈路預(yù)測方法分為3類[6]：基于網(wǎng)絡(luò)局部結(jié)構(gòu)的預(yù)測方法，基于網(wǎng)絡(luò)全局結(jié)構(gòu)的預(yù)測方法，基于準(zhǔn)局部結(jié)構(gòu)的預(yù)測方法。本文主要關(guān)注基于網(wǎng)絡(luò)局部結(jié)構(gòu)的研究。鏈路預(yù)測本質(zhì)上是對網(wǎng)絡(luò)演化規(guī)律的猜測。在鏈路預(yù)測的一些方法中體現(xiàn)出網(wǎng)絡(luò)中三元閉包機(jī)制的原理。例如，共同鄰居（common neighbor，CN）算法[7]，利用共同鄰居節(jié)點(diǎn)數(shù)定義節(jié)點(diǎn)之間的相似性。其思想是兩個(gè)節(jié)點(diǎn)如果有越多的共同鄰居節(jié)點(diǎn)，那么這兩個(gè)節(jié)點(diǎn)越相似，就越可能形成鏈接。Adamic等人[8]在共同鄰居的基礎(chǔ)上考慮節(jié)點(diǎn)的度，根據(jù)共同鄰居節(jié)點(diǎn)的度為每個(gè)節(jié)點(diǎn)賦予一個(gè)權(quán)重值，提出AA（Adamic-Adar）算法。Zhou等人[9]受網(wǎng)絡(luò)資源分配過程的啟發(fā)提出了資源分配指標(biāo)（resource allocation，RA）算法，與AA算法有異曲同工之效。近年來，在共同鄰居的基礎(chǔ)上結(jié)合網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)信息的鏈路預(yù)測算法有很多。Gupta等人[10]認(rèn)為只利用共同鄰居節(jié)點(diǎn)的信息是不夠的，在此基礎(chǔ)上考慮非共同鄰居節(jié)點(diǎn)之間的連接緊密程度，提出了一種新的鏈路預(yù)測算法，獲得較好的預(yù)測效果。Yin等人[11]認(rèn)為每個(gè)共同鄰居節(jié)點(diǎn)對鏈接的影響是不同的，定義共同鄰居節(jié)點(diǎn)連接強(qiáng)度的概念，提出了NLSA（node link strength algorithm）預(yù)測算法，并且在真實(shí)的社交網(wǎng)絡(luò)中取得了較好預(yù)測效果。Zhang等人[12]在考慮兩步路徑上的節(jié)點(diǎn)對鏈接產(chǎn)生貢獻(xiàn)的同時(shí)又考慮了三步路徑上節(jié)點(diǎn)的貢獻(xiàn)，提出了CCN（cohesive common neighbors）算法，并且取得了較高的預(yù)測精確度。利用三元閉包機(jī)制結(jié)合網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)信息可以提高鏈路預(yù)測算法的預(yù)測效果。

三元閉包（triadic closure）[13]作為網(wǎng)絡(luò)最基本的局部結(jié)構(gòu)和重要的鏈接生成機(jī)制，在網(wǎng)絡(luò)模型的研究中不斷被提到，對探索網(wǎng)絡(luò)演化機(jī)制具有重要的作用。其作為網(wǎng)絡(luò)中的最小局部結(jié)構(gòu)，具有結(jié)構(gòu)平衡和穩(wěn)定的特征。三元閉包的形成機(jī)理在不同的網(wǎng)絡(luò)中有著不同的解釋。在朋友網(wǎng)絡(luò)中表現(xiàn)為：A和B是朋友，B和C也是朋友，那么A和C很可能也是朋友。在微博中關(guān)注關(guān)系網(wǎng)絡(luò)中表現(xiàn)為：關(guān)注用戶v的用戶u同時(shí)關(guān)注了很多v的朋友，那么u很可能去關(guān)注用戶v關(guān)注的用戶。文獻(xiàn)[14]在Twitter上的朋友推薦系統(tǒng)的研究中，根據(jù)三元閉包的形成機(jī)理，利用HITS算法與根據(jù)該機(jī)理計(jì)算得到的用戶間的相似性值來產(chǎn)生最后的推薦結(jié)果，并獲得了不錯(cuò)的效果。文獻(xiàn)[15]提到三元閉包的形成過程是多種網(wǎng)絡(luò)中新鏈接生成的一個(gè)非常重要的機(jī)制，并在引文網(wǎng)絡(luò)中證明了該機(jī)制是引文鏈接產(chǎn)生的重要力量。文獻(xiàn)[16]提出一種基于三元閉包機(jī)制的網(wǎng)絡(luò)生長模型，利用該模型產(chǎn)生帶有肥尾分布、高聚類系數(shù)和強(qiáng)社團(tuán)結(jié)構(gòu)特征屬性的網(wǎng)絡(luò)系統(tǒng)，體現(xiàn)出三元閉包在網(wǎng)絡(luò)演化中的重要作用。文獻(xiàn)[17]根據(jù)三元閉包定義聚類系數(shù)的思想，在雙模網(wǎng)絡(luò)中重新定義了聚類系數(shù)的計(jì)算方法，體現(xiàn)出三元閉包在不同網(wǎng)絡(luò)中的應(yīng)用。文獻(xiàn)[18]根據(jù)三元閉包和隨機(jī)鏈接兩種機(jī)制，提出了一種社交網(wǎng)絡(luò)增長模型，并應(yīng)用到兩種社交網(wǎng)絡(luò)中，證明了該模型能夠重建網(wǎng)絡(luò)的主要拓?fù)浣Y(jié)構(gòu)。另外文獻(xiàn)[19]研究在動(dòng)態(tài)網(wǎng)絡(luò)中三元閉包是如何形成的，提到三元閉包預(yù)測問題與鏈路預(yù)測是相關(guān)的，不同之處是它只專注于預(yù)測三元閉包中的鏈路問題。

本文根據(jù)三元閉包結(jié)構(gòu)提出了一種加節(jié)點(diǎn)權(quán)重的鏈路預(yù)測算法，根據(jù)三元閉包結(jié)構(gòu)的數(shù)目計(jì)算節(jié)點(diǎn)的權(quán)重。首先統(tǒng)計(jì)網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)擁有的三元閉包結(jié)構(gòu)的數(shù)目，根據(jù)該數(shù)目對每個(gè)節(jié)點(diǎn)排序，得到每個(gè)節(jié)點(diǎn)的序值，再將序值映射到區(qū)間[0,1]內(nèi)，由此求得每個(gè)節(jié)點(diǎn)的權(quán)重。將其應(yīng)用到節(jié)點(diǎn)相似性指標(biāo)中得到計(jì)算相似性的方法。采用CN算法、AA算法和RA算法作為最基本的對比算法。與文獻(xiàn)[20]和文獻(xiàn)[21]中提出的在有權(quán)網(wǎng)絡(luò)中的鏈路預(yù)測算法進(jìn)行比較，在10個(gè)真實(shí)網(wǎng)絡(luò)中實(shí)驗(yàn)結(jié)果表明，本文算法能夠提高鏈路預(yù)測的精確度。分析實(shí)驗(yàn)結(jié)果，發(fā)現(xiàn)了一個(gè)很有趣的現(xiàn)象：在社交網(wǎng)絡(luò)中，擁有較多三元閉包結(jié)構(gòu)的用戶，不傾向于建立更多的新鏈接；相反，擁有較少三元閉包結(jié)構(gòu)的用戶，傾向于建立更多的新鏈接。這種現(xiàn)象也符合社會學(xué)中有關(guān)弱關(guān)系產(chǎn)生鏈接的現(xiàn)象。

3 算法描述

3.1 鏈路預(yù)測問題描述

定義一個(gè)無向網(wǎng)絡(luò)G(V，E)，其中V表示節(jié)點(diǎn)集合，E表示邊的集合。網(wǎng)絡(luò)總的節(jié)點(diǎn)數(shù)是N，總的邊數(shù)是M。令U為N×(N-1)/2個(gè)節(jié)點(diǎn)對組成的全集。給定一種鏈路預(yù)測方法，為每對沒有連邊的節(jié)點(diǎn)對(x,y)賦予一個(gè)分?jǐn)?shù)值。這個(gè)分?jǐn)?shù)值可以理解為一種接近性，它與兩節(jié)點(diǎn)的鏈接概率正相關(guān)。將所有未連接的節(jié)點(diǎn)對按照該分?jǐn)?shù)值從大到小排序，排在最前面的節(jié)點(diǎn)對相互連接的概率最大。

3.2 基本算法介紹

定義Γ(x)表示節(jié)點(diǎn)x的鄰居節(jié)點(diǎn)集合，CN、AA、RA算法的計(jì)算節(jié)點(diǎn)相似性指標(biāo)的定義如下。

（1）CN指標(biāo)：其思想是兩個(gè)節(jié)點(diǎn)如果有很多的共同鄰居節(jié)點(diǎn)，那么這兩個(gè)節(jié)點(diǎn)相似。

（2）AA指標(biāo)：其思想是度小的共同鄰居節(jié)點(diǎn)的貢獻(xiàn)大于度大的共同鄰居節(jié)點(diǎn)，根據(jù)共同鄰居節(jié)點(diǎn)的度為每個(gè)節(jié)點(diǎn)賦予一個(gè)權(quán)重值。

（3）RA指標(biāo)：其思想是每個(gè)媒介都有一個(gè)單位的資源并且將平均分配傳給它的鄰居，則節(jié)點(diǎn)可以接收到的資源數(shù)就定義為節(jié)點(diǎn)x和y的相似性。

其中，kz表示節(jié)點(diǎn)z的度。

3.3 基于三元閉包的鏈路預(yù)測算法

三元閉包作為網(wǎng)絡(luò)最基本的局部結(jié)構(gòu)和重要的鏈接生成機(jī)制，對網(wǎng)絡(luò)衍化有著重要的作用。作為網(wǎng)絡(luò)中的最小局部結(jié)構(gòu)，具有結(jié)構(gòu)平衡和穩(wěn)定的特征?？梢詫⑵鋺?yīng)用到鏈路預(yù)測當(dāng)中，探索其對網(wǎng)絡(luò)衍化的影響。用一個(gè)三元組表示一個(gè)三元閉包，即(A，B，C)，其表示在網(wǎng)絡(luò)中的結(jié)構(gòu)是節(jié)點(diǎn)A與節(jié)點(diǎn)B和C都有連邊，且節(jié)點(diǎn)B和C之間也有連邊。統(tǒng)計(jì)整個(gè)網(wǎng)絡(luò)中的三元閉包數(shù)目，根據(jù)這些存在的三元閉包統(tǒng)計(jì)出每個(gè)節(jié)點(diǎn)所擁有的三元閉包的數(shù)目。在網(wǎng)絡(luò)中，節(jié)點(diǎn)擁有的三元閉包越多，它的聚類系數(shù)可能越大，它的“朋友圈”就越緊密，該節(jié)點(diǎn)就越重要。為了量化這種重要性，采用如下的做法：統(tǒng)計(jì)網(wǎng)絡(luò)中節(jié)點(diǎn)i擁有的三元閉包數(shù)目nΔi，對nΔi進(jìn)行排序，nΔi越大，序值x越小，節(jié)點(diǎn)就越重要。根據(jù)函數(shù) f(x)= 1/(1+lg x)，將序值映射到[0,1]之間，得到最終的節(jié)點(diǎn)權(quán)重wi。一個(gè)簡單的例子如圖1所示。在該網(wǎng)絡(luò)中，三元閉包結(jié)構(gòu)中的邊用粗黑線表示，非三元閉包結(jié)構(gòu)中的關(guān)系用細(xì)黑線表示，該簡單網(wǎng)絡(luò)中的三元閉包結(jié)構(gòu)有(1,2,9)、(1,2,7)、(1,7,9)、(2,3,9)、(2,7,9)、(4, 5,7)。節(jié)點(diǎn)權(quán)重的計(jì)算結(jié)果如表1所示。

Fig.1 Asimple network圖1 一個(gè)簡單網(wǎng)絡(luò)

Table 1 Node weight表1 節(jié)點(diǎn)權(quán)重

基于三元閉包的節(jié)點(diǎn)相似性鏈路預(yù)測算法，其計(jì)算相似性的方法是將所求的節(jié)點(diǎn)權(quán)重應(yīng)用到CN指標(biāo)、AA指標(biāo)和RA指標(biāo)中，分別得到加節(jié)點(diǎn)權(quán)重的共同鄰居指標(biāo)TWCN，加節(jié)點(diǎn)權(quán)重的Adamic-Adar指標(biāo)TWAA，加節(jié)點(diǎn)權(quán)重的資源分配指標(biāo)TWRA。其計(jì)算公式如下所示：

為了進(jìn)一步研究三元閉包結(jié)構(gòu)在鏈路預(yù)測中的作用，將式（4）、（5）和（6）節(jié)點(diǎn)相似性指標(biāo)進(jìn)行改進(jìn)，加入權(quán)重調(diào)節(jié)參數(shù)α來調(diào)節(jié)權(quán)重的大小。其計(jì)算公式如下所示：

將根據(jù)三元閉包計(jì)算節(jié)點(diǎn)權(quán)重的算法命名為CNWTC（calc node weight based triadic closure）算法。將基于節(jié)點(diǎn)權(quán)重的鏈路預(yù)測算法命名為PWNW（prediction with node weight）算法。將帶調(diào)節(jié)參數(shù)α的鏈路預(yù)測算法命名為PWNW_α（prediction with node weight_α）算法。

算法1 CNWTC算法

算法2 PWNW算法

算法3 PWNW_α算法

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

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

鏈路預(yù)測評價(jià)指標(biāo)有AUC（area under the receiver operating characteristic curve）[22]和精確度[23]precision）。

AUC可以理解為在測試集中的邊的分?jǐn)?shù)值有比隨機(jī)選擇的一條不存在的邊的分?jǐn)?shù)值高的概率。獨(dú)立比較n次，如果有n′次測試集中的邊的分?jǐn)?shù)值大于不存在的邊的分?jǐn)?shù)值，有n″次兩分?jǐn)?shù)值相等，其計(jì)算公式如下所示：

precision定義為在前L個(gè)預(yù)測邊中被預(yù)測準(zhǔn)確的比例。如果有m個(gè)預(yù)測準(zhǔn)確，即排在前L的邊中有m個(gè)在測試集中，則precision定義為：

本文采用的評價(jià)指標(biāo)是precision，排序列表L的長度為100。

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

本文采用10個(gè)真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集，分別是以復(fù)雜網(wǎng)絡(luò)為主題發(fā)表過論文的科學(xué)家合作網(wǎng)絡(luò)[24]Net-Science）、計(jì)算幾何領(lǐng)域的科學(xué)家合作網(wǎng)絡(luò)（CGScience，http://vlado.fmf.uni-lj.si/pub/networks/data/）、爵士音樂家合作網(wǎng)絡(luò)[25]Jazz）、Facebook（http://snap.stanford. edu/data/）社交網(wǎng)絡(luò)，以及6個(gè)合作者網(wǎng)絡(luò)（T75sub0、T162sub1、T145sub0、T131sub0、T24sub0、T107sub1，http://www.datatang.com/datares/go.aspx?dataid=608815）。數(shù)據(jù)集詳細(xì)信息如表2所示（表中N表示節(jié)點(diǎn)數(shù)，M表示邊數(shù)，＜k＞表示網(wǎng)絡(luò)的平均度，＜c＞表示網(wǎng)絡(luò)的平均聚類系數(shù)，D表示網(wǎng)絡(luò)密度，Triadic表示網(wǎng)絡(luò)中三元閉包數(shù)目）。另外還分析了節(jié)點(diǎn)的度和節(jié)點(diǎn)擁有的三元閉包數(shù)的關(guān)系，如圖2所示（圖中的橫坐標(biāo)表示節(jié)點(diǎn)的度d，縱坐標(biāo)表示度為d的節(jié)點(diǎn)擁有的三元閉包數(shù)目的平均數(shù)）。從圖中的結(jié)果可以看出，整體上，節(jié)點(diǎn)的三元閉包數(shù)正比于節(jié)點(diǎn)的度。即節(jié)點(diǎn)的度越大，該節(jié)點(diǎn)擁有的三元閉包的數(shù)目就越多。另外，圖中隨著度的增加散點(diǎn)的分布越稀疏，這是因?yàn)榫W(wǎng)絡(luò)中度越大，節(jié)點(diǎn)的數(shù)目越少。由圖2的結(jié)果還可以看出，度大的節(jié)點(diǎn)占據(jù)著網(wǎng)絡(luò)中大部分三元閉包結(jié)構(gòu)，由此看出度大的節(jié)點(diǎn)對網(wǎng)絡(luò)結(jié)構(gòu)穩(wěn)定性有著重要影響。

Table 2 Information of datasets表2 數(shù)據(jù)集信息

4.3 結(jié)果分析

本文采用十字交叉驗(yàn)證法，將數(shù)據(jù)集平均分為10份，其中1份作為測試集，其余9份作為訓(xùn)練集。分別進(jìn)行了10次實(shí)驗(yàn)，取平均值作為最后的結(jié)果。與基本算法的精確度比較結(jié)果如表3所示，在該表中CN、AA、RA對應(yīng)的結(jié)果是基本相似性指標(biāo)算法的精確度結(jié)果；TWCN、TWAA、TWRA對應(yīng)的結(jié)果是直接加上節(jié)點(diǎn)權(quán)重的相似性指標(biāo)的精確度結(jié)果（即PWNW算法的結(jié)果）；TWCN*、TWAA*、TWRA*對應(yīng)的結(jié)果是在最優(yōu)參數(shù)α?xí)r的加節(jié)點(diǎn)權(quán)重的相似性指標(biāo)的精確度結(jié)果（即PWNW_α算法的結(jié)果）。表3～表5中加黑字體表示在對應(yīng)指標(biāo)下的最優(yōu)精確度值。

另外從表4可以得到，由結(jié)構(gòu)信息獲得的節(jié)點(diǎn)權(quán)重的鏈路預(yù)測算法在部分網(wǎng)絡(luò)中的預(yù)測效果，仍然高于由一般屬性信息獲得的邊權(quán)重的鏈路預(yù)測算法的預(yù)測效果。表5比較了有權(quán)重參數(shù)α調(diào)節(jié)的兩種不同權(quán)重預(yù)測算法的預(yù)測結(jié)果，可以看出，由結(jié)構(gòu)信息獲得的節(jié)點(diǎn)權(quán)重鏈路預(yù)測算法（PWNW_α算法）仍有預(yù)測精度上的優(yōu)勢。

Fig.2 Relationships between the number of triadic closure and degree d圖2 三元閉包數(shù)與度d的關(guān)系

而且本文算法的相似性指標(biāo)是基于網(wǎng)絡(luò)結(jié)構(gòu)信息的，其適用范圍比較廣泛，在有權(quán)網(wǎng)絡(luò)和無權(quán)網(wǎng)絡(luò)中均可應(yīng)用。整體來說，該相似性指標(biāo)在無權(quán)網(wǎng)絡(luò)中能夠提高預(yù)測精確度，在有權(quán)網(wǎng)絡(luò)中，該算法的精確度亦可以得到保證。圖3給出在這10個(gè)不同網(wǎng)絡(luò)中精確度與權(quán)重調(diào)節(jié)參數(shù)α的關(guān)系。根據(jù)精確度與α的關(guān)系，獲得各指標(biāo)取得最優(yōu)值時(shí)α的取值情況，來進(jìn)一步研究三元閉包對鏈路預(yù)測精確度的影響。參數(shù)α的取值結(jié)果如表6所示。

Table 3 Precision of CNWTC,PWNA_αand CN,AA,RAalgorithms表3 CNWTC算法、PWNA_α算法與CN、AA、RA算法的精確度

Table 4 Precision of TWCN,TWAA,TWRA and WCN,WAA,WRA表4 TWCN、TWAA、TWRA與WCN、WAA、WRA的精確度

Table 5 Precision of TWCN*,TWAA*,TWRA* and WCN*,WAA*,WRA*表5 TWCN*、TWAA*、TWRA*與WCN*、WAA*、WRA*的精確度

當(dāng)最優(yōu)參數(shù)α的值均小于0時(shí)，基于三元閉包得到的節(jié)點(diǎn)權(quán)重，權(quán)重小的節(jié)點(diǎn)對預(yù)測精確度的促進(jìn)作用較大，而權(quán)重較大的節(jié)點(diǎn)對預(yù)測精確度的促進(jìn)作用較小。這說明在社交網(wǎng)絡(luò)中會有這樣一種現(xiàn)象：擁有較多三元閉包的節(jié)點(diǎn)不傾向于建立更多的新鏈接；相反，擁有較少三元閉包的節(jié)點(diǎn)非常樂意去建立更多的新鏈接。即朋友圈越緊密的人不傾向結(jié)交更多的新朋友。在社會學(xué)領(lǐng)域中弱關(guān)系傳遞信息，人們?yōu)榱双@取更多且有用的信息，往往會愿意和關(guān)系并不緊密的朋友建立聯(lián)系。本文所提算法的實(shí)驗(yàn)結(jié)果也契合了這種社會學(xué)現(xiàn)象。表6中α取負(fù)值的情況（表6中加黑字體所示），說明這種現(xiàn)象是存在于社交網(wǎng)絡(luò)中的。

為了進(jìn)一步分析實(shí)驗(yàn)結(jié)果，做出如下定義：如果一條邊所在的三元閉包數(shù)目大于3，說明這條邊具有局部結(jié)構(gòu)特征。假設(shè)一條邊只具有局部結(jié)構(gòu)特征和非局部結(jié)構(gòu)特征，得到如圖4所示的結(jié)構(gòu)（粗線表示一條邊只具有局部結(jié)構(gòu)特征）。網(wǎng)絡(luò)中的三元閉包結(jié)構(gòu)可以表示為圖5中所示結(jié)構(gòu)。

Fig.3 Relationships between precision and parameterα圖3 精確度與參數(shù)α之間的關(guān)系

Table 6 Values of optimal parameterα表6 最優(yōu)參數(shù)α取值情況

Fig.4 Structure feature of edge in network圖4 網(wǎng)絡(luò)中邊的結(jié)構(gòu)特征

在這10個(gè)網(wǎng)絡(luò)中統(tǒng)計(jì)這7種連通三元閉包CS1～CS7的數(shù)目，分別用N1～N7表示。那么兩條邊都具有局部結(jié)構(gòu)特征，則相連的概率就為。設(shè)參數(shù) β=N4/Triadic（Triadic表示網(wǎng)絡(luò)中三元閉包數(shù)目）。β越大，說明網(wǎng)絡(luò)的局部結(jié)構(gòu)越稠密，三元閉包數(shù)越多。P1越小，說明網(wǎng)絡(luò)中局部相連的概率越低。當(dāng)β越大P1越小時(shí)，說明網(wǎng)絡(luò)的局部結(jié)構(gòu)越稠密，但是局部結(jié)構(gòu)相連的概率越低，該結(jié)果正好反映出上述現(xiàn)象。該結(jié)果越明顯說明這種現(xiàn)象在網(wǎng)絡(luò)中表現(xiàn)就越明顯。從表7的結(jié)果中可以看出，F(xiàn)acebook、Jazz、T75sub0、T145sub0、T131sub0和T24sub0這6個(gè)網(wǎng)絡(luò)明顯具有這種特征，這同樣說明了該現(xiàn)象是明顯存在于部分社交網(wǎng)絡(luò)中的。

Fig.5 Triadic closure structure in network圖5 網(wǎng)絡(luò)中三元閉包結(jié)構(gòu)

Table 7 Values ofP1andβ表7 P1與 β值

4.4 算法時(shí)間復(fù)雜度分析

運(yùn)算效率高且預(yù)測效果好的鏈路預(yù)測算法較難獲得，一般的算法是在兩者之間取得一個(gè)平衡或謀求某一方面的促進(jìn)與提升。在基于共同鄰居的鏈路預(yù)測算法中，計(jì)算節(jié)點(diǎn)對的共同鄰居的時(shí)間復(fù)雜度為O(k)，k表示網(wǎng)絡(luò)的平均度。因此對于CN算法來說，計(jì)算所有節(jié)點(diǎn)的相似度值的時(shí)間復(fù)雜度為O(n2×k)。AA與RA兩個(gè)算法與CN算法有著相同的計(jì)算過程，同樣與CN算法的時(shí)間復(fù)雜度也相同。較為簡單的PA算法[7]，其時(shí)間復(fù)雜度為O(n2)，是一種較為高效的方法。另外，局部路徑指標(biāo)LP算法[26]的時(shí)間復(fù)雜度為O(n×k3)?；谌值念A(yù)測算法Katz[27]的時(shí)間復(fù)雜度為O(n3)，另外ACT[28]和RWR[29]算法的時(shí)間復(fù)雜度也是O(n3)?；陔S機(jī)游走的兩個(gè)算法LRW和SRW[30]的時(shí)間復(fù)雜度為O(n×kl)，其中l(wèi)為隨機(jī)游走的步數(shù)。本文算法最耗時(shí)的地方是統(tǒng)計(jì)網(wǎng)絡(luò)中三元閉包數(shù)目的過程，其時(shí)間復(fù)雜度為O(n3)。其預(yù)測過程與CN算法的預(yù)測過程是完全相同的，該過程的時(shí)間復(fù)雜度為O(n2×k)，因此本文算法的時(shí)間復(fù)雜度為O(n3)。與CN、AA、RA算法相比犧牲了時(shí)間換取精度上的提升。

5 結(jié)束語

本文提出了一個(gè)新的基于網(wǎng)絡(luò)局部拓?fù)浣Y(jié)構(gòu)的度量節(jié)點(diǎn)相似性的鏈路預(yù)測算法。利用了網(wǎng)絡(luò)中的最基本的局部結(jié)構(gòu)三元閉包，根據(jù)結(jié)構(gòu)平衡理論，三元閉包具有結(jié)構(gòu)平衡特征和穩(wěn)定性特征。通過統(tǒng)計(jì)網(wǎng)絡(luò)中三元閉包數(shù)目，經(jīng)過轉(zhuǎn)化得到節(jié)點(diǎn)權(quán)重，將該權(quán)重應(yīng)用到鏈路預(yù)測相似性指標(biāo)中，得到計(jì)算節(jié)點(diǎn)相似性的方法，即3個(gè)相似性指標(biāo)TWCN、TWAA、TWRA和具有調(diào)節(jié)參數(shù)α的3個(gè)相似性指標(biāo)TWCN*、TWAA*、TWRA*，由此提出PWNW算法和PWNW_ α算法。與CN、AA和RA算法相比，PWNW_α算法在預(yù)測效果上有很大的優(yōu)勢。在10個(gè)網(wǎng)絡(luò)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，本文提出的鏈路預(yù)測算法能夠提高預(yù)測精確度。通過分析參數(shù)α的結(jié)果得到了一個(gè)很有趣的現(xiàn)象：在社交網(wǎng)絡(luò)中，擁有較多三元閉包的節(jié)點(diǎn)，不傾向于建立更多的新鏈接；相反，擁有較少三元閉包的節(jié)點(diǎn)，樂于建立更多的新鏈接。這種現(xiàn)象也符合社會學(xué)中有關(guān)弱關(guān)系產(chǎn)生鏈接的現(xiàn)象。

無向網(wǎng)絡(luò)中的一個(gè)三元閉包，在有向網(wǎng)絡(luò)中有7種情形。有向網(wǎng)絡(luò)中的三元閉包比無向網(wǎng)絡(luò)更復(fù)雜，不同的三元閉包對網(wǎng)絡(luò)功能有著不同的影響。下一步的工作是研究不同形式的三元閉包對有向網(wǎng)絡(luò)鏈路預(yù)測算法的影響。

[1]Mamitsuka H.Mining from protein-protein interactions[J]. Wiley Interdisciplinary Reviews:Data Mining and Knowledge Discovery,2012,2(5):400-410.

[2]Aiello L M,BarratA,Schifanella R,et al.Friendship prediction and homophily in social media[J].ACM Transactions on the Web,2012,6(2):1-33.

[3]Getoor L,Diehl C P.Link mining:a survey[J].ACM SIGKDD Explorations Newsletter,2005,7(2):3-12.

[4]Lv Linyuan,Zhou Tao.Link prediction in complex networks: a survey[J].Physica A:Statistical Mechanics and Its Applications,2011,390(6):1150-1170.

[5]Lv Linyuan.Link prediction on complex networks[J].Journal of University of Electronic Science and Technology of China,2010,39(5):651-661.

[6]Chen Bolun,Chen Ling,Li Bin.A fast algorithm for predicting links to nodes of interest[J].Information Sciences,2016, 329:552-567.

[7]Xie Yanbo,Zhou Tao,Wang Binghong.Scale-free networks without growth[J].Physica A:Statistical Mechanics and Its Applications,2008,387(7):1683-1688.

[8]Adamic L A,Adar E.Friends and neighbors on the Web[J]. Social Networks,2003,25(3):211-230.

[9]Ou Qing,Jin Yingdi,Zhou Tao,et al.Power-law strengthdegree correlation from a resource-allocation dynamics on weighted networks[J].Physical Review E,2007,75:021102.

[10]Gupta N,Singh A.A novel strategy for link prediction in soial networks[C]//Proceedings of the 10th International Conference on Emerging Networking Experiments and Technologies on Student Workshop,Sydney,Dec 2-5,2014. New York:ACM,2014:12-14.

[11]Yin Guisheng,Yin Wansi,Dong Yuxin.A new link prediction algorithm:node link strength algorithm[C]//Proceedings of the 2014 IEEE Symposium on Computer Applications and Communications,Weihai,China,Jul 26-27,2014. Piscataway,USA:IEEE,2014:5-9.

[12]Zhang Weiyu,Wu Bin.Accurate and fast link prediction in complex networks[C]//Proceedings of the 10th International Conference on Natural Computation,Xiamen,China,Aug 19-21,2014.Piscataway,USA:IEEE,2014:653-657.

[13]Easley D,Kleinberg J.Networks,crowds,and markets:reasoning about a highly connected world[M].Cambridge,UK: Cambridge University Press,2010.

[14]Carullo G,Castiglione A,De Santis A,et al.A triadic closure and homophily-based recommendation system for online social networks[J].World Wide Web,2015,18(6):1579-1601.

[15]Peng Taiquan.Assortative mixing,preferential attachment, and triadic closure:a longitudinal study of tie-generative mechanisms in journal citation networks[J].Journal of Informetrics,2015,9(2):250-262.

[16]Bianconi G,Darst R K,Iacovacci J,et al.Triadic closure as a basic generating mechanism of communities in complex networks[J].Physical Review E,2014,90(4):042806.

[17]Opsahl T.Triadic closure in two-mode networks:redefining the global and local clustering coefficients[J].Social Networks,2013,35(2):159-167.

[18]Medus A D,Dorso C O.Triadic closure mechanism in faceto-face and online social relationship networks[J].arXiv: 1312.3496,2013.

[19]Huang Hong,Tang Jie,Wu Sen,et al.Mining triadic closure patterns in social networks[C]//Proceedings of the 23rd International Conference on World Wide Web,Seoul, Apr 7-11,2014.New York:ACM,2014:499-504.

[20]Lv Linyuan,Zhou Tao.Role of weak ties in link prediction of complex networks[C]//Proceedings of the 1st ACM International Workshop on Complex Networks Meet Information&Knowledge Management,Hong Kong,China,Nov 6,2009.New York:ACM,2009:55-58.

[21]Wind D K,M?rup M.Link prediction in weighted networks [C]//Proceedings of the 2012 International Workshop on Machine Learning for Signal Processing,Santander,Spain, Sep 23-26,2012.Piscataway,USA:IEEE,2012:1-6.

[22]Hanley J A,McNeil B J.The meaning and use of the area under a receiver operating characteristic(ROC)curve[J]. Radiology,1982,143(1):29-36.

[23]Herlocker J L,Konstan J A,Terveen L G,et al.Evaluating collaborative filtering recommender systems[J].ACM Trans-actions on Information Systems,2004,22(1):5-53.

[24]Newman M E J.Finding community structure in networks using the eigenvectors of matrices[J].Physical Review E, 2006,74(3):036104.

[25]Gleiser P M,Danon L.Community structure in Jazz[J].Advances in Complex Systems,2003,6(4):565-573.

[26]Zhou Tao,Lv Linyuan,Zhang Yicheng.Predicting missing links via local information[J].The European Physical Journal B,2009,71(4):623-630.

[27]Katz L.A new status index derived from sociometric analysis[J].Psychometrika,1953,18(1):39-43.

[28]Klein D J,Randi? M.Resistance distance[J].Journal of Mathematical Chemistry,1993,12(1):81-95.

[29]Sehgal U,Kaur K,Kumar P.The anatomy of a large-scale hyper textual Web search engine[C]//Proceedings of the 2nd International Conference on Computer and Electrical Engineering,Dubai,UAE,Dec 28-30,2009.Washington: IEEE Computer Society,2009:491-495.

[30]Liu Weiping,Lv Linyuan.Link prediction based on local random walk[J].Europhysics Letters,2010,89(5):58007.

附中文參考文獻(xiàn)：

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

GAO Yang was born in 1990.He is an M.S.candidate at Anhui University.His research interests include complex network and link prediction,etc.

高楊（1990—），男，安徽宿州人，安徽大學(xué)碩士研究生，主要研究領(lǐng)域?yàn)閺?fù)雜網(wǎng)絡(luò)，鏈路預(yù)測等。

ZHANG Yanping was born in 1962.She is a professor and Ph.D.supervisor at Anhui University,the member of CCF.Her research interests include intelligent computing,quotient space,machine learning,artificial neural network and intelligent information processing,etc.

張燕平（1962—），女，安徽合肥人，安徽大學(xué)教授、博士生導(dǎo)師，CCF會員，主要研究領(lǐng)域?yàn)橹悄苡?jì)算，商空間，機(jī)器學(xué)習(xí)，神經(jīng)網(wǎng)絡(luò)，智能信息處理等。發(fā)表學(xué)術(shù)論文80多篇，其中SCI、EI、ISTP收錄30多篇。

QIAN Fulan was born in 1978.She received the Ph.D.degree from Anhui University in 2016.Now she is a lecturer at Anhui University,and the member of CCF.Her research interests include granular computing,social network and data mining,etc.

錢付蘭（1978—），女，安徽蚌埠人，2016年于安徽大學(xué)獲得博士學(xué)位，現(xiàn)為安徽大學(xué)講師，CCF會員，主要研究領(lǐng)域?yàn)榱Ｓ?jì)算，社交網(wǎng)絡(luò)，數(shù)據(jù)挖掘等。

ZHAO Shu was born in 1979.She is a professor and Ph.D.supervisor at Anhui University,and the member of CCF.Her research interests include intelligent computing,quotient space,machine learning,social network and granular computing,etc.

趙姝（1979—），女，安徽合肥人，安徽大學(xué)教授、博士生導(dǎo)師，CCF會員，主要研究領(lǐng)域?yàn)橹悄苡?jì)算，商空間，機(jī)器學(xué)習(xí)，社交網(wǎng)絡(luò)，粒計(jì)算等。

Link PredictionAlgorithm Based on Node Similarity of Triadic Closure*

GAO Yang,ZHANG Yanping,QIAN Fulan+,ZHAO Shu
School of Computer Science and Technology,Anhui University,Hefei 230601,China

+Corresponding author:E-mail:qianfulan@hotmail.com

GAO Yang,ZHAGN Yanping,QIAN Fulan,et al.Link prediction algorithm based on node similarity of triadic closure.Journal of Frontiers of Computer Science and Technology,2017,11(5)：822-832.

Link prediction is a fundamental method for analyzing complex network which has been widely used in many domains.Link prediction in complex network based on solely topological information is a challenging problem.As one of the basic local structure,triadic closure has the characteristics of structural balance and stability.This paper proposes a link prediction algorithm to measure the similarity of nodes based on triadic closure.By calculating the weight of each node in the network according to the triadic closure,and using the weights in the node similarity index,this paper proposes three similarity indexes of TWCN,TWAA,TWRA and the other three similarity indexes of TWCN*,TWAA*,TWRA*with adjustment parameter.The experimental results on ten real network datasets demonstrate that the new method can improve the accuracy of link prediction.Moreover,by analyzing the experiment results,this paper finds that the network with more triadic closure nodes tends to be more stable.In other words,a network with less triadic closure nodes is less stable,and it is more likely to establish a new link with others.This phenomenon is also consistent with some related phenomenon in sociology on weak relations to generate links.

complex networks;link prediction;triadic closure;node weight

10.3778/j.issn.1673-9418.1605039

A

TP391

*The National Natural Science Foundation of China under Grant Nos.61175046,61402006(國家自然科學(xué)基金);the Natural Science Foundation of Anhui Province under Grant No.1508085MF113(安徽省自然科學(xué)基金);the Humanities and Social Science Foundation of the Ministry of Education of China under Grant No.1508085MF113(教育部人文社科基金項(xiàng)目).

Received 2016-04,Accepted 2016-06.

CNKI網(wǎng)絡(luò)優(yōu)先出版:2016-06-23,http://www.cnki.net/kcms/detail/11.5602.TP.20160623.1139.008.html

摘 要：鏈路預(yù)測作為復(fù)雜網(wǎng)絡(luò)分析的基本方法被應(yīng)用到很多領(lǐng)域，完全基于拓?fù)浣Y(jié)構(gòu)信息的復(fù)雜網(wǎng)絡(luò)鏈路預(yù)測仍然是一個(gè)具有挑戰(zhàn)性的問題。三元閉包作為網(wǎng)絡(luò)中最小局部結(jié)構(gòu)，具有結(jié)構(gòu)平衡和穩(wěn)定的特征。提出了一種基于三元閉包的節(jié)點(diǎn)相似性鏈路預(yù)測算法，通過計(jì)算出每個(gè)節(jié)點(diǎn)在網(wǎng)絡(luò)中所占三元閉包的權(quán)重，并將該權(quán)重用于節(jié)點(diǎn)相似性指標(biāo)中，提出了3個(gè)相似性指標(biāo)TWCN、TWAA、TWRA和具有調(diào)節(jié)參數(shù)的3個(gè)相似性指標(biāo)TWCN*、TWAA*、TWRA*。在10個(gè)不同的網(wǎng)絡(luò)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，所提算法能夠提高鏈路預(yù)測的精度。不僅如此，通過分析實(shí)驗(yàn)結(jié)果，發(fā)現(xiàn)在社交網(wǎng)絡(luò)中擁有較多三元閉包的節(jié)點(diǎn)具有局部穩(wěn)定性，不傾向于建立更多的新鏈接；相反，擁有較少三元閉包的節(jié)點(diǎn)具有局部不穩(wěn)定性，傾向于建立更多的新鏈接。這種現(xiàn)象也符合社會學(xué)中有關(guān)弱關(guān)系產(chǎn)生鏈接的現(xiàn)象。