蔡 彪，李蕊岑，吳媛媛

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

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.2 加權(quán)標(biāo)簽相似性CSW算法

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

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

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

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

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

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

1.4 帶權(quán)值標(biāo)簽系統(tǒng)實例

為了進(jìn)一步說明本文的帶權(quán)值標(biāo)簽系統(tǒng)，下面以一個例子來解釋如何構(gòu)造一個帶權(quán)值的標(biāo)簽系統(tǒng)。

在圖1 中，ta為節(jié)點的標(biāo)簽，節(jié)點vi及vj的鄰居節(jié)點標(biāo)簽集為：｛ta，ta，ta，ta，ta，tb，tb，tb，tb，tc，t｝c，則vi的標(biāo)簽系統(tǒng)為：Ai=｛ta，tb，t｝c；節(jié)點vi及vj的鄰居節(jié)點標(biāo)簽集為：｛ta，ta，ta，tb，tc，td，te，tf，tg，th，th｝，則vj的標(biāo)簽系統(tǒng)為：Aj=｛ta，tb，tc，td，te，tf，tg，th｝。其中，vw節(jié)點為共同鄰居節(jié)點，其節(jié)點的標(biāo)簽權(quán)值為：在基礎(chǔ)權(quán)值1上加，即5/3，其余節(jié)點的標(biāo)簽權(quán)值均為1，則vi與vj兩節(jié)點的標(biāo)簽系統(tǒng)中每一類標(biāo)簽的對應(yīng)權(quán)重分別為：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é)點的標(biāo)簽Fig.1 Nodes and node tags

1.5 復(fù)雜性分析

2 實驗設(shè)置

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

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

2.2 評價標(biāo)準(zhǔn)

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

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

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

3 實驗結(jié)果

3.1 帶權(quán)值標(biāo)簽相似性實驗結(jié)果

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

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

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

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

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

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

4 實驗分析

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

4.1 帶權(quán)值標(biāo)簽增強(qiáng)了相似性

4.1.1 帶權(quán)值標(biāo)簽相似性CSW的分布

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

圖2 四個真實網(wǎng)絡(luò)的測試集中組成測試邊的節(jié)點對間lg(ki ?kj)的值與CSWij值的關(guān)系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 標(biāo)簽系統(tǒng)提升了相似性值

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

圖3 四個真實網(wǎng)絡(luò)的測試集中組成測試邊的節(jié)點對間lg(ki ?kj)的值與標(biāo)簽相似性平均值的關(guān)系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)絡(luò)中每條測試邊的標(biāo)簽相似性，并對lg(ki?kj)值相同的測試邊的標(biāo)簽相似性取平均值，用similarity來表示。

4.1.3 帶權(quán)值標(biāo)簽相似性解決了JT為0的情況

在圖3中存在標(biāo)簽相似性為0的情況。因此，本文分別統(tǒng)計了四個真實網(wǎng)絡(luò)中測試集中的邊數(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)絡(luò)的測試集中，出現(xiàn)大量JTij值為0 的情況，極少甚至沒有出現(xiàn)CSWij值為0 的情況。CSW 解決了組成測試邊的節(jié)點對間因不存在相同標(biāo)簽導(dǎo)致節(jié)點的標(biāo)簽相似性為0，進(jìn)而使產(chǎn)生鏈接的可能性為0 的情況，算法的準(zhǔn)確性也得到了提升。

4.1.4 CSW進(jìn)一步提升了CSTS相似性值

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

圖4 四個真實網(wǎng)絡(luò)中的測試集中組成測試邊的節(jié)點對間lg(ki ?kj)的值與標(biāo)簽相似性差值的關(guān)系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)絡(luò)每條鏈接中兩個節(jié)點的標(biāo)簽之間的Jaccard 相似性，選取大于等于0.2 的鏈接組成新的網(wǎng)絡(luò)Lastfm-2，該網(wǎng)絡(luò)的平均Jaccard 相似性為0.25。將Lastfm-2網(wǎng)絡(luò)的鏈接按訓(xùn)練集和測試集9∶1 的比例劃分，訓(xùn)練集被視為已知信息，測試集用來預(yù)測，表6 中為CSTS 與CSW 算法在不同網(wǎng)絡(luò)中的AUC值。

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

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

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

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

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

圖5 三個真實網(wǎng)絡(luò)的測試集中組成測試邊的節(jié)點對間lg(ki ?kj)的值與ki ?kj ?CSWij的關(guān)系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 的基礎(chǔ)上引入了偏好鏈接機(jī)制，CSWP 與基準(zhǔn)算法相比較而言，預(yù)測準(zhǔn)確性最好。同樣，本文在CSTS的基礎(chǔ)上也引入了偏好鏈接機(jī)制，得到了CSTSP 算法。CSTSP 算法和CSWP 算法在PB 和Religion 網(wǎng)絡(luò)上的預(yù)測準(zhǔn)確性相等，在Cora 網(wǎng)絡(luò)上，CSTSP 的準(zhǔn)確性略低于CSWP，該實驗結(jié)果進(jìn)一步驗證了假設(shè)2的正確性。

5 結(jié)語

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

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