相似性特征對鏈路預測的影響與增強

蔡 彪，李蕊岑，吳媛媛

（成都理工大學計算機與網(wǎng)絡安全學院，成都 610059）

（*通信作者電子郵箱caibiao@cdut.edu.cn）

0 引言

復雜網(wǎng)絡是研究真實世界中各種復雜系統(tǒng)的結(jié)構和演化規(guī)律的常用工具。許多社會、生物和信息系統(tǒng)都可以被抽象成一個個的網(wǎng)絡來對它們加以描述，一個典型的網(wǎng)絡是由許多節(jié)點和連接兩個節(jié)點之間的一些邊組成，其中節(jié)點用來代表真實系統(tǒng)中不同的個體或組織，而邊則用來表示它們之間的相互作用。與復雜網(wǎng)絡有關的研究越來越受到人們的關注，鏈路預測是復雜網(wǎng)絡的一個重要分支，它的任務是基于已知網(wǎng)絡結(jié)構［1-3］，挖掘出給定網(wǎng)絡中節(jié)點之間缺失的鏈接。對于某些網(wǎng)絡，特別是生物網(wǎng)絡，如蛋白質(zhì)-蛋白質(zhì)相互作用網(wǎng)絡［4-6］、代謝網(wǎng)絡和食物網(wǎng)，節(jié)點之間是否存在連接需要通過大量實驗結(jié)果來進行推斷。已知的實驗結(jié)果僅僅揭示了巨大網(wǎng)絡的冰山一角，但揭示這類網(wǎng)絡中隱而未現(xiàn)的鏈接需要耗費高額的實驗成本，如果預測能足夠準確，事先在已知網(wǎng)絡結(jié)構的基礎上設計出精確的鏈路預測算法，則可以大大降低實驗成本，而不是逐個地檢查所有可能的交互。鏈路預測因其重大的實際應用價值，成為許多科學分支的共同焦點［7-9］。

傳統(tǒng)上，一種有效的鏈路預測模型是對潛在節(jié)點對進行相似性評分，這對節(jié)點越相似，它們之間的聯(lián)系就越緊密，產(chǎn)生鏈接的可能性也就越大。此類方法可以通過研究網(wǎng)絡的結(jié)構特征來實現(xiàn)，如三元圖［10］、節(jié)點聚類［11］、社區(qū)結(jié)構［12］和環(huán)結(jié)構［13］等。此外，基于結(jié)構層次上節(jié)點之間的相似性，也有一系列經(jīng)典的預測算法，如共同鄰居（Common Neighbor，CN）［14］、AA（Adar-Adamic）［15］和資源分配（Resource Allocation，RA）［16］等，它們啟發(fā)了其他方法［17］。這些主要是通過它們的共同鄰居［14-16］、路徑［18］以及路徑的權重［19］來度量兩節(jié)點之間的相似性。然而大多數(shù)關于相似性的研究只考慮了結(jié)構特征，忽視了在創(chuàng)建新的鏈接時，標簽通常也扮演著重要的角色。

標簽能夠?qū)€人興趣進行描述，在推薦系統(tǒng)［20-22］中也得到了廣泛應用。卜心怡等［23］用微博的粉絲數(shù)量、微博數(shù)量、關注人數(shù)、轉(zhuǎn)發(fā)微博數(shù)量等作為節(jié)點標簽進行預測。Schifanella等［24］和Aiello 等［25］直接從社交平臺收集節(jié)點標簽來計算節(jié)點標簽的余弦相似性［26］。相應的也有通過研究標簽來度量節(jié)點相似性的方法，如相同標簽（Common Tags，CT）［25］和用戶標簽間的Jaccard 指標（Jaccard index between users’Tags，JT）［27］。這些研究都基于同質(zhì)性的假設，即具有相似標簽的節(jié)點傾向于彼此連接。Wang 等［28］提出一個節(jié)點的標簽不足以描述這個節(jié)點，這個節(jié)點的鄰居節(jié)點的標簽也具有參考價值，因此，使用每個節(jié)點自身的標簽及其鄰居節(jié)點的標簽來構造一個標簽系統(tǒng)，在標簽的基礎上增加了結(jié)構信息。標簽系統(tǒng)間的余弦相似性（Cosine Similarity between Tag Systems，CSTS）算法基于標簽系統(tǒng)，通過Cosine 相似性來度量vi和vj兩節(jié)點標簽系統(tǒng)的相似性。CSTS 算法的不足之處在于：在計算標簽系統(tǒng)中每類標簽的比重時，僅簡單計算了這類標簽在節(jié)點及其鄰居節(jié)點的節(jié)點集合中存在的個數(shù)，表示每個節(jié)點自身所攜帶的標簽的權值均為1，這意味著每一個節(jié)點的標簽貢獻都是相同的，每個標簽都處于同等地位。

共同鄰居［14］算法假設兩個節(jié)點擁有的共同鄰居越多，它們越傾向連接，這一方法在很多真實網(wǎng)絡中都證明是有效的［29］。基于樸素貝葉斯（Naive Bayes，NB）［30］分類器，在條件獨立［31］的假設下，Liu 等［32］設計了局部樸素貝葉斯（Local NB，LNB）模型來研究鏈路預測問題，并提出了基于局部樸素貝葉斯模型的相似性算法LNBCN（Local Naive Bayes model-CN）。基于以上分析，由于節(jié)點自身的重要性的不同，節(jié)點所帶有的標簽的貢獻也有所區(qū)別，共同鄰居節(jié)點的標簽的貢獻應高于其他標簽。因此，本文引入了角色函數(shù)，在CSTS的基礎上，對共同鄰居節(jié)點的標簽進行加權，提出了帶權值的標簽。本文研究了四個不同領域的真實網(wǎng)絡的結(jié)構特征，發(fā)現(xiàn)在不同的網(wǎng)絡中，節(jié)點間的標簽相似性差異較大。本文從該網(wǎng)絡結(jié)構特征著手，研究了標簽相似性與鏈路預測間的關系。本文主要工作如下：

1）通過對四個真實網(wǎng)絡中標簽相似性這一結(jié)構特征進行研究發(fā)現(xiàn)：在平均Jaccard 相似性較低的網(wǎng)絡中，通過使用帶權值的標簽可以提高節(jié)點間標簽的相似性，從而提高鏈路預測的準確率；在平均Jaccard 相似性較高的網(wǎng)絡中，在提高相似性的基礎上，充分利用結(jié)構特征，可以提高鏈路預測的準確率。

2）本文在標簽系統(tǒng)的基礎上提出了標簽具有角色性，并通過引入角色函數(shù)計算標簽的權值，提出了加權標簽余弦相似性（Cosine Similarity with Weighted tags，CSW）算法用于提高低相似性網(wǎng)絡中的鏈路預測準確性。

3）在高Jaccard相似性網(wǎng)絡中，將體現(xiàn)網(wǎng)絡結(jié)構信息的偏好鏈接機制引入到節(jié)點的相似性計算中，提出了基于偏好鏈接機制的加權標簽相似性（CSW based on Preferential attachment mechanism，CSWP）算法和基于偏好鏈接機制的標簽系統(tǒng)余弦相似性（Cosine Similarity between Tag Systems based on Preferential attachment mechanism，CSTSP）算法，提升了網(wǎng)絡中鏈路預測的準確性。

在真實網(wǎng)絡上實驗結(jié)果表明，相較于其他鏈路預測基準算法，CSW 算法、CSWP 算法和CSTSP 算法都取得了更好的預測效果。

1 基于網(wǎng)絡相似性結(jié)構的鏈路預測算法

1.1 相似性參數(shù)對鏈路預測的影響

本文在現(xiàn)有算法的基礎上研究四個來自不同領域的真實網(wǎng)絡的結(jié)構特征，特別是基于相似性結(jié)構特征的CSTS 算法。四個網(wǎng)絡的結(jié)構參數(shù)如表1 所示，其中：|V|是節(jié)點數(shù)；|E|是鏈接數(shù)；C是聚類系數(shù)［33］；kˉ是網(wǎng)絡的平均度；ntag是每個節(jié)點擁有的平均標簽數(shù)；Ntag是每個網(wǎng)絡中不同標簽的數(shù)目；J是測量每個鏈接中兩個節(jié)點的標簽之間的平均Jaccard 相似性［28］，J=；Ti是節(jié)點vi的標簽集合。

表1 四個真實網(wǎng)絡的結(jié)構特征Tab.1 Structural features of four real networks

本文主要分析基于相似性的網(wǎng)絡結(jié)構參數(shù)J，如表1 所示，PB（Political Blogs）和Religion 這兩個網(wǎng)絡上的J值較高，均達到0.9 以上，其次是Cora 網(wǎng)絡，相似性達到0.8，Lastfm 網(wǎng)絡的相似性最低為0.046。結(jié)合相似性參數(shù)J和CSTS 算法的研究結(jié)果如表2 所示，其中，偏好鏈接（Preferential Attachment，PA）和RA 為結(jié)構性預測算法，CT 和JT 僅基于標簽信息，CSTS 在CT 和JT 的基礎上，增加了結(jié)構信息，提高了節(jié)點間的標簽相似性。通過分析該結(jié)果發(fā)現(xiàn)：Jaccard 相似性最大的PB和Religion兩個網(wǎng)絡采用提高相似性的方法并不能提高預測的準確性，而Cora 和Lastfm 網(wǎng)絡通過提高節(jié)點之間的標簽相似性能夠在一定程度提高鏈路預測的準確性。

表2 基準鏈路預測算法與CSTS算法在四個網(wǎng)絡上的預測準確性Tab.2 Prediction accuracies of baseline link prediction algorithms and CSTS algorithm on four networks

基于以上分析，本文認為，在網(wǎng)絡的鏈路預測研究中，采用一種算法很難適應不同相似性結(jié)構網(wǎng)絡中的鏈路預測，為此提出以下兩點假設：

假設1 在平均Jaccard相似性較低（低于0.8）的網(wǎng)絡中，使用帶權值標簽系統(tǒng)可以優(yōu)化節(jié)點間標簽的相似性，從而提高鏈路預測的準確率。

假設2 在平均Jaccard 相似性較高（大于等于0.8）的網(wǎng)絡中，在相似性算法的基礎上充分利用結(jié)構特征可以提高鏈路預測的準確率。

根據(jù)上面提出的兩點假設，本文針對不同相似性結(jié)構網(wǎng)絡設計了相應的算法，以提高鏈路預測算法的性能。在Jaccard 相似性較低的網(wǎng)絡采用加權余弦標簽相似性CSW 算法；在Jaccard 相似性較高的網(wǎng)絡采用引入偏好鏈接機制的CSWP 算法和CSTSP 算法，這兩種算法在不同的相似性的網(wǎng)絡中均能在一定程度上提高鏈路預測的準確性。

1.2 加權標簽相似性CSW算法

為提高較低Jaccard 相似性網(wǎng)絡中標簽的相似性，本節(jié)將通過為標簽加權的方式來提高節(jié)點間標簽系統(tǒng)的相似性。為計算標簽的權值，首先計算節(jié)點vi的標簽系統(tǒng)，方法如下：

其中：Γ(vi)是節(jié)點vi的鄰居集合。

利用LNB 中角色函數(shù)計算每一個共同鄰居節(jié)點的標簽的權值。其定義如式（2）：

1.3 帶結(jié)構的CSWP算法

本節(jié)將研究在平均Jaccard 相似性較高的網(wǎng)絡中，將網(wǎng)絡結(jié)構信息與標簽相似性結(jié)合形成適合較高相似性網(wǎng)絡鏈路預測方法。為此，在CSW 的基礎上，引入偏好鏈接機制來進行鏈路預測，增加了網(wǎng)絡的結(jié)構特征，提出CSWP 相似性算法如下：

其中：ki和kj分別代表節(jié)點vi和節(jié)點vj的度，在傳統(tǒng)研究中通常用于衡量節(jié)點的吸引度［34］。CSWP 算法既考慮了結(jié)構特征，又結(jié)合了節(jié)點的標簽信息，通過重新定義節(jié)點標簽系統(tǒng)中標簽權重的計算方法，進一步提高了鏈路預測的準確性，這將有助于理解驅(qū)動網(wǎng)絡演化的機制。CSWP 算法的實現(xiàn)偽代碼如下。

1.4 帶權值標簽系統(tǒng)實例

為了進一步說明本文的帶權值標簽系統(tǒng)，下面以一個例子來解釋如何構造一個帶權值的標簽系統(tǒng)。

在圖1 中，ta為節(jié)點的標簽，節(jié)點vi及vj的鄰居節(jié)點標簽集為：｛ta，ta，ta，ta，ta，tb，tb，tb，tb，tc，t｝c，則vi的標簽系統(tǒng)為：Ai=｛ta，tb，t｝c；節(jié)點vi及vj的鄰居節(jié)點標簽集為：｛ta，ta，ta，tb，tc，td，te，tf，tg，th，th｝，則vj的標簽系統(tǒng)為：Aj=｛ta，tb，tc，td，te，tf，tg，th｝。其中，vw節(jié)點為共同鄰居節(jié)點，其節(jié)點的標簽權值為：在基礎權值1上加，即5/3，其余節(jié)點的標簽權值均為1，則vi與vj兩節(jié)點的標簽系統(tǒng)中每一類標簽的對應權重分別為：V（it）：｛ta：17/35，tb：12/35，tc：6/35｝，V（jt）：｛ta：11/35，tb：3/35，tc：3/35，td：3/35，te：3/35，tf：3/35，tg：3/35，th：6/35｝。

圖1 節(jié)點及節(jié)點的標簽Fig.1 Nodes and node tags

1.5 復雜性分析

2 實驗設置

2.1 實驗數(shù)據(jù)

本文的實驗數(shù)據(jù)使用表1 中的四個來自不同領域的真實網(wǎng)絡：1）Cora 網(wǎng)絡是一個由機器學習相關的論文組成［35-36］的引用網(wǎng)絡。每篇論文都被劃分到一個特定的類，其中，可能存在的類有：基于案例、遺傳算法、神經(jīng)網(wǎng)絡、概率方法、強化學習、規(guī)則學習和理論。2）Lastfm 網(wǎng)絡是一個從lastfm.com［37］收集的友誼網(wǎng)絡，其中每個用戶都可以為藝術家分配標簽。3）PB 網(wǎng)絡是美國政治博客的信息網(wǎng)絡［38］，其中每個節(jié)點都被標記為“自由”或“保守”。4）宗教網(wǎng)絡（Religion）是一個由新浪微博的宗教信徒組成的網(wǎng)絡［39］，其中每個用戶只有一個信仰，其中可能的信仰包括基督教、佛教、伊斯蘭教和道教。其中：Cora、PB 和Religion 網(wǎng)絡是定向網(wǎng)絡。在實驗中，忽略鏈接的方向，將網(wǎng)絡視為無向網(wǎng)絡。

2.2 評價標準

任意給定一個無向網(wǎng)絡G（V，E），為了測試算法的準確性，本文將已知的鏈接E隨機地分成兩部分：訓練集ET和測試集EP。訓練集被視為已知信息，測試集被用于測試，在計算分數(shù)值的時僅使用訓練集中的信息，測試集中的任何信息都不允許用于預測。顯然，E=ET∪EP，且ET∩EP=?。在本文的實驗中，|ET∶||EP|=9∶1，且保證訓練集中不包含孤立節(jié)點與圖的連通性。本文使用AUC（Area Under Curve）［40］衡量預測算法的準確性。AUC可以理解為在測試集中隨機選擇鏈接的分數(shù)值比隨機選擇不存在的鏈接（即集合UE中的鏈接，其中U為|V（||V|-1）/2個所有可能鏈接組成的全集）的分數(shù)值更高的概率。在實驗的n次獨立比較中，如果有n′次測試集中的鏈接分數(shù)值大于不存在的鏈接分數(shù)值，有n″次測試集中的鏈接分數(shù)值與不存在的鏈接分數(shù)值相等，則AUC定義為：

如果所有分數(shù)均隨機產(chǎn)生，則準確度應該在0.5 左右，因此，AUC高于0.5 的程度表示該算法比隨機選擇方法準確的程度。每個AUC精度值均為10次獨立實驗后的平均值。

從泉州志愿服務開展的情況看，大部分志愿活動是由政府部分機構組織的，志愿者也是由政府機關工作人員組成。政府主導和行政推動的方式雖然有利于啟動志愿服務活動，但過分依靠行政推動往往會出現(xiàn)“被志愿”或志愿服務形式化或運動化的問題。[7]由于長期的行政化主導，一方面讓民眾產(chǎn)生誤解，以為志愿服務是政府行為；一方面很容易形成運動式，出現(xiàn)形式化的問題；一方面“被志愿”者在心理上對志愿服務活動會產(chǎn)生抵觸情緒。

3 實驗結(jié)果

3.1 帶權值標簽相似性實驗結(jié)果

在本文實驗中，以J=0.8 為閾值來劃分低相似性網(wǎng)絡和高相似性網(wǎng)絡。由于Lastfm 網(wǎng)絡的平均Jaccard 相似性低于0.1，而Cora 的相似性為0.804，均低于PB 和Religion 兩個網(wǎng)絡的相似性，因此，將本文提出的標簽加權CSW 算法與現(xiàn)有的基準算法［41］和未加權的標簽算法在Lastfm和Cora網(wǎng)絡上進行了實驗對比，以此驗證假設1 的正確性。每個AUC精度值均為10 次獨立實驗后的平均值，加粗的值表示在同一個網(wǎng)絡中性能最好的算法的平均AUC精度值，相較于其他算法，本文提出的基于加權標簽相似的CSW 算法的鏈路預測準確性最好，對比的實驗結(jié)果如表3所示。

從表3可以看出，在平均Jaccard相似性較低的網(wǎng)絡中，帶權值的標簽系統(tǒng)通過為標簽加權提高了標簽系統(tǒng)的相似性，從而提高鏈路預測的準確性，驗證了第2章中提出的第1個假設，在低相似性的網(wǎng)絡中，提高相似性可以得到最高的準確性。

表3 CSTS、CSW和基準算法在Lastfm和Cora網(wǎng)絡上的AUCTab.3 AUC of CSTS，CSW and baseline algorithms on Lastfm and Cora networks

3.2 引入結(jié)構信息實驗結(jié)果

與Lastfm 網(wǎng)絡相比，可以認為Cora、PB 和Religion 這三個網(wǎng)絡的平均Jaccard 相似性為高相似性網(wǎng)絡結(jié)構。本文將CSWP 算法和CSTSP 算法與幾個基準算法在這三個網(wǎng)絡上進行了實驗對比，以此驗證假設2的正確性。實驗結(jié)果如表4所示。在上述多組對比實驗中，基于偏好鏈接機制的CSTSP 和CSWP 的準確性在三個網(wǎng)絡中相較于不包含偏好鏈接機制的CSTS 和CSW 均有較大的提高。在Cora 網(wǎng)絡上，CSWP 的預測準確率略高于CSTSP，可以認為預測結(jié)果的提高是因為帶權值的CSW 算法提升了標簽相似性。在Jaccard 相似性大于0.9 的PB 和Religion 網(wǎng)絡中，CSTSP 和CSWP 的預測準確性一致。CSW 與CSTS 相比，有較小程度的提升。因此，可以認為在Jaccard 相似性很高的網(wǎng)絡中，相似性改變不能明顯提高鏈路預測的準確性，鏈路預測結(jié)果主要由引入的結(jié)構信息決定，在提高相似性的基礎上引入的結(jié)構信息可以得到最高的準確性，驗證了第2章中提出第2個假設的正確性。

表4 不同算法在Cora、PB和Religion網(wǎng)絡上的AUCTab.4 AUC of different algorithms on Cora，PB and Religion networks

4 實驗分析

鏈路預測算法主要是基于標簽信息和結(jié)構信息這兩個方面設計的，同時，多種有助于鏈路預測的機制都與標簽和結(jié)構有關，當網(wǎng)絡和算法所遵循的機制一致時，該算法能夠提供更加準確的預測。因此，本文將從標簽和結(jié)構這兩個方面對實驗結(jié)果進行分析。

4.1 帶權值標簽增強了相似性

4.1.1 帶權值標簽相似性CSW的分布

根據(jù)3.2 節(jié)中提出的數(shù)據(jù)劃分方法，將四個真實網(wǎng)絡隨機劃分為訓練集ET和測試集EP兩部分，訓練集被視為已知信息，用來計算測試集中每條測試邊關于lg(ki?kj)和CSWij的相似性值。Cora、PB 和Religion 三個網(wǎng)絡的J值較高，Lastfm 的J值較低，在圖2 中Cora、PB、Religion 這三個網(wǎng)絡上，CSWij的值大多分布在0.8～1.0，而Lastfm的CSWij的值大多都分布在0.8以下。本文分別計算了四個網(wǎng)絡的測試部分的CSWij平均值：在Cora 上為0.882；在Lastfm 上為0.666；在PB 上為0.944；在Religion 上為0.983。同樣計算了四個網(wǎng)絡的測試部分的Jaccardij平均值：在Cora 上為0.819；在Lastfm 上為0.047；在PB 上 為0.901；在Religion 上 為0.981。CSWij值相較于Jaccardij相似性值均有一定程度的提高，尤其是在Lastfm 中，節(jié)點間的標簽系統(tǒng)相似性較Jaccardij相似性值改變最明顯。

圖2 四個真實網(wǎng)絡的測試集中組成測試邊的節(jié)點對間lg(ki ?kj)的值與CSWij值的關系Fig.2 Relationship between lg(ki ?kj)value and CSWij value of the node pairs that constitute the test edge in the test set of four real networks

4.1.2 標簽系統(tǒng)提升了相似性值

接下來分析基于標簽相似性的CSTS 和基于帶權值標簽相似性的CSW 相較于僅基于標簽信息的JT 預測算法的相似性。JT算法的預測準確性較低，僅略高于隨機預測的準確性。CSTS 和CSW 在CT 和JT 的基礎上，將鄰居節(jié)點的標簽也考慮進來。在平均Jaccard 相似性較低的Lastfm 網(wǎng)絡中，使用節(jié)點鄰居的標簽信息大幅提高了節(jié)點間標簽的相似性，如圖3（b）所示，與JT 算法相比，CSTS 算法和CSW 算法的相似性有大幅度的提升；在平均Jaccard 相似性較高的網(wǎng)絡中，Cora、PB 和Religion 三個網(wǎng)絡的J值較高，使用節(jié)點鄰居的標簽信息不同程度地提高了節(jié)點間標簽的相似性，如圖3（a）、（c）和（d）以及表2 與表4 所示，與CT 和JT 相比，CSTS 算法和CSW 算法的準確性相應地也得到了提升；并且，標簽相似性越低的網(wǎng)絡，通過提高節(jié)點間標簽的相似性來提升算法的準確性的效果越顯著，這一結(jié)論在Cora、Lastfm和PB網(wǎng)絡上可以得到印證。

圖3 四個真實網(wǎng)絡的測試集中組成測試邊的節(jié)點對間lg(ki ?kj)的值與標簽相似性平均值的關系Fig.3 Relationship between lg(ki ?kj)value and average value of tag similarity of the node pairs that constitute the test edge in the test sets of four real networks

分別用CSW 算法、CSTS 算法和JT 算法計算了四個網(wǎng)絡中每條測試邊的標簽相似性，并對lg(ki?kj)值相同的測試邊的標簽相似性取平均值，用similarity來表示。

4.1.3 帶權值標簽相似性解決了JT為0的情況

在圖3中存在標簽相似性為0的情況。因此，本文分別統(tǒng)計了四個真實網(wǎng)絡中測試集中的邊數(shù)（Edges）、測試邊CSWij=0 的數(shù)量（用CSW（0）表示）、測試邊JTij=0 的數(shù)量（用JT（0）表示）。實驗結(jié)果如表5所示。

表5 CSWij與JTij在測試集中值為0的情況Tab.5 Cases where the values of CSWij and JTij are zero in the test sets

分析實驗結(jié)果發(fā)現(xiàn)：在四個真實網(wǎng)絡的測試集中，出現(xiàn)大量JTij值為0 的情況，極少甚至沒有出現(xiàn)CSWij值為0 的情況。CSW 解決了組成測試邊的節(jié)點對間因不存在相同標簽導致節(jié)點的標簽相似性為0，進而使產(chǎn)生鏈接的可能性為0 的情況，算法的準確性也得到了提升。

4.1.4 CSW進一步提升了CSTS相似性值

本文的CSW 相較于CSTS 在一定程度上能夠提升預測的準確性。因為CSW 算法在CSTS 算法的基礎上引入了帶權值的標簽，有助于提升存在邊的相似性。為了驗證該結(jié)論，分別用CSW 算法和CSTS 算法計算每條測試邊節(jié)點對間的標簽相似性，對同一條測試邊，用CSWij減去CSTSij，得到的差值用D-value進行表示。如圖4 所示，D-value的值幾乎全部分布于0 刻度線以上，這表明使用帶權值的標簽加強了潛在節(jié)點對間的標簽相似性，且Lastfm 的相似性提高更多。基于以上分析，本文驗證了假設1 的正確性，在節(jié)點間標簽相似性較低的網(wǎng)絡中，使用帶權值的標簽，在標簽系統(tǒng)的基礎上進一步提高節(jié)點間標簽的相似性從而提高鏈路預測的準確率。

圖4 四個真實網(wǎng)絡中的測試集中組成測試邊的節(jié)點對間lg(ki ?kj)的值與標簽相似性差值的關系Fig.4 Relationship between lg(ki ?kj)value and label similarity difference of the node pairs that constitute the test sets of four real networks

計算Lastfm 網(wǎng)絡每條鏈接中兩個節(jié)點的標簽之間的Jaccard 相似性，選取大于等于0.2 的鏈接組成新的網(wǎng)絡Lastfm-2，該網(wǎng)絡的平均Jaccard 相似性為0.25。將Lastfm-2網(wǎng)絡的鏈接按訓練集和測試集9∶1 的比例劃分，訓練集被視為已知信息，測試集用來預測，表6 中為CSTS 與CSW 算法在不同網(wǎng)絡中的AUC值。

表6 CSTS與CSW算法的AUC比較Tab.6 AUC comparison of CSTS and CSW algorithms

將J為0.046 的Lastfm 網(wǎng)絡的平均Jaccard 相似性提高到0.25，在相似性較低的網(wǎng)絡中，提高標簽的相似性有助于提高鏈路預測的準確性，同時也表明，CSW 算法在相似性較低的網(wǎng)絡中與其他的標簽相似性算法相比有更好的表現(xiàn)。

4.2 高相似性網(wǎng)絡中結(jié)構信息的影響分析

在平均Jaccard相似性較高的Cora、PB和Religion網(wǎng)絡中，由于PA、CN、RA 和LNBCN 等算法均是僅基于結(jié)構信息的算法，而它們的AUC精度值均高于僅基于標簽信息的算法。本文提出的CSWP 在CSW 的基礎上引入了偏好鏈接機制，增加了ki?kj，CSWP 中的CSW 包含了同質(zhì)性機制和聚類機制，既使用了標簽信息，又使用了結(jié)構信息。

在CSWP 中，當vi和vj兩節(jié)點間存在共同鄰居節(jié)點時，本文將共同鄰居節(jié)點對vi和vj是否產(chǎn)生鏈接的貢獻度量通過其節(jié)點所攜帶標簽的權值進行表示；當vi和vj兩節(jié)點間不存在共同鄰居時，CSW 將退化成CSTS，聚類機制將不再發(fā)生作用。在計算潛在節(jié)點對間形成鏈接的可能性時，若節(jié)點的標簽系統(tǒng)間相似性不同，即CSWij值不同，則可以區(qū)分多個ki?kj值相等的潛在節(jié)點對，如圖5 所示；當節(jié)點對的標簽系統(tǒng)間標簽種類和對應比重值完全相同時，CSWij值最大為1，兩節(jié)點吸引力達到最大，為ki?kj；相反，若節(jié)點對的標簽系統(tǒng)間有不同的標簽或相同標簽對應比重值不同，則這兩個節(jié)點的吸引力就會降低，將低于ki?kj。

圖5 三個真實網(wǎng)絡的測試集中組成測試邊的節(jié)點對間lg(ki ?kj)的值與ki ?kj ?CSWij的關系Fig.5 Relationship between lg(ki ?kj)value and ki ?kj ?CSWij of the node pairs that constitute the test edge in the test sets of three real networks

CSWP 在CSW 的基礎上引入了偏好鏈接機制，CSWP 與基準算法相比較而言，預測準確性最好。同樣，本文在CSTS的基礎上也引入了偏好鏈接機制，得到了CSTSP 算法。CSTSP 算法和CSWP 算法在PB 和Religion 網(wǎng)絡上的預測準確性相等，在Cora 網(wǎng)絡上，CSTSP 的準確性略低于CSWP，該實驗結(jié)果進一步驗證了假設2的正確性。

5 結(jié)語

本文主要研究了相似性在復雜網(wǎng)絡演化中對鏈路預測的影響。在標簽系統(tǒng)的研究中，忽略了標簽的角色性。本文認為，具有不同相似性參數(shù)的網(wǎng)絡可以采用不同的方法來提高鏈路預測的準確性，不同節(jié)點所攜帶標簽重要性也不同，共同鄰居節(jié)點的標簽的貢獻應高于其他標簽。本文結(jié)合鏈路預測的多個基準算法以及來自四個不同領域的真實網(wǎng)絡的結(jié)構特征對標簽相似性與鏈路預測間的關系進行研究，發(fā)現(xiàn)網(wǎng)絡的標簽相似性特征對所采用的鏈路預測方法有較大的影響，提出了兩點假設，并根據(jù)這兩點假設分別設計了對應的鏈路預測算法。在四個真實網(wǎng)絡上進行的實驗結(jié)果表明，本文提出的根據(jù)不同網(wǎng)絡相似性特征采用對應算法進行鏈路預測均能夠得到更準確的預測結(jié)果。

由于帶權值標簽和偏好鏈接機制均是基于1 階網(wǎng)絡相似性，因此，下一步工作將在本文的基礎上研究基于1.5 階鏈路預測算法來揭示驅(qū)動網(wǎng)絡演化的機制；同時，本文中的閾值是根據(jù)經(jīng)驗設置的，目前沒有合適的實驗數(shù)據(jù)來研究J的不同值對結(jié)果的影響，下一步工作還將結(jié)合模糊優(yōu)化理論和合適的網(wǎng)絡對其作進一步研究分析。