基于三元閉包的節點相似性鏈路預測算法*

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

安徽大學 計算機科學與技術學院，合肥 230601

基于三元閉包的節點相似性鏈路預測算法*

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

安徽大學 計算機科學與技術學院，合肥 230601

復雜網絡；鏈路預測；三元閉包；節點權重

1 引言

很多復雜系統都可以用網絡的形式來描述，節點可以表示一個人、一座城市或者一個機構等，邊可以表示節點之間的聯系、關系或相互作用等。復雜網絡涉及的領域非常廣泛，在社會、技術、生物等領域都有關于復雜網絡的研究。復雜網絡研究對探索網絡生成機制具有重要的意義。

鏈路預測作為復雜網絡的重要研究方向越來越受到研究者們的關注。網絡中的鏈路預測是指如何通過已知的網絡節點和網絡結構等信息，預測網絡中尚未連接的兩個節點之間產生鏈接的可能性[1-3]。這種預測既包含對未知鏈接的預測，也包含對未來鏈接的預測。

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

本文組織結構如下：第1章介紹鏈路預測的研究目的與意義；第2章討論相關工作；第3章介紹本文提出的鏈路預測算法；第4章給出實驗結果并進行算法效率分析；第5章是結束語，總結本文工作以及對下一步研究進行展望。

2 相關工作

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

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

本文根據三元閉包結構提出了一種加節點權重的鏈路預測算法，根據三元閉包結構的數目計算節點的權重。首先統計網絡中每個節點擁有的三元閉包結構的數目，根據該數目對每個節點排序，得到每個節點的序值，再將序值映射到區間[0,1]內，由此求得每個節點的權重。將其應用到節點相似性指標中得到計算相似性的方法。采用CN算法、AA算法和RA算法作為最基本的對比算法。與文獻[20]和文獻[21]中提出的在有權網絡中的鏈路預測算法進行比較，在10個真實網絡中實驗結果表明，本文算法能夠提高鏈路預測的精確度。分析實驗結果，發現了一個很有趣的現象：在社交網絡中，擁有較多三元閉包結構的用戶，不傾向于建立更多的新鏈接；相反，擁有較少三元閉包結構的用戶，傾向于建立更多的新鏈接。這種現象也符合社會學中有關弱關系產生鏈接的現象。

3 算法描述

3.1 鏈路預測問題描述

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

3.2 基本算法介紹

定義Γ(x)表示節點x的鄰居節點集合，CN、AA、RA算法的計算節點相似性指標的定義如下。

（1）CN指標：其思想是兩個節點如果有很多的共同鄰居節點，那么這兩個節點相似。

（2）AA指標：其思想是度小的共同鄰居節點的貢獻大于度大的共同鄰居節點，根據共同鄰居節點的度為每個節點賦予一個權重值。

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

其中，kz表示節點z的度。

3.3 基于三元閉包的鏈路預測算法

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

Fig.1 Asimple network圖1 一個簡單網絡

Table 1 Node weight表1 節點權重

基于三元閉包的節點相似性鏈路預測算法，其計算相似性的方法是將所求的節點權重應用到CN指標、AA指標和RA指標中，分別得到加節點權重的共同鄰居指標TWCN，加節點權重的Adamic-Adar指標TWAA，加節點權重的資源分配指標TWRA。其計算公式如下所示：

為了進一步研究三元閉包結構在鏈路預測中的作用，將式（4）、（5）和（6）節點相似性指標進行改進，加入權重調節參數α來調節權重的大小。其計算公式如下所示：

將根據三元閉包計算節點權重的算法命名為CNWTC（calc node weight based triadic closure）算法。將基于節點權重的鏈路預測算法命名為PWNW（prediction with node weight）算法。將帶調節參數α的鏈路預測算法命名為PWNW_α（prediction with node weight_α）算法。

算法1 CNWTC算法

算法2 PWNW算法

算法3 PWNW_α算法

4 實驗結果分析

4.1 評價指標

鏈路預測評價指標有AUC（area under the receiver operating characteristic curve）[22]和精確度[23]precision）。

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

precision定義為在前L個預測邊中被預測準確的比例。如果有m個預測準確，即排在前L的邊中有m個在測試集中，則precision定義為：

本文采用的評價指標是precision，排序列表L的長度為100。

4.2 實驗數據

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

Table 2 Information of datasets表2 數據集信息

4.3 結果分析

本文采用十字交叉驗證法，將數據集平均分為10份，其中1份作為測試集，其余9份作為訓練集。分別進行了10次實驗，取平均值作為最后的結果。與基本算法的精確度比較結果如表3所示，在該表中CN、AA、RA對應的結果是基本相似性指標算法的精確度結果；TWCN、TWAA、TWRA對應的結果是直接加上節點權重的相似性指標的精確度結果（即PWNW算法的結果）；TWCN*、TWAA*、TWRA*對應的結果是在最優參數α時的加節點權重的相似性指標的精確度結果（即PWNW_α算法的結果）。表3～表5中加黑字體表示在對應指標下的最優精確度值。

另外從表4可以得到，由結構信息獲得的節點權重的鏈路預測算法在部分網絡中的預測效果，仍然高于由一般屬性信息獲得的邊權重的鏈路預測算法的預測效果。表5比較了有權重參數α調節的兩種不同權重預測算法的預測結果，可以看出，由結構信息獲得的節點權重鏈路預測算法（PWNW_α算法）仍有預測精度上的優勢。

Fig.2 Relationships between the number of triadic closure and degree d圖2 三元閉包數與度d的關系

而且本文算法的相似性指標是基于網絡結構信息的，其適用范圍比較廣泛，在有權網絡和無權網絡中均可應用。整體來說，該相似性指標在無權網絡中能夠提高預測精確度，在有權網絡中，該算法的精確度亦可以得到保證。圖3給出在這10個不同網絡中精確度與權重調節參數α的關系。根據精確度與α的關系，獲得各指標取得最優值時α的取值情況，來進一步研究三元閉包對鏈路預測精確度的影響。參數α的取值結果如表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*的精確度

當最優參數α的值均小于0時，基于三元閉包得到的節點權重，權重小的節點對預測精確度的促進作用較大，而權重較大的節點對預測精確度的促進作用較小。這說明在社交網絡中會有這樣一種現象：擁有較多三元閉包的節點不傾向于建立更多的新鏈接；相反，擁有較少三元閉包的節點非常樂意去建立更多的新鏈接。即朋友圈越緊密的人不傾向結交更多的新朋友。在社會學領域中弱關系傳遞信息，人們為了獲取更多且有用的信息，往往會愿意和關系并不緊密的朋友建立聯系。本文所提算法的實驗結果也契合了這種社會學現象。表6中α取負值的情況（表6中加黑字體所示），說明這種現象是存在于社交網絡中的。

為了進一步分析實驗結果，做出如下定義：如果一條邊所在的三元閉包數目大于3，說明這條邊具有局部結構特征。假設一條邊只具有局部結構特征和非局部結構特征，得到如圖4所示的結構（粗線表示一條邊只具有局部結構特征）。網絡中的三元閉包結構可以表示為圖5中所示結構。

Fig.3 Relationships between precision and parameterα圖3 精確度與參數α之間的關系

Table 6 Values of optimal parameterα表6 最優參數α取值情況

Fig.4 Structure feature of edge in network圖4 網絡中邊的結構特征

在這10個網絡中統計這7種連通三元閉包CS1～CS7的數目，分別用N1～N7表示。那么兩條邊都具有局部結構特征，則相連的概率就為。設參數 β=N4/Triadic（Triadic表示網絡中三元閉包數目）。β越大，說明網絡的局部結構越稠密，三元閉包數越多。P1越小，說明網絡中局部相連的概率越低。當β越大P1越小時，說明網絡的局部結構越稠密，但是局部結構相連的概率越低，該結果正好反映出上述現象。該結果越明顯說明這種現象在網絡中表現就越明顯。從表7的結果中可以看出，Facebook、Jazz、T75sub0、T145sub0、T131sub0和T24sub0這6個網絡明顯具有這種特征，這同樣說明了該現象是明顯存在于部分社交網絡中的。

Fig.5 Triadic closure structure in network圖5 網絡中三元閉包結構

Table 7 Values ofP1andβ表7 P1與 β值

4.4 算法時間復雜度分析

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

5 結束語

本文提出了一個新的基于網絡局部拓撲結構的度量節點相似性的鏈路預測算法。利用了網絡中的最基本的局部結構三元閉包，根據結構平衡理論，三元閉包具有結構平衡特征和穩定性特征。通過統計網絡中三元閉包數目，經過轉化得到節點權重，將該權重應用到鏈路預測相似性指標中，得到計算節點相似性的方法，即3個相似性指標TWCN、TWAA、TWRA和具有調節參數α的3個相似性指標TWCN*、TWAA*、TWRA*，由此提出PWNW算法和PWNW_ α算法。與CN、AA和RA算法相比，PWNW_α算法在預測效果上有很大的優勢。在10個網絡數據集上的實驗結果表明，本文提出的鏈路預測算法能夠提高預測精確度。通過分析參數α的結果得到了一個很有趣的現象：在社交網絡中，擁有較多三元閉包的節點，不傾向于建立更多的新鏈接；相反，擁有較少三元閉包的節點，樂于建立更多的新鏈接。這種現象也符合社會學中有關弱關系產生鏈接的現象。

無向網絡中的一個三元閉包，在有向網絡中有7種情形。有向網絡中的三元閉包比無向網絡更復雜，不同的三元閉包對網絡功能有著不同的影響。下一步的工作是研究不同形式的三元閉包對有向網絡鏈路預測算法的影響。

[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.

附中文參考文獻：

[5]呂琳媛.復雜網絡鏈路預測[J].電子科技大學學報,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—），男，安徽宿州人，安徽大學碩士研究生，主要研究領域為復雜網絡，鏈路預測等。

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—），女，安徽合肥人，安徽大學教授、博士生導師，CCF會員，主要研究領域為智能計算，商空間，機器學習，神經網絡，智能信息處理等。發表學術論文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年于安徽大學獲得博士學位，現為安徽大學講師，CCF會員，主要研究領域為粒計算，社交網絡，數據挖掘等。

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—），女，安徽合肥人，安徽大學教授、博士生導師，CCF會員，主要研究領域為智能計算，商空間，機器學習，社交網絡，粒計算等。

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(國家自然科學基金);the Natural Science Foundation of Anhui Province under Grant No.1508085MF113(安徽省自然科學基金);the Humanities and Social Science Foundation of the Ministry of Education of China under Grant No.1508085MF113(教育部人文社科基金項目).

Received 2016-04,Accepted 2016-06.

CNKI網絡優先出版:2016-06-23,http://www.cnki.net/kcms/detail/11.5602.TP.20160623.1139.008.html

摘 要：鏈路預測作為復雜網絡分析的基本方法被應用到很多領域，完全基于拓撲結構信息的復雜網絡鏈路預測仍然是一個具有挑戰性的問題。三元閉包作為網絡中最小局部結構，具有結構平衡和穩定的特征。提出了一種基于三元閉包的節點相似性鏈路預測算法，通過計算出每個節點在網絡中所占三元閉包的權重，并將該權重用于節點相似性指標中，提出了3個相似性指標TWCN、TWAA、TWRA和具有調節參數的3個相似性指標TWCN*、TWAA*、TWRA*。在10個不同的網絡數據集上的實驗結果表明，所提算法能夠提高鏈路預測的精度。不僅如此，通過分析實驗結果，發現在社交網絡中擁有較多三元閉包的節點具有局部穩定性，不傾向于建立更多的新鏈接；相反，擁有較少三元閉包的節點具有局部不穩定性，傾向于建立更多的新鏈接。這種現象也符合社會學中有關弱關系產生鏈接的現象。