參照零模型的加權(quán)網(wǎng)絡(luò)鏈路預(yù)測因素研究

*基金項目：安徽省高等學(xué)校自然科學(xué)重點研究項目（編號 2022AH052763）的成果之一。

收稿日期：2024-5-2

作者簡介：梁西陳（1975-），安徽宿州人，碩士，副教授，研究方向：網(wǎng)絡(luò)安全、云計算等。Email：sffi515@163.com。

摘要：基于零模型，文章研究了如何量化分析加權(quán)復(fù)雜網(wǎng)絡(luò)中鏈路預(yù)測的影響因素。通過對1階零模型、權(quán)重置亂零模型，結(jié)構(gòu)置亂零模型在拓?fù)浣Y(jié)構(gòu)和權(quán)重相關(guān)性兩個方面分別進(jìn)行研究。以美國航空網(wǎng)絡(luò)為實證網(wǎng)絡(luò)，針對加權(quán)網(wǎng)絡(luò)中的權(quán)重特性，分析不同權(quán)重連邊的可預(yù)測性和對于鏈路預(yù)測的影響。結(jié)果表明，美國航空網(wǎng)中存在拓?fù)錂?quán)重相關(guān)性，并且破環(huán)拓?fù)浣Y(jié)構(gòu)比破壞權(quán)重相關(guān)性對于鏈路預(yù)測的影響更大。

關(guān)鍵詞：復(fù)雜網(wǎng)絡(luò)，加權(quán)復(fù)雜網(wǎng)絡(luò)，零模型，鏈路預(yù)測

中圖分類號：O157.5

文獻(xiàn)標(biāo)識碼：A

文章編號：1674-9545（2024）02-0000-（04）

DOI：10.19717/j.cnki.jjun.2024.02.018

鏈路預(yù)測問題是復(fù)雜的網(wǎng)絡(luò)領(lǐng)域中一個重要的研究熱點［1］，相關(guān)的預(yù)測方法、影響因素、結(jié)構(gòu)與功能的關(guān)系等研究［2］，無論對于靜態(tài)復(fù)雜網(wǎng)絡(luò)或者動態(tài)復(fù)雜網(wǎng)絡(luò)都有很重要的研究價值和科學(xué)意義。為了提高各個方法在加權(quán)網(wǎng)絡(luò)鏈路的預(yù)測效果，傅馨玉和顧益軍利用自定義系數(shù)調(diào)節(jié)影響程度作為結(jié)構(gòu)相似性與節(jié)點重要性的融合節(jié)點，提高加權(quán)網(wǎng)絡(luò)鏈路預(yù)測算法的精確度［3］。袁榕等人基于4個鏈接拓?fù)錂?quán)重的WCD含權(quán)預(yù)測指標(biāo)，以邊的聚類和擴(kuò)散特性作為邊的拓?fù)錂?quán)重，提高帶權(quán)數(shù)據(jù)集的鏈路預(yù)測精度［4］。萬楊曄等人通過網(wǎng)絡(luò)局部結(jié)構(gòu)相似性與特征余弦相似性結(jié)合定義網(wǎng)絡(luò)的結(jié)構(gòu)權(quán)重，提高了拓?fù)浣Y(jié)構(gòu)網(wǎng)絡(luò)鏈路的預(yù)測精度［5］。此外，結(jié)構(gòu)信息和權(quán)重是影響鏈路預(yù)測的主要因素［6］，比如，張斌等人通過改變網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)特征的聚類系數(shù)，發(fā)現(xiàn)在稀疏網(wǎng)絡(luò)中增大聚類系數(shù)可以提高SRW指標(biāo)的預(yù)測效果［7］。蔡彪等人研究了相似性特征對鏈路預(yù)測的影響，利用節(jié)點間標(biāo)簽的相似性提高算法的準(zhǔn)確性［8］。但關(guān)于不同權(quán)重連邊的可預(yù)測性及其影響因素的研究鮮有報道。文章以美國航空網(wǎng)絡(luò)為實證網(wǎng)絡(luò)，針對加權(quán)網(wǎng)絡(luò)中的權(quán)重特性，分析不同權(quán)重連邊的可預(yù)測性和對于鏈路預(yù)測的影響。首先，根據(jù)加權(quán)網(wǎng)絡(luò)的不同性質(zhì)構(gòu)造相應(yīng)的零模型。然后，研究加權(quán)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)和權(quán)重，并分析它們對鏈接預(yù)測的影響。最后將所有關(guān)系分為強(qiáng)弱關(guān)系，并分析不同權(quán)重對鏈接預(yù)測的影響及其在預(yù)測中的作用。

1基于節(jié)點結(jié)構(gòu)信息的鏈路預(yù)測方法

1.1定義與原理

在無權(quán)復(fù)雜網(wǎng)絡(luò)中基于節(jié)點局域信息的常用的鏈路預(yù)測指標(biāo)主要包括CN（common neighbors）、AA（adamic-adar）和RA（resources allocation ）指標(biāo)。為了便于計算可以將其分別拓展為含權(quán)形式［9］：

SWCNxy=∑Z∈Γ（x）∩Γ（y）w（x，c）α+w（z，y）α（1）

SWAAxy=∑Z∈Γ（x）∩Γ（y）w（x，c）α+w（z，y）αlog（1+s（z））（2）

SWRAxy=∑Z∈Γ（x）∩Γ（y）w（x，c）α+w（z，y）αs（z）

（3）

式中，α參數(shù)用于調(diào)節(jié)權(quán)重在預(yù)測中的作用。

1.2加權(quán)網(wǎng)絡(luò)及零模型的構(gòu)造

（1）1階零模型。0階零模型不僅改變了拓?fù)浣Y(jié)構(gòu)，而且改變了原網(wǎng)絡(luò)的度分布，導(dǎo)致了較強(qiáng)的隨機(jī)性［10］。實際上，強(qiáng)大的隨機(jī)性使得0階零模型在研究現(xiàn)實生活網(wǎng)絡(luò)時使用得更少。由于1階零模型保持原始網(wǎng)絡(luò)的程度分布，因此它已被用于富裕俱樂部和社區(qū)的檢測。首先，節(jié)點A和B以及節(jié)點C和D如圖1所示連接，而節(jié)點A和D以及節(jié)點B和C未連接在一起。然后，斷開連接AB和CD，并分別重新連接節(jié)點A和D以及節(jié)點B和C。最后，新增加的鏈路AD（BC）的權(quán)重與原始網(wǎng)絡(luò)中AC（BD）的鏈路權(quán)重相同。一般來說，應(yīng)該強(qiáng)調(diào)的是，需要多次重復(fù)上述過程，直到原始網(wǎng)絡(luò)完全隨機(jī)化。顯然，重復(fù)時間與網(wǎng)絡(luò)的大?。催吘壍臄?shù)量N）相關(guān)，因此在該研究中重復(fù)時間設(shè)置為2*N。

（a）原始網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)（b）隨機(jī)交換兩個邊后，1階零網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)

（2）結(jié)構(gòu)隨機(jī)斷邊重連零模型。1階零網(wǎng)絡(luò)破壞了原始網(wǎng)絡(luò)的結(jié)構(gòu)相關(guān)性和權(quán)重相關(guān)性［10］，因此，基于該模型，兩種相關(guān)性（結(jié)構(gòu)或權(quán)重）中的每一種對鏈路預(yù)測的影響都不能單獨研究。引入結(jié)構(gòu)疏導(dǎo)網(wǎng)絡(luò)，只破壞原有網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，但保有它的權(quán)重分布。具體的構(gòu)建過程如圖2所示。

首先，節(jié)點A和B以及節(jié)點C和D在圖2中連接，而節(jié)點A和D以及節(jié)點B和C未連接。然后，隨機(jī)選擇一對具有相同權(quán)重的鏈接AC和BD。最后，斷開鏈路AC和BD，并分別重新連接節(jié)點A和D以及節(jié)點B和C。整個操作之后，盡管網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)已經(jīng)改變，網(wǎng)絡(luò)中每個節(jié)點的權(quán)重分布仍然保持不變。在一些網(wǎng)絡(luò)中，很難找到足夠的鏈路來解決相同的權(quán)重問題。為了確保盡可能多的邊可以交換，采用另一種方法來交換具有近似權(quán)重的邊。

（3）權(quán)重置亂零模型。除了拓?fù)浣Y(jié)構(gòu)相關(guān)之外，節(jié)點邊緣之間的權(quán)重相關(guān)性是影響復(fù)雜網(wǎng)絡(luò)非平凡性的另一個重要因素。構(gòu)造過程如圖3所示。

首先，隨機(jī)選擇兩個具有不同權(quán)重的邊，例如邊AB和CD。然后，這兩個鏈路的權(quán)重都被消除了，所以現(xiàn)在AB的權(quán)重是2，CD的權(quán)重是3。這里不改變原始網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，而是改變四者的權(quán)重相關(guān)性節(jié)點。由于網(wǎng)絡(luò)的規(guī)模，需要重復(fù)多次以上的操作，以使零網(wǎng)絡(luò)的權(quán)重相關(guān)性足夠隨機(jī)化。連邊之間的權(quán)重置亂是影響網(wǎng)絡(luò)非平凡過程的一個重要因素，連邊AB和CD權(quán)重互換，步驟重復(fù)多次，就可以達(dá)到置亂權(quán)重的目的。權(quán)重置亂零模型只是置亂了權(quán)重并沒有改變網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，并不會改變網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)。

1.3鏈路預(yù)測過程評價方法

（1）AUC評價方法。ROC曲線下的面積（area under the curve，AUC），反映在測試集中的邊的分?jǐn)?shù)值有比隨機(jī)選擇的一個不存在的邊的分?jǐn)?shù)值高的概率，AUC定義為［11］：

AUC=n′+0.5n′n （1）

式（1）中，n為比較的總次數(shù)，n′為測試集中的邊數(shù)的分?jǐn)?shù)值是大于不存在邊的分?jǐn)?shù)值的，n″為連連邊的分?jǐn)?shù)值相等的次數(shù)。

（2）Precision評價方法。Precision評價算法被定義預(yù)測準(zhǔn)確的次數(shù)與L的比值，假設(shè)如果有m個預(yù)測準(zhǔn)確，則Precision定義為［12］：

Precision=mL（2）

2結(jié)果分析

2.1加權(quán)網(wǎng)絡(luò)來源

為了定量檢查加權(quán)復(fù)雜網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)和屬性對鏈路預(yù)測的影響。文章美國航空運輸網(wǎng)絡(luò)（USAir）進(jìn)行研究，該網(wǎng)絡(luò)由332個節(jié)點和2126個鏈路組成。節(jié)點代表機(jī)場，并且鏈路指示路線，鏈路的重量是兩個機(jī)場之間的飛行頻率。該網(wǎng)絡(luò)的權(quán)重分布如圖1所示。

由圖4可以看出，該網(wǎng)絡(luò)的權(quán)重分配遵循長尾分布，也就是說，只有少數(shù)邊緣具有較高的權(quán)重。根據(jù)這個網(wǎng)絡(luò)的權(quán)重，選擇一個閾值將所有邊緣劃分為強(qiáng)關(guān)系和弱關(guān)系，每個邊緣占總邊緣數(shù)量的50％（圖4中的虛線是截斷點）。

2.2拓?fù)浣Y(jié)構(gòu)和權(quán)重相關(guān)性對鏈路預(yù)測的影響

圖5顯示了原始網(wǎng)絡(luò)及其相應(yīng)三個零模型的鏈路預(yù)測結(jié)果。當(dāng)參數(shù)比0h，原始網(wǎng)絡(luò)的準(zhǔn)確性最高，這表明弱鏈接可能在鏈接預(yù)測中發(fā)揮重要作用。在該研究中，考慮了相關(guān)性：權(quán)重相關(guān)性和程度相關(guān)性。1個網(wǎng)絡(luò)只保留原有網(wǎng)絡(luò)的度分布，同時破壞權(quán)重相關(guān)性和度相關(guān)性。因此，1階零網(wǎng)絡(luò)的AUC和精度表現(xiàn)出最低的預(yù)測精度，證明了它具有最強(qiáng)的隨機(jī)性。

AUC和精密結(jié)構(gòu)-整合網(wǎng)絡(luò)僅高于1階模型，這意味著度相關(guān)對鏈接預(yù)測有較強(qiáng)的影響。在權(quán)重調(diào)整網(wǎng)絡(luò)中，只交換兩個邊的權(quán)重，而不改變權(quán)重相關(guān)性，以免改變整個網(wǎng)絡(luò)的鏈接關(guān)系?？梢钥闯?，加權(quán)平滑網(wǎng)絡(luò)中的鏈路預(yù)測結(jié)果與原始網(wǎng)絡(luò)接近，這意味著權(quán)重相關(guān)對鏈路預(yù)測的影響較小。當(dāng)參數(shù)α大于0時，加權(quán)平滑網(wǎng)絡(luò)的AUC和精度要高于原始網(wǎng)絡(luò)的AUC和精度。原因在于，在原有網(wǎng)絡(luò)中存在著很多弱關(guān)系，在權(quán)重增加的情況下，通過回收這些邊的權(quán)重，預(yù)測效果比原始網(wǎng)絡(luò)好。綜上所述，權(quán)重相關(guān)性和程度相關(guān)性都會影響網(wǎng)絡(luò)的鏈接預(yù)測，程度相關(guān)性的影響要比權(quán)重相關(guān)性更強(qiáng)。其他幾個經(jīng)驗網(wǎng)絡(luò)，其基于三個零模型的鏈路預(yù)測結(jié)果以AUC和精度的最大值的形式給出。在這些網(wǎng)絡(luò)中，提供了三個零模型，可以量化拓?fù)浣Y(jié)構(gòu)和權(quán)重相關(guān)性在加權(quán)網(wǎng)絡(luò)的鏈接預(yù)測中。所有1階零模型的結(jié)果都是最差的，權(quán)重靜默模型的預(yù)測結(jié)果要好于結(jié)構(gòu)靜默模型的預(yù)測結(jié)果。

2.2不同權(quán)重連邊的鏈路預(yù)測的影響

2.2.1不同權(quán)重連邊的鏈路預(yù)測結(jié)果" 加權(quán)網(wǎng)絡(luò)和未加權(quán)網(wǎng)絡(luò)之間的顯著差異在于加權(quán)網(wǎng)絡(luò)中的邊緣具有有意義的權(quán)重。權(quán)重在鏈接預(yù)測中的作用是值得考慮的問題，尤其是在權(quán)重鏈接預(yù)測中是否存在弱關(guān)系的強(qiáng)大影響。針對這個問題，按降序?qū)λ羞厵?quán)重進(jìn)行排序，在圖6中，前50％被認(rèn)為是強(qiáng)關(guān)聯(lián)，另外50％被認(rèn)為是弱關(guān)聯(lián)。文章隨機(jī)選擇了一半邊的鏈接預(yù)測。根據(jù)圖6中的AUC和Precision的結(jié)果，在α=-0.5＜0時可以獲得最高的性能，這意味著USAir網(wǎng)絡(luò)存在“弱關(guān)系的強(qiáng)大影響”。因為當(dāng)α＜0時，弱關(guān)系的權(quán)重變大，原始網(wǎng)絡(luò)的結(jié)果最準(zhǔn)確，表明弱關(guān)聯(lián)性強(qiáng)預(yù)測性強(qiáng)。而且，強(qiáng)大的鏈路執(zhí)行最高的準(zhǔn)確性，而弱化的鏈路執(zhí)行最低的性能。因此，具有較高權(quán)重（強(qiáng)關(guān)系）的邊緣比具有較小權(quán)重（弱關(guān)系）的邊緣更容易被預(yù)測。

2.2.2不同權(quán)重連邊對鏈路預(yù)測的影響" 通過對網(wǎng)絡(luò)中的一些連邊進(jìn)行1階置亂，按照上述的鏈路預(yù)測方法進(jìn)行預(yù)測，觀察不同權(quán)重遍的鏈路預(yù)測結(jié)果，具體結(jié)果如圖7所示。

圖7顯示，對網(wǎng)絡(luò)中隨機(jī)選取的連邊進(jìn)行1階置亂后不同權(quán)重的鏈路預(yù)測結(jié)果。圖中的藍(lán)色線代表原始網(wǎng)絡(luò)的結(jié)果，黑色線代表強(qiáng)連邊的預(yù)測結(jié)果，綠色線代表弱連邊對應(yīng)的結(jié)果，紅色線代表原始網(wǎng)絡(luò)的1階置亂零模型的預(yù)測結(jié)果。從圖7可以看出，隨機(jī)置亂部分連邊后，弱連邊置亂后的預(yù)測結(jié)果要低于其他連邊置亂后的網(wǎng)絡(luò)的預(yù)測結(jié)果，說明網(wǎng)絡(luò)中還是弱連接起作用。

3結(jié)語

加權(quán)網(wǎng)絡(luò)的一個最重要的屬性是拓?fù)錂?quán)重相關(guān)性。為了測試這個屬性并區(qū)分鏈接預(yù)測中的拓?fù)浜蜋?quán)重之間的作用，文章構(gòu)建了一個加密復(fù)雜網(wǎng)絡(luò)中的零模型。它可以用來檢測加權(quán)復(fù)雜網(wǎng)絡(luò)中拓?fù)錂?quán)重的相關(guān)性，該框架可以用來定量檢測鏈路預(yù)測中拓?fù)浜蜋?quán)值的作用。通過經(jīng)驗網(wǎng)絡(luò)的實驗可以看出，這些網(wǎng)絡(luò)中存在一個拓?fù)錂?quán)重關(guān)聯(lián)，并且這個拓?fù)浣Y(jié)構(gòu)在重量上對重量進(jìn)行了預(yù)測。權(quán)重是加權(quán)網(wǎng)絡(luò)的一個重要特征，也是不同加權(quán)關(guān)系對鏈路預(yù)測的影響，將所有關(guān)系分為強(qiáng)弱關(guān)系。結(jié)果表明，當(dāng)網(wǎng)絡(luò)具有較強(qiáng)的節(jié)點強(qiáng)度協(xié)調(diào)性時，網(wǎng)絡(luò)預(yù)測結(jié)果相對較高，不受權(quán)值變化的影響。這個通用框架被可以更準(zhǔn)確地描述網(wǎng)絡(luò)的特征，并用來改善加權(quán)復(fù)雜網(wǎng)絡(luò)中其他應(yīng)用的性能。

參考文獻(xiàn)：

［1］陳廣福，劉奇，李曉飛.融合權(quán)重和結(jié)構(gòu)的加權(quán)非負(fù)矩陣分解的鏈路預(yù)測［J］.西華大學(xué)學(xué)報（自然科學(xué)版），2022，41（4）：57.

［2］陳廣福，韓輝珍.基于鄰域結(jié)構(gòu)和對稱非負(fù)矩陣分解的加權(quán)網(wǎng)絡(luò)鏈路預(yù)測［J］.微電子學(xué)與計算機(jī)，2022，39（5）：62.

［3］傅馨玉，顧益軍.融合節(jié)點重要性的無監(jiān)督鏈路預(yù)測算法［J］.計算機(jī)工程與應(yīng)用，2022，58（16）：94.

［4］袁榕，宋玉蓉，孟繁榮.一種基于加權(quán)網(wǎng)絡(luò)拓?fù)錂?quán)重的鏈路預(yù)測方法［J］.計算機(jī)科學(xué)，2020，47（5）：265.

［5］萬楊曄，郭進(jìn)利.基于資源分配與圖嵌入加權(quán)的鏈路預(yù)測算法［J］.計算機(jī)與現(xiàn)代化，2021，37（7）：12.

［6］楊曉翠，宋甲秀，張曦煌.基于集體影響和邊聚類信息的鏈路預(yù)測算法［J］.計算機(jī)科學(xué)與探索，2018，12（12）：1914.

［7］張斌，李亞婷，戴怡清.聚集系數(shù)對合著網(wǎng)絡(luò)鏈路預(yù)測效果的影響研究［J］.情報理論與實踐，2018，41（1）：100.

［8］蔡彪，李蕊岑，吳媛媛.相似性特征對鏈路預(yù)測的影響與增強(qiáng)［J］.計算機(jī)應(yīng)用，2021，41（9）：2569.

［9］楊旭華，王磊，葉蕾，等.基于節(jié)點相似性和網(wǎng)絡(luò)嵌入的復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法［J］.計算機(jī)科學(xué)，2022，49（3）：121.

［10］尚可可，許小可.基于置亂算法的復(fù)雜網(wǎng)絡(luò)零模型構(gòu)造及其應(yīng)用本期“復(fù)雜性科學(xué)”專欄評述［J］.電子科技大學(xué)學(xué)報，2014，43（1）：7.

［11］王文強(qiáng)，張千明.鏈路預(yù)測的網(wǎng)絡(luò)演化模型評價方法［J］.電子科技大學(xué)學(xué)報，2011，40（2）：174.

［12］姜禹，胡愛群，潘婷婷.基于鏈路重要性的分布式網(wǎng)絡(luò)可靠性評價方法［J］.東南大學(xué)學(xué)報（自然科學(xué)版），2008，10（4）：547.

Research on Weighted Network Link Prediction Factors Based on

Zero Model

LIANG Xichen

（Suzhou Vocationed and Technical college，Suzhou，Anhui 234，China）

ABSTRACT" Based on the zero model， this paper studied how to quantitatively analyze the influencing factors of link prediction in weighted Complex network. By constructing a first-order zero model and a weight scrambling zero model， the structural scrambling zero model was studied in terms of topology and weight correlation. Using the US aviation network as an empirical network， analyzed the predictability of different weight connections and their impact on link prediction based on the weight characteristics of the weighted network. The results indicate that there was topological weight correlation in the US aviation network， and the impact of broken topology on link prediction was greater than that of broken weight correlation. At the same time， there was a phenomenon in the US aviation network where weak links play a strong role， known as the weak link theory， which had also been proven through further experiments.

KEY WORDS" complex network； weighted complex network； zero model； link prediction

（責(zé)任編輯" 胡安娜）