基于節(jié)點(diǎn)匹配度的動(dòng)態(tài)網(wǎng)絡(luò)鏈路預(yù)測(cè)方法

李聰，季新生，劉樹(shù)新，李勁松，李海濤

基于節(jié)點(diǎn)匹配度的動(dòng)態(tài)網(wǎng)絡(luò)鏈路預(yù)測(cè)方法

李聰，季新生，劉樹(shù)新，李勁松，李海濤

（信息工程大學(xué)，河南 鄭州 450001）

現(xiàn)實(shí)世界存在眾多真實(shí)網(wǎng)絡(luò)，研究真實(shí)網(wǎng)絡(luò)中的動(dòng)態(tài)演化趨勢(shì)和時(shí)序性特征是熱點(diǎn)問(wèn)題。鏈路預(yù)測(cè)技術(shù)作為網(wǎng)絡(luò)科學(xué)領(lǐng)域重要研究工具可通過(guò)挖掘歷史連邊信息推測(cè)網(wǎng)絡(luò)演化規(guī)律，進(jìn)而對(duì)未來(lái)連邊進(jìn)行預(yù)測(cè)。通過(guò)分析動(dòng)態(tài)真實(shí)網(wǎng)絡(luò)中的拓?fù)浣Y(jié)構(gòu)演化，發(fā)現(xiàn)通過(guò)分析網(wǎng)絡(luò)拓?fù)渲泄?jié)點(diǎn)間的交互性和匹配度問(wèn)題能夠更充分捕捉網(wǎng)絡(luò)的動(dòng)態(tài)特征，提出一種基于節(jié)點(diǎn)匹配度的動(dòng)態(tài)網(wǎng)絡(luò)鏈路預(yù)測(cè)方法。該方法對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)的屬性特征進(jìn)行分析，定義基于原生影響力和次生影響力的節(jié)點(diǎn)重要性量化方法；引入時(shí)間衰減因子，刻畫(huà)不同時(shí)刻網(wǎng)絡(luò)拓?fù)鋵?duì)連邊形成的影響程度；結(jié)合節(jié)點(diǎn)重要性和時(shí)間衰減因子定義動(dòng)態(tài)節(jié)點(diǎn)匹配度（TMDN，temporal matching degree of nodes）方法，用于衡量節(jié)點(diǎn)對(duì)之間未來(lái)形成連邊的可能性。在5個(gè)真實(shí)動(dòng)態(tài)網(wǎng)絡(luò)數(shù)據(jù)集中的實(shí)驗(yàn)結(jié)果表明，相比現(xiàn)有3類(lèi)主流動(dòng)態(tài)網(wǎng)絡(luò)鏈路預(yù)測(cè)方法，所提方法在AUC和Ranking Score兩種評(píng)價(jià)標(biāo)準(zhǔn)下均取得更優(yōu)的預(yù)測(cè)性能，預(yù)測(cè)結(jié)果最高提升42%，證明了節(jié)點(diǎn)間存在著交互匹配優(yōu)先級(jí)，同時(shí)證實(shí)了節(jié)點(diǎn)原生影響力和次生影響力的有效性。

動(dòng)態(tài)網(wǎng)絡(luò)；鏈路預(yù)測(cè)；節(jié)點(diǎn)匹配度；節(jié)點(diǎn)重要性；時(shí)間衰減因子

0 引言

隨著社會(huì)學(xué)[1]、生物學(xué)[2]、醫(yī)學(xué)[3]以及互聯(lián)網(wǎng)技術(shù)[4]的飛速發(fā)展，復(fù)雜網(wǎng)絡(luò)[5]被廣泛應(yīng)用于復(fù)雜系統(tǒng)的抽象化表示、形式化分析與深度挖掘等，極大地推動(dòng)了網(wǎng)絡(luò)科學(xué)的蓬勃發(fā)展。復(fù)雜系統(tǒng)[6]中的個(gè)體，如人類(lèi)、細(xì)胞、基站、路由器等可以看成實(shí)體，在網(wǎng)絡(luò)拓?fù)渲杏霉?jié)點(diǎn)表示，節(jié)點(diǎn)之間的連邊用來(lái)描述實(shí)體之間的關(guān)系[7]。鏈路預(yù)測(cè)作為研究復(fù)雜科學(xué)的重要技術(shù)之一，已成為近年來(lái)的研究熱點(diǎn)問(wèn)題[8-11]。鏈路預(yù)測(cè)技術(shù)旨在利用復(fù)雜系統(tǒng)中已觀測(cè)的結(jié)構(gòu)信息、屬性信息等，發(fā)現(xiàn)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中的缺失連邊，以及推測(cè)未來(lái)可能形成的連邊[12]。鏈路預(yù)測(cè)為生物學(xué)、醫(yī)學(xué)、計(jì)算機(jī)網(wǎng)絡(luò)、社會(huì)科學(xué)等領(lǐng)域的研究提供了強(qiáng)大的技術(shù)支持。通過(guò)對(duì)大量節(jié)點(diǎn)之間復(fù)雜關(guān)系的挖掘可清晰地分析網(wǎng)絡(luò)結(jié)構(gòu)，發(fā)現(xiàn)網(wǎng)絡(luò)中連邊的演化趨勢(shì)[13]，實(shí)現(xiàn)對(duì)未來(lái)連邊的預(yù)測(cè)。例如，通過(guò)分析社交群體近期的社交活動(dòng)，利用鏈路預(yù)測(cè)技術(shù)尋找未來(lái)可能發(fā)生的詐騙、推銷(xiāo)等異常行為。

近年來(lái)，社交網(wǎng)絡(luò)分析在各行各業(yè)中引起了相當(dāng)大的關(guān)注，被廣泛應(yīng)用于市場(chǎng)營(yíng)銷(xiāo)、業(yè)務(wù)流程建模及傳染病模型。鏈路預(yù)測(cè)作為社交網(wǎng)絡(luò)分析的重要手段能夠捕捉社交網(wǎng)絡(luò)信息，及時(shí)發(fā)現(xiàn)新的節(jié)點(diǎn)和連接?，F(xiàn)實(shí)中的社交網(wǎng)絡(luò)由個(gè)體及個(gè)體間復(fù)雜關(guān)系組成，是一個(gè)高度動(dòng)態(tài)變化的網(wǎng)絡(luò)。通過(guò)鏈路預(yù)測(cè)從已知的網(wǎng)絡(luò)結(jié)構(gòu)中尋找和檢測(cè)隱藏的連邊和節(jié)點(diǎn)，可進(jìn)行異常節(jié)點(diǎn)挖掘、重要連邊預(yù)測(cè)等，映射到真實(shí)社交網(wǎng)絡(luò)中可識(shí)別詐騙信息。當(dāng)前，對(duì)于靜態(tài)網(wǎng)絡(luò)的鏈路預(yù)測(cè)技術(shù)研究已經(jīng)相當(dāng)成熟，文獻(xiàn)[14]詳細(xì)對(duì)比分析了各種方法，將其在局部和全局兩個(gè)維度進(jìn)行歸類(lèi)。對(duì)于動(dòng)態(tài)網(wǎng)絡(luò)的研究也在近幾年發(fā)展迅速。Ahmed等[15]提出一種通過(guò)集成網(wǎng)絡(luò)中的時(shí)間信息、社區(qū)結(jié)構(gòu)和節(jié)點(diǎn)中心性進(jìn)行動(dòng)態(tài)網(wǎng)絡(luò)鏈預(yù)測(cè)的方法，通過(guò)節(jié)點(diǎn)在社區(qū)中的交互情況構(gòu)造特征向量來(lái)預(yù)測(cè)節(jié)點(diǎn)未來(lái)的重要性。Günes等[16]提出了一種演進(jìn)網(wǎng)絡(luò)的鏈路預(yù)測(cè)方法，先計(jì)算過(guò)去不同時(shí)間段的網(wǎng)絡(luò)結(jié)構(gòu)中不同節(jié)點(diǎn)的相似性得分，再通過(guò)時(shí)間序列預(yù)測(cè)模型ARIMA來(lái)預(yù)測(cè)未來(lái)節(jié)點(diǎn)的連邊情況。Ahmed等[17]提出了一種針對(duì)時(shí)間不確定網(wǎng)絡(luò)的鏈路方法，首先將不確定網(wǎng)絡(luò)中的鏈路預(yù)測(cè)問(wèn)題轉(zhuǎn)化為確定網(wǎng)絡(luò)的隨機(jī)游走問(wèn)題，然后在子圖中計(jì)算節(jié)點(diǎn)與鄰居之間的相似性分?jǐn)?shù)。針對(duì)異構(gòu)網(wǎng)絡(luò)，Sett等[18]結(jié)合多域拓?fù)涮卣骱蜁r(shí)間維度，提出一種TMLP算法，利用二元交互情況和圖拓?fù)涮卣髯兓闆r，結(jié)合時(shí)間序列模型進(jìn)行預(yù)測(cè)。但上述方法通過(guò)轉(zhuǎn)化成靜態(tài)圖或考慮局部特征，容易丟失動(dòng)態(tài)網(wǎng)絡(luò)中重要拓?fù)湫畔ⅲ绊戭A(yù)測(cè)精度。

本文通過(guò)捕捉歷史拓?fù)涮卣?，并將其作為?jié)點(diǎn)相似度的依據(jù)，提出一種基于節(jié)點(diǎn)匹配度的動(dòng)態(tài)網(wǎng)絡(luò)鏈路預(yù)測(cè)方法。該方法根據(jù)節(jié)點(diǎn)原生重要性和次生重要性定義節(jié)點(diǎn)匹配度，用于衡量節(jié)點(diǎn)間未來(lái)產(chǎn)生交互的可能性。進(jìn)而結(jié)合網(wǎng)絡(luò)拓?fù)涞臍v史變化特征及時(shí)間影響力，捕捉網(wǎng)絡(luò)拓?fù)涞膭?dòng)態(tài)信息。實(shí)驗(yàn)結(jié)果表明，本文所提方法在動(dòng)態(tài)網(wǎng)絡(luò)鏈路預(yù)測(cè)方面相比現(xiàn)有方法取得更優(yōu)的效果。

1 相關(guān)工作

1) 任意節(jié)點(diǎn)不能形成自閉環(huán)；

2) 任意節(jié)點(diǎn)之間最多只能含有一條邊；

3) 節(jié)點(diǎn)間的交互無(wú)方向；

4) 連邊只代表節(jié)點(diǎn)之間關(guān)系的存在。

2 方法介紹

原生能力[19]與次生能力[20]在現(xiàn)實(shí)生活中無(wú)處不在，大到生態(tài)系統(tǒng)，小至單一細(xì)胞，近些年頻發(fā)的自然災(zāi)害也會(huì)造成原生災(zāi)難[21]和次生災(zāi)難[22]。例如，在社交網(wǎng)絡(luò)中，有些個(gè)體天生擅長(zhǎng)某些事物，稱(chēng)之為原生能力；個(gè)體具備依托已存關(guān)系而帶動(dòng)新關(guān)系形成的能力，此能力建立在原生能力的基礎(chǔ)上，稱(chēng)之為次生能力。復(fù)雜網(wǎng)絡(luò)作為真實(shí)網(wǎng)絡(luò)的抽象，需準(zhǔn)確刻畫(huà)真實(shí)網(wǎng)絡(luò)的網(wǎng)絡(luò)特性及個(gè)體屬性。在網(wǎng)絡(luò)拓?fù)渲忻枋鰧?shí)體的節(jié)點(diǎn)應(yīng)反映出實(shí)體的原生能力和次生能力。度是衡量節(jié)點(diǎn)重要性[23]的指標(biāo)，是真實(shí)網(wǎng)絡(luò)中實(shí)體原生能力在復(fù)雜網(wǎng)絡(luò)中的抽象表現(xiàn)，在網(wǎng)絡(luò)拓?fù)渲锌勺鳛楣?jié)點(diǎn)原生能力的體現(xiàn)。例如，在社交網(wǎng)絡(luò)中，節(jié)點(diǎn)度高的節(jié)點(diǎn)之間更容易形成連接；在食物鏈網(wǎng)絡(luò)中，節(jié)點(diǎn)度高象征著在食物鏈中的等級(jí)高，這部分節(jié)點(diǎn)更傾向于與節(jié)點(diǎn)度低的實(shí)體形成連邊。在網(wǎng)絡(luò)拓?fù)渲?，?jié)點(diǎn)的度是由節(jié)點(diǎn)自身性質(zhì)決定的，而連邊是在節(jié)點(diǎn)度的基礎(chǔ)上產(chǎn)生的，兩者是真實(shí)系統(tǒng)中原生與次生邏輯關(guān)系的抽象。作為節(jié)點(diǎn)的次生產(chǎn)物[24]，連邊影響力被多次提起。連邊具有帶動(dòng)新連邊形成的能力，此能力決定于節(jié)點(diǎn)本身，這正是真實(shí)網(wǎng)絡(luò)中次生能力的抽象，在網(wǎng)絡(luò)拓?fù)渲?，稱(chēng)之為節(jié)點(diǎn)的次生能力。本文根據(jù)節(jié)點(diǎn)原生能力和次生能力定義節(jié)點(diǎn)原生重要性和次生重要性，并結(jié)合兩者提出節(jié)點(diǎn)匹配度的概念。

2.1 節(jié)點(diǎn)重要性

對(duì)于節(jié)點(diǎn)重要性的衡量可從節(jié)點(diǎn)自身和鄰域拓?fù)鋬蓚€(gè)角度加以考察。連邊是基于節(jié)點(diǎn)性質(zhì)而形成的，可看作節(jié)點(diǎn)的次生產(chǎn)物。在復(fù)雜網(wǎng)絡(luò)中，節(jié)點(diǎn)度可用于衡量節(jié)點(diǎn)在網(wǎng)絡(luò)中的重要性程度，其可以解釋為節(jié)點(diǎn)周?chē)B邊貢獻(xiàn)的和[25]。然而，節(jié)點(diǎn)度將每條邊的貢獻(xiàn)程度設(shè)為1，無(wú)法區(qū)分不同邊的連接能力[25]，因此，本文用連邊連接能力刻畫(huà)該貢獻(xiàn)程度，定義節(jié)點(diǎn)次生重要性。

下面討論連邊連接能力的量化問(wèn)題。通常情況下，復(fù)雜網(wǎng)絡(luò)中連邊的形成不是隨機(jī)的，而是具有特定傾向性。該傾向性在無(wú)標(biāo)度網(wǎng)絡(luò)中通?？捎谩皟?yōu)先連接（PA，preferential attachment）[26]”機(jī)制解釋。該機(jī)制描述了復(fù)雜網(wǎng)絡(luò)中“富者越富，強(qiáng)者越強(qiáng)”的現(xiàn)象。對(duì)于一條連邊而言，可利用優(yōu)先連接機(jī)制刻畫(huà)其連接能力。傳統(tǒng)PA方法只考慮端節(jié)點(diǎn)度的乘積，對(duì)網(wǎng)絡(luò)中三角形結(jié)構(gòu)具有的貢獻(xiàn)能力未做區(qū)分。

三角形結(jié)構(gòu)[27]穩(wěn)定性強(qiáng)，結(jié)構(gòu)不容易發(fā)生改變，是復(fù)雜網(wǎng)絡(luò)中最為穩(wěn)定的局部結(jié)構(gòu)之一。穩(wěn)定性強(qiáng)則意味著結(jié)構(gòu)不容易發(fā)生改變，在動(dòng)態(tài)網(wǎng)絡(luò)中則意味著連邊不會(huì)隨時(shí)間的變化而輕易消失。

圖1 不同時(shí)刻網(wǎng)絡(luò)拓?fù)鋱D示例1

Figure 1 Example of network topology diagram 1 at different times

圖2 不同時(shí)刻網(wǎng)絡(luò)拓?fù)鋱D示例2

Figure 2 Example of network topology diagram 2 at different times

圖3 第時(shí)刻網(wǎng)絡(luò)拓?fù)渥訄D

基于上述分析，本文考慮三角形結(jié)構(gòu)與非三角形結(jié)構(gòu)的貢獻(xiàn)區(qū)別，基于PA指標(biāo)定義連邊的連接能力，如下：

圖3中通過(guò)上述方法可計(jì)算得出

圖4 第時(shí)刻網(wǎng)絡(luò)拓?fù)渥訄D

在圖4中，有

上述定義考慮了節(jié)點(diǎn)原生重要性和節(jié)點(diǎn)次生重要性，并對(duì)節(jié)點(diǎn)間單個(gè)節(jié)點(diǎn)重要性進(jìn)行量化，因而對(duì)節(jié)點(diǎn)重要性的刻畫(huà)更加合理。在圖4所示的拓?fù)渥訄D中可以看到，通過(guò)此方法計(jì)算得到的節(jié)點(diǎn)重要性數(shù)值為

2.2 節(jié)點(diǎn)匹配度

節(jié)點(diǎn)重要性決定節(jié)點(diǎn)的影響力，在實(shí)際網(wǎng)絡(luò)中，影響力大的個(gè)體捕獲資源和信息的能力更強(qiáng)。Wang等[28]提出，在電網(wǎng)中，每個(gè)電站都具有有限負(fù)載和有限容量，而節(jié)點(diǎn)的承載能力決定了電站的負(fù)載和容量，重要的節(jié)點(diǎn)會(huì)承載更多的負(fù)載，與其他節(jié)點(diǎn)的匹配能力[29]會(huì)更強(qiáng)。綜合以上情形，給出節(jié)點(diǎn)匹配度的定義，用于刻畫(huà)拓?fù)浣Y(jié)構(gòu)中節(jié)點(diǎn)間產(chǎn)生連邊的概率。

2.3 時(shí)間衰減因子

結(jié)合衰減因子，節(jié)點(diǎn)匹配度的定義如下。

3 衡量標(biāo)準(zhǔn)及數(shù)據(jù)集

3.1 對(duì)比方法介紹

（1）傳統(tǒng)方法

共同鄰居（CN，common nodes）方法[31]：以?xún)晒?jié)點(diǎn)之間共同鄰居數(shù)量為衡量標(biāo)準(zhǔn)，數(shù)學(xué)公式表示為

Adamic-Adar（AA）方法[32]：此方法是建立在共同鄰居的基礎(chǔ)上的，即兩節(jié)點(diǎn)的共同鄰居度越大，則兩節(jié)點(diǎn)之間的相似性分?jǐn)?shù)越高，數(shù)學(xué)公式表示為

資源分配（RA，resource allocation）方法[33]：RA與AA有異曲同工之妙，兩者的思想相同，只是賦予節(jié)點(diǎn)權(quán)重的方式不同，數(shù)學(xué)表達(dá)式為

局部路徑（LP，local path）方法[34]：將三階路徑考慮進(jìn)來(lái)，數(shù)學(xué)表達(dá)式為

（2）拓展方法

①基于時(shí)間序列的拓展方法

首先將在時(shí)刻觀察到的網(wǎng)絡(luò)劃分成多個(gè)時(shí)間分段的快照，然后定義一個(gè)預(yù)測(cè)窗口，將這些時(shí)間快照按照窗口長(zhǎng)度進(jìn)行劃分。

利用相似性指標(biāo)計(jì)算每個(gè)子圖上節(jié)點(diǎn)對(duì)的相似性分?jǐn)?shù)，構(gòu)造時(shí)間序列，利用平均預(yù)測(cè)模型，得到相似性分?jǐn)?shù)。預(yù)測(cè)模型為

此類(lèi)拓展方法用TCN、TAA、TRA、TLP[35]表示。

②基于時(shí)間因子的拓展方法

Güne?等[16]將時(shí)間因子應(yīng)用于相似性方法內(nèi)，結(jié)合時(shí)間因子，網(wǎng)絡(luò)的鄰接矩陣表示為

相應(yīng)的拓展方法為

3.2 算法評(píng)價(jià)標(biāo)準(zhǔn)

RS對(duì)所有未連邊按照相似分值大小排序，得到測(cè)試集的邊在最終排序中的位置，測(cè)試集連邊排名越高，排序分值越小時(shí)，說(shuō)明該算法具有越好預(yù)測(cè)性能。以為未連邊的集合（測(cè)試集中和不存在邊集的集合），網(wǎng)絡(luò)中某條測(cè)試邊的RS為

整個(gè)網(wǎng)絡(luò)的平均RS可通過(guò)遍歷求和得到，計(jì)算方式如下。

3.3 數(shù)據(jù)集

通過(guò)調(diào)研近兩年文獻(xiàn)，發(fā)現(xiàn)多數(shù)文獻(xiàn)選擇郵件數(shù)據(jù)集進(jìn)行算法性能對(duì)比。為驗(yàn)證所提方法的性能，使其更具有說(shuō)服力，本文選用5個(gè)來(lái)自不同領(lǐng)域的真實(shí)動(dòng)態(tài)網(wǎng)絡(luò)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。5個(gè)真實(shí)數(shù)據(jù)集的基本特征參數(shù)如表1所示。以下詳細(xì)介紹各數(shù)據(jù)集的具體信息。

（1）DNC emails（DNC）[36]：由 2016 年美國(guó)民主黨全國(guó)委員會(huì)郵件泄露事件中采集的郵件往來(lái)網(wǎng)絡(luò)，其節(jié)點(diǎn)表示郵件賬號(hào)，有向邊表示某賬號(hào)發(fā)往另一賬號(hào)的郵件。

（2）Manufacturing emails（MAN）[36]：一個(gè)制造業(yè)工廠內(nèi)部員工的郵件往來(lái)網(wǎng)絡(luò)。屬于動(dòng)態(tài)網(wǎng)絡(luò)，其中節(jié)點(diǎn)表示員工賬號(hào)，有向邊表示在某一時(shí)刻由員工之間發(fā)送的郵件。

（3）LevantMonths（LEM）[37]：一個(gè)由堪薩斯事件數(shù)據(jù)系統(tǒng)基于包含WEIS編碼事件的文件夾收集的交互網(wǎng)絡(luò)，其中包含8個(gè)國(guó)家之間的交互信息。原始數(shù)據(jù)集涵蓋了1979年4月至2004年6月的事件。

（4）Email-Eu-core-temporal（EEC）[38]：一個(gè)由歐洲某大型研究機(jī)構(gòu)內(nèi)部郵件往來(lái)數(shù)據(jù)構(gòu)成的有向網(wǎng)絡(luò)。節(jié)點(diǎn)表示郵件賬號(hào)，有向邊表示某一賬號(hào)在某時(shí)刻發(fā)往另一賬號(hào)的郵件。根據(jù)數(shù)據(jù)來(lái)源，原始數(shù)據(jù)集包含若干子數(shù)據(jù)集，代表研究機(jī)構(gòu)內(nèi)不同部門(mén)的郵件往來(lái)。本文選用其中的email-Eu-core-temporal-Dept1（EEC1）和email-Eu- core-temporal-Dept2（EEC2）。由于原始數(shù)據(jù)集的時(shí)間戳起始于0，確切起始日期無(wú)法確定。

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

為驗(yàn)證所提TMDN在真實(shí)數(shù)據(jù)集中的預(yù)測(cè)效果，本文通過(guò)對(duì)比實(shí)驗(yàn)分析了TMDN在不同參數(shù)、時(shí)刻下AUC和RS結(jié)果，具體分析如下。

4.1 平均性能對(duì)比

4.1.1 AUC評(píng)價(jià)方法

首先研究所提TMDN方法在AUC衡量標(biāo)準(zhǔn)下的性能。圖5為T(mén)MDN和現(xiàn)有方法在真實(shí)數(shù)據(jù)集中的AUC對(duì)比結(jié)果?？梢钥闯?，與其他指標(biāo)相比，TMDN指標(biāo)在5個(gè)網(wǎng)絡(luò)中均取得了較高的預(yù)測(cè)精度。CN、TCN、TF_CN僅考慮了二階鄰居數(shù)目，在AUC評(píng)價(jià)標(biāo)準(zhǔn)下結(jié)果普遍一般，但在MAN中，CN明顯高于AA、RA和全局指標(biāo)LP，預(yù)測(cè)效果僅次于本文的指標(biāo)，TCN也優(yōu)于TAA、TRA、TLP；而加入時(shí)間因素的拓展指標(biāo)性能沒(méi)有展示出優(yōu)勢(shì)，性能表現(xiàn)整體不如傳統(tǒng)指標(biāo)，造成此現(xiàn)象的原因是MAN數(shù)據(jù)集動(dòng)態(tài)特性不明顯，考慮時(shí)間因素的拓展方法無(wú)法發(fā)揮性能優(yōu)勢(shì)。在MAN數(shù)據(jù)集中，CN指標(biāo)優(yōu)勢(shì)明顯，說(shuō)明此數(shù)據(jù)集局部特征明顯，局部指標(biāo)可發(fā)揮出性能優(yōu)勢(shì)，而考慮共同鄰居的AA、RA不及CN，說(shuō)明該數(shù)據(jù)集共同鄰居特征不明顯。AA、RA及其拓展指標(biāo)考慮了共同鄰居節(jié)點(diǎn)度，也表現(xiàn)出了不錯(cuò)的預(yù)測(cè)效果，在DNC、LEM、EEC1、EEC2這4個(gè)網(wǎng)絡(luò)中預(yù)測(cè)效果明顯優(yōu)于CN。而考慮全局信息的LP及其拓展方法TLP、TF_LP，在大部分網(wǎng)絡(luò)中表現(xiàn)出了較高的預(yù)測(cè)精度，甚至在EEC2網(wǎng)絡(luò)中，LP、TLP的AUC得分強(qiáng)于TMDN，加入時(shí)間因子，將網(wǎng)絡(luò)的動(dòng)態(tài)信息考慮進(jìn)來(lái)，全局方法TF_LP明顯高于局部方法TF_CN、TF_AA和TF_RA。整體而言，拓展方法表現(xiàn)優(yōu)于傳統(tǒng)方法，具體到數(shù)據(jù)集中表現(xiàn)卻參差不齊，這是由于動(dòng)態(tài)特性只是動(dòng)態(tài)網(wǎng)絡(luò)的一個(gè)特征，還要考慮其局部特征和全局特征等多個(gè)因素，在一些動(dòng)態(tài)特性較高的網(wǎng)絡(luò)中，會(huì)出現(xiàn)拓展方法低于傳統(tǒng)方法的現(xiàn)象，所以，算法的普適性也是衡量指標(biāo)性能的重要標(biāo)準(zhǔn)。

表1 5個(gè)真實(shí)數(shù)據(jù)集的基本特征參數(shù)

在考慮節(jié)點(diǎn)匹配度后，TMDN預(yù)測(cè)效果明顯領(lǐng)先，說(shuō)明現(xiàn)實(shí)網(wǎng)絡(luò)連邊構(gòu)建中均存在一定程度的匹配傾向性。同樣考慮共同鄰居間存在的社團(tuán)關(guān)系，TMDN在5個(gè)網(wǎng)絡(luò)中的預(yù)測(cè)效果均優(yōu)于局部相似性方法及拓展方法TCN、TF_CN、TAA、TF_AA、TRA、TF_RA，且提升精度在1%～33%。相比全局方法LP、TLP、TF_LP，在DNC、MAN、LEM中同樣有較高的提升，提升比例為1%～42%，但在EEC2中，本文的方法效果不如LP和TLP?？傮w上，相比其他方法，TMDN方法的平均提升比率為19.3%，最高提升比例為42%。

圖5 不同方法的平均AUC性能

Figure 5 Average AUC performance of different methods

4.1.2 RS評(píng)價(jià)方法

本節(jié)在RS衡量標(biāo)準(zhǔn)下對(duì)TMDN的性能進(jìn)行對(duì)比分析。圖6為T(mén)MDN與其他方法在5個(gè)真實(shí)網(wǎng)絡(luò)中的RS對(duì)比結(jié)果。

圖6 不同方法的平均RS性能對(duì)比

Figure 6 Comparison of average RS performance of different methods

相比其他相似性方法，本文所提TMDN在5個(gè)網(wǎng)絡(luò)中均有較優(yōu)的性能。與AUC結(jié)果不同，局部相似性方法及拓展方法在不同網(wǎng)絡(luò)中表現(xiàn)各異，某些網(wǎng)絡(luò)中CN表現(xiàn)較好，而在另一些網(wǎng)絡(luò)中則表現(xiàn)較差?？紤]共同鄰居節(jié)點(diǎn)度的AA、RA方法，在AUC衡量標(biāo)準(zhǔn)下展現(xiàn)出了一定的優(yōu)勢(shì)，而在RS衡量標(biāo)準(zhǔn)下卻表現(xiàn)出了較差的性能，僅在LEM中預(yù)測(cè)性能高于CN。在大部分網(wǎng)絡(luò)中，結(jié)合時(shí)間因素的局部拓展方法性能較傳統(tǒng)方法有所提升，這說(shuō)明在動(dòng)態(tài)網(wǎng)絡(luò)中，傳統(tǒng)方法可能會(huì)忽略網(wǎng)絡(luò)結(jié)構(gòu)的動(dòng)態(tài)特性，導(dǎo)致預(yù)測(cè)結(jié)果不佳。而這些局部方法性能表現(xiàn)各異，說(shuō)明共同鄰居節(jié)點(diǎn)本身信息的利用對(duì)于刻畫(huà)動(dòng)態(tài)網(wǎng)絡(luò)結(jié)構(gòu)特征的貢獻(xiàn)難以界定，像AA、RA這些考慮了鄰居節(jié)點(diǎn)度的額外因素并非一定會(huì)起到正面促進(jìn)作用。全局指標(biāo)LP、TLP、TF_LP在一些網(wǎng)絡(luò)中表現(xiàn)出了較為穩(wěn)定的預(yù)測(cè)性能，但在MAN中LP和TLP的預(yù)測(cè)效果卻最差，說(shuō)明基于全局信息的方法難以概述動(dòng)態(tài)網(wǎng)絡(luò)的全部屬性，導(dǎo)致預(yù)測(cè)性能存在未知性。

TMDN方法在5個(gè)網(wǎng)絡(luò)中均表現(xiàn)出較好的性能，RS得分普遍低于其他指標(biāo)。在DNC和MAN網(wǎng)絡(luò)中性能提升明顯，相比其他指標(biāo)，TMDN的預(yù)測(cè)性能最高提升了49.6%，在DNC中，TF_RA展現(xiàn)出了不俗的預(yù)測(cè)精度，RS得分甚至低于TMDN，但也僅僅低0.01。在其他3個(gè)網(wǎng)絡(luò)中，TMDN提升幅度不大，但RS得分低于其他任何指標(biāo)，性能提升幅度在1%～27%?？傮w上，TMDN指標(biāo)表現(xiàn)出了更加穩(wěn)定的預(yù)測(cè)性能，RS結(jié)果平均提升幅度為16.5%，最高提升幅度為49.6%。

4.2 參數(shù)對(duì)性能的影響分析

圖7 不同方法關(guān)于參數(shù)的性能曲線(xiàn)

圖8 不同方法隨時(shí)間的AUC性能曲線(xiàn)

圖9 不同方法隨時(shí)間的RS性能曲線(xiàn)

4.3 不同時(shí)刻t的性能對(duì)比

圖8是AUC評(píng)價(jià)標(biāo)準(zhǔn)下各方法隨時(shí)間變化的性能曲線(xiàn)；圖9是RS評(píng)價(jià)標(biāo)準(zhǔn)下各方法隨時(shí)間變化的性能曲線(xiàn)。

從不同方法隨時(shí)間的AUC性能曲線(xiàn)中可以看出，整體而言，TMDN方法的性能優(yōu)于其他拓展指標(biāo)，尤其是優(yōu)于基于時(shí)間序列的拓展方法。通過(guò)不同時(shí)刻的AUC對(duì)比實(shí)驗(yàn)中，同樣考慮時(shí)間影響因素的不同方法能表現(xiàn)出不一致的變化趨勢(shì)，這說(shuō)明時(shí)間衰減因子能準(zhǔn)確描繪時(shí)間影響特征，更驗(yàn)證了所提算法的普適性和全面性，不僅考慮網(wǎng)絡(luò)拓?fù)涞木植啃畔?，也考慮了拓?fù)湫畔⒌娜A路徑；而相對(duì)加入時(shí)間衰減因子的拓展指標(biāo)，本文方法展現(xiàn)出了較好的預(yù)測(cè)性能，主要是因?yàn)楸疚姆椒ǜ釉敿?xì)和全面地考慮網(wǎng)絡(luò)拓?fù)涞男畔ⅰ?/p>

各指標(biāo)在5個(gè)網(wǎng)絡(luò)中的性能表現(xiàn)不太穩(wěn)定，說(shuō)明這些方法雖然針對(duì)不同的網(wǎng)絡(luò)可以表現(xiàn)出比較好的預(yù)測(cè)效果，但普適性和穩(wěn)定性遠(yuǎn)遠(yuǎn)不如TMDN方法。在5個(gè)網(wǎng)絡(luò)中，TMDN的RS得分最高降低了58%，在這幾個(gè)網(wǎng)絡(luò)中普遍降低3%～58%。

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

其中，為方法的運(yùn)行時(shí)間。

Figure 10 Comparison of time consumption of different methods

從運(yùn)行時(shí)間歸一化對(duì)比圖可看出，本文所提TMDN指標(biāo)在提升性能的同時(shí)并未增加太多運(yùn)行時(shí)間。

5 結(jié)束語(yǔ)

動(dòng)態(tài)網(wǎng)絡(luò)上的鏈路預(yù)測(cè)問(wèn)題近年來(lái)受到網(wǎng)絡(luò)科學(xué)領(lǐng)域?qū)W者的廣泛關(guān)注。針對(duì)真實(shí)網(wǎng)絡(luò)中連邊的形成存在偏好性這一現(xiàn)象，結(jié)合網(wǎng)絡(luò)節(jié)點(diǎn)自身屬性特征，本文提出一種基于節(jié)點(diǎn)匹配度的動(dòng)態(tài)網(wǎng)絡(luò)鏈路預(yù)測(cè)方法。該方法首先定義了衡量節(jié)點(diǎn)重要性的原生影響力和次生影響力方法；隨后，將節(jié)點(diǎn)重要性與時(shí)間衰減因子相結(jié)合，提出用于動(dòng)態(tài)網(wǎng)絡(luò)鏈路預(yù)測(cè)的節(jié)點(diǎn)匹配度方法。在多個(gè)真實(shí)網(wǎng)絡(luò)中的實(shí)驗(yàn)結(jié)果表明，所提TMDN方法相比現(xiàn)有方法在AUC和RS評(píng)價(jià)標(biāo)準(zhǔn)下均表現(xiàn)出更優(yōu)的預(yù)測(cè)效果，驗(yàn)證了節(jié)點(diǎn)間匹配程度對(duì)動(dòng)態(tài)網(wǎng)絡(luò)連邊形成的影響。所提方法實(shí)現(xiàn)簡(jiǎn)單，計(jì)算復(fù)雜度較低，可推廣至超大規(guī)模動(dòng)態(tài)網(wǎng)絡(luò)上的鏈路預(yù)測(cè)場(chǎng)景。今后的研究中，可不局限于對(duì)網(wǎng)絡(luò)拓?fù)涞木植拷Y(jié)構(gòu)化研究，通過(guò)加入多樣化的特征信息，對(duì)動(dòng)態(tài)真實(shí)網(wǎng)絡(luò)作進(jìn)一步深層次分析可對(duì)更準(zhǔn)確預(yù)測(cè)出其演化規(guī)律，具有現(xiàn)實(shí)研究意義。

[1] MCGLOIN J M, KIRK D S. Social network analysis[M]. Springer TMDN York, 2010.

[2] CUI Y, CAI M, DAI Y, et al. A hybrid network-based method for the detection of disease-related genes[J]. Physica A: Statistical Mechanics and Its Applications, 2018, 492: 389-394.

[3] SLAVIN S. Medical student mental health: challenges and opportunities[J]. Medical Science Educator, 2018, 28(1): 13-15.

[4] SHANMUKHAPPA T, HO I W H, TSE C K. Spatial analysis of bus transport networks using network theory[J]. Physica A: Statistical Mechanics and Its Applications, 2018, 502: 295-314.

[5] 劉樹(shù)新, 季新生, 劉彩霞, 等. 一種信息傳播促進(jìn)網(wǎng)絡(luò)增長(zhǎng)的網(wǎng)絡(luò)演化模型[J]. 物理學(xué)報(bào), 2014, 63(15): 429-439.

LIU S X, JI X S, LIU C X, et al. A complex network evolution model for network growth promoted by information transmission[J]. Acta Physica Sinica, 2014, 63(15): 429-439.

[6] ROLI A, VILLANI M, FILISETTI A, et al. Dynamical criticality: overview and open questions[J]. Journal of Systems Science and Complexity, 2018, 31(3): 647-663.

[7] SCELLATO S, NOULAS A, MASCOLO C. Exploiting place features in link prediction on location-based social networks[C]//Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining. 2011: 1046-1054.

[8] KERRACHE S, ALHARBI R, BENHIDOUR H. A scalable similarity-popularity link prediction method[J]. Scientific Reports, 2020, 10: 6394.

[9] WANG Y C, WANG Y, LIN X Y, et al. The influence of network structural preference on link prediction[J]. Discrete Dynamics in Nature and Society, 2020, 2020: 1-9.

[10] HISANO R. Semi-supervised graph embedding approach to dynamic link prediction[J]. CoRR, 2016, abs/1610.04351.

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

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

[12] VON MERING C, JENSEN L J, SNEL B, et al. STRING: known and predicted protein-protein associations, integrated and transferred across organisms[J]. Nucleic Acids Research, 2005, 33(suppl_1): D433-D437.

[13] SARKAR P, CHAKRABARTI D, JORDAN M. Nonparametric link prediction in large scale dynamic networks[J]. Electronic Journal of Statistics, 2014, 8(2): 2022–2065.

[14] 呂琳媛, 任曉龍, 周濤. 網(wǎng)絡(luò)鏈路預(yù)測(cè): 概念與前沿[J]. 中國(guó)計(jì)算機(jī)學(xué)會(huì)通訊, 2016, 12(4): 12-19.

LYU L Y, REN X L, ZHOU T. Network link prediction: concept and frontier[J]. Communications of CCF, 2016, 12(4): 12-19.

[15] AHMED N M, CHEN L. An efficient algorithm for link prediction in temporal uncertain social networks[J]. Information Sciences, 2016, 331: 120-136.

[16] GüNE??, GüNDüZ-??üDüCü ?, ?ATALTEPE Z. Link prediction using time series of neighborhood-based node similarity scores[J]. Data Mining and Knowledge Discovery, 2016, 30(1): 147-180.

[17] AHMED N M, CHEN L, WANG Y L, et al. Sampling-based algorithm for link prediction in temporal networks[J]. Information Sciences, 2016, 374: 1-14.

[18] SETT N, BASU S, NANDI S, et al. Temporal link prediction in multi-relational network[J]. World Wide Web, 2018, 21(2): 395-419.

[19] 陳敏, 崔大方, 黃平, 等. 3種鄉(xiāng)土水生植物對(duì)富營(yíng)養(yǎng)化水體凈化能力比較[J]. 安徽農(nóng)業(yè)科學(xué), 2019, 47(7): 63-65, 69.

CHEN M, CUI D F, HUANG P, et al. Comparison of purification ability of three native aquatic plants to eutrophic water bodies[J]. Journal of Anhui Agricultural Sciences, 2019, 47(7): 63-65, 69.

[20] CROMIE G, COLLINS J, LEACH D. Sequence interruptions in enterobacterial repeated elements retain their ability to encode well-folded RNA secondary structures[J]. Molecular Microbiology, 1997, 24(6): 1311-1314.

[21] 嚴(yán)麗軍. 自然災(zāi)害的災(zāi)情信息集成：理論與實(shí)證研究[D]. 上海: 上海師范大學(xué), 2016.

YAN L J. Disaster information integration of natural disasters: theoretical and empirical research. Shanghai: Shanghai Normal University, 2016.

[22] 苗會(huì)強(qiáng), 劉會(huì)平, 范九生, 等. 汶川地震次生災(zāi)害的成因、成災(zāi)與治理[J]. 地質(zhì)災(zāi)害與環(huán)境保護(hù), 2008, 19(4): 1-5.

MIAO H Q, LIU H P, FAN J S, et al. Secondary disasters, hazard chains and the curing in Wenchuan earthquake-hit area, West China[J]. Journal of Geological Hazards and Environment Preservation, 2008, 19(4): 1-5.

[23] 陳嘉穎, 于炯, 楊興耀, 等. 基于復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)重要性的鏈路預(yù)測(cè)算法[J]. 計(jì)算機(jī)應(yīng)用, 2016, 36(12): 3251-3255, 3268.

CHEN J Y, YU J, YANG X Y, et al. Link prediction algorithm based on node importance in complex networks[J]. Journal of Computer Applications, 2016, 36(12): 3251-3255, 3268.

[24] LIU F X, YANG H, WANG L M, et al. Biosynthesis of the high-value plant secondary product benzyl isothiocyanate via functional expression of multiple heterologous enzymes in escherichia coli[J]. ACS Synthetic Biology, 2016, 5(12): 1557-1565.

[25] 楊育捷. 復(fù)雜網(wǎng)絡(luò)下基于拓?fù)湎嗨菩缘逆溌奉A(yù)測(cè)研究[D]. 北京: 北京郵電大學(xué), 2019.

YANG Y J. Research on link prediction based on topological similarity in complex networks[D]. Beijing: Beijing University of Posts and Telecommunications, 2019.

[26] VáZQUEZ A. Growing network with local rules: preferential attachment, clustering hierarchy, and degree correlations[J]. Physical Review E, 2003, 67(5): 056104.

[27] MUBAYI D. Structure and stability of triangle-free set systems[J]. Transactions of the American Mathematical Society, 2007, 359(1): 275-291.

[28] WANG X Y, CAO J Y, QIN X M. Study of robustness in functionally identical coupled networks against cascading failures[J]. PLoS One, 2016, 11(8): e0160545.

[29] 劉樹(shù)新, 李星, 陳鴻昶, 等. 基于資源傳輸匹配度的復(fù)雜網(wǎng)絡(luò)鏈路預(yù)測(cè)方法[J]. 通信學(xué)報(bào), 2020, 41(6): 70-79.

LIU S X, LI X, CHEN H C, et al. Link prediction method based on matching degree of resource transmission for complex network[J]. Journal on Communications, 2020, 41(6): 70-79.

[30] ?ZCAN A, ??üDüCü ? G. Supervised temporal link prediction using time series of similarity measures[C]//Proceedings of 2017 Ninth International Conference on Ubiquitous and Future Networks (ICUFN). 2017: 519-521.

[31] LORRAIN F, WHITE H C. Structural equivalence of individuals in social networks[J]. The Journal of Mathematical Sociology, 1971, 1(1): 49-80.

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

[33] OU Q, JIN Y D, ZHOU T, et al. Power-law strength-degree correlation from resource-allocation dynamics on weighted networks[J]. Physical Review E, Statistical, Nonlinear, and Soft Matter Physics, 2007, 75(2): 021102.

[34] LYU L, JIN C H, ZHOU T. Similarity index based on local paths for link prediction of complex networks[J]. Physical Review E, Statistical, Nonlinear, and Soft Matter Physics, 2009, 80(4): 046122.

[35] DA SILVA SOARES P R, PRUDêNCIO R B C. Time series based link prediction[C]//Proceedings of 2012 International Joint Conference on Neural Networks (IJCNN). 2012: 1-7.

[36] KUNEGIS J. KONECT: the Koblenz network collection[C]// Proceedings of the 22nd International Conference on World Wide Web - WWW '13 Companion. 2013: 1343-1350.

[37] Batagelj V, Mrvar A. Pajek Datasets[EB/OL].

[38] PARANJAPE A, BENSON A R, LESKOVEC J. Motifs in temporal networks[C]//Proceedings of the Tenth ACM International Conference on Web Search and Data Mining. 2017: 601-610.

Link prediction method for dynamic networks based on matching degree of nodes

LI Cong, JI Xinsheng, LIU shuxin, LI Jinsong, LI Haitao

Information Engineering University, Zhengzhou 450001, China

The research of dynamic evolutionary trends and temporal characteristics in real networks which are important part of the real world is a hot research issue nowadays. As a typical research tool in the field of network science, link prediction technique can be used to predict the network evolution by mining the historical edge information and then predict the future edge. The topological evolution of dynamic real networks was analyzed and it found that the interaction and matching between nodes in the network topology can capture the dynamic characteristics of the network more comprehensively. The proposed method analyzed the attribute characteristics of network nodes, and defined a node importance quantification method based on primary and secondary influences. Besides, a time decay factor was introduced to portray the influence of network topology on the formation of connected edges at different moments. Furthermore, the node importance and time decay factor were combined to define the Temporal Matching Degree of Nodes (TMDN), which was used to measure the possibility of future edge formation between node pairs. The experimental results in five real dynamic network datasets showed that the proposed method achieves better prediction performance under both AUC and Ranking Score, with a maximum improvement of 42%. It also proved the existence of interactive matching priority among nodes, and confirmed the effectiveness of both primary and secondary influence of nodes. As the future work, we will add diversified feature information to further deepen the analysis of dynamic real networks and then predict the evolution law more accurately.

dynamic networks, link prediction, matching degree of nodes, node importance, time decaying parameter

The National Natural Science Foundation of China (61803384)

李聰, 季新生, 劉樹(shù)新, 等. 基于節(jié)點(diǎn)匹配度的動(dòng)態(tài)網(wǎng)絡(luò)鏈路預(yù)測(cè)方法[J]. 網(wǎng)絡(luò)與信息安全學(xué)報(bào), 2022, 8(4):131-143.

TP393

A

10.11959/j.issn.2096?109x.2022053

李聰（1996?），男，山東菏澤人，信息工程大學(xué)碩士生，主要研究方向?yàn)閺?fù)雜網(wǎng)絡(luò)、鏈路預(yù)測(cè)、網(wǎng)絡(luò)安全。

季新生（1969?），男，河南駐馬店人，信息工程大學(xué)教授、博士生導(dǎo)師，主要研究方向?yàn)橥ㄐ啪W(wǎng)架構(gòu)、內(nèi)生安全、復(fù)雜網(wǎng)絡(luò)。

劉樹(shù)新（1987?），男，山東臨沂人，信息工程大學(xué)助理研究員，主要研究方向?yàn)閺?fù)雜網(wǎng)絡(luò)、鏈路預(yù)測(cè)、社交網(wǎng)絡(luò)分析等。

李勁松（1992?），男，山東泰安人，信息工程大學(xué)博士生，主要研究方向?yàn)閺?fù)雜網(wǎng)絡(luò)、鏈路預(yù)測(cè)、大數(shù)據(jù)挖掘、網(wǎng)絡(luò)安全。

李海濤（1982?），男，山東泰安人，信息工程大學(xué)副研究員，主要研究方向通信網(wǎng)安全、數(shù)據(jù)處理和嵌入式設(shè)計(jì)。

2021?01?05；

2021?05?04

季新生，jixinsheng@ndsc.com.cn

國(guó)家自然科學(xué)基金（61803384）

LI C, JI X S, LIU S X, et al. Link prediction method for dynamic networks based on matching degree of nodes[J]. Chinese Journal of Network and Information Security, 2022, 8(4): 131-143.