基于節點匹配度的動態網絡鏈路預測方法

李聰，季新生，劉樹新，李勁松，李海濤

基于節點匹配度的動態網絡鏈路預測方法

李聰，季新生，劉樹新，李勁松，李海濤

（信息工程大學，河南 鄭州 450001）

現實世界存在眾多真實網絡，研究真實網絡中的動態演化趨勢和時序性特征是熱點問題。鏈路預測技術作為網絡科學領域重要研究工具可通過挖掘歷史連邊信息推測網絡演化規律，進而對未來連邊進行預測。通過分析動態真實網絡中的拓撲結構演化，發現通過分析網絡拓撲中節點間的交互性和匹配度問題能夠更充分捕捉網絡的動態特征，提出一種基于節點匹配度的動態網絡鏈路預測方法。該方法對網絡節點的屬性特征進行分析，定義基于原生影響力和次生影響力的節點重要性量化方法；引入時間衰減因子，刻畫不同時刻網絡拓撲對連邊形成的影響程度；結合節點重要性和時間衰減因子定義動態節點匹配度（TMDN，temporal matching degree of nodes）方法，用于衡量節點對之間未來形成連邊的可能性。在5個真實動態網絡數據集中的實驗結果表明，相比現有3類主流動態網絡鏈路預測方法，所提方法在AUC和Ranking Score兩種評價標準下均取得更優的預測性能，預測結果最高提升42%，證明了節點間存在著交互匹配優先級，同時證實了節點原生影響力和次生影響力的有效性。

動態網絡；鏈路預測；節點匹配度；節點重要性；時間衰減因子

0 引言

隨著社會學[1]、生物學[2]、醫學[3]以及互聯網技術[4]的飛速發展，復雜網絡[5]被廣泛應用于復雜系統的抽象化表示、形式化分析與深度挖掘等，極大地推動了網絡科學的蓬勃發展。復雜系統[6]中的個體，如人類、細胞、基站、路由器等可以看成實體，在網絡拓撲中用節點表示，節點之間的連邊用來描述實體之間的關系[7]。鏈路預測作為研究復雜科學的重要技術之一，已成為近年來的研究熱點問題[8-11]。鏈路預測技術旨在利用復雜系統中已觀測的結構信息、屬性信息等，發現網絡拓撲結構中的缺失連邊，以及推測未來可能形成的連邊[12]。鏈路預測為生物學、醫學、計算機網絡、社會科學等領域的研究提供了強大的技術支持。通過對大量節點之間復雜關系的挖掘可清晰地分析網絡結構，發現網絡中連邊的演化趨勢[13]，實現對未來連邊的預測。例如，通過分析社交群體近期的社交活動，利用鏈路預測技術尋找未來可能發生的詐騙、推銷等異常行為。

近年來，社交網絡分析在各行各業中引起了相當大的關注，被廣泛應用于市場營銷、業務流程建模及傳染病模型。鏈路預測作為社交網絡分析的重要手段能夠捕捉社交網絡信息，及時發現新的節點和連接。現實中的社交網絡由個體及個體間復雜關系組成，是一個高度動態變化的網絡。通過鏈路預測從已知的網絡結構中尋找和檢測隱藏的連邊和節點，可進行異常節點挖掘、重要連邊預測等，映射到真實社交網絡中可識別詐騙信息。當前，對于靜態網絡的鏈路預測技術研究已經相當成熟，文獻[14]詳細對比分析了各種方法，將其在局部和全局兩個維度進行歸類。對于動態網絡的研究也在近幾年發展迅速。Ahmed等[15]提出一種通過集成網絡中的時間信息、社區結構和節點中心性進行動態網絡鏈預測的方法，通過節點在社區中的交互情況構造特征向量來預測節點未來的重要性。Günes等[16]提出了一種演進網絡的鏈路預測方法，先計算過去不同時間段的網絡結構中不同節點的相似性得分，再通過時間序列預測模型ARIMA來預測未來節點的連邊情況。Ahmed等[17]提出了一種針對時間不確定網絡的鏈路方法，首先將不確定網絡中的鏈路預測問題轉化為確定網絡的隨機游走問題，然后在子圖中計算節點與鄰居之間的相似性分數。針對異構網絡，Sett等[18]結合多域拓撲特征和時間維度，提出一種TMLP算法，利用二元交互情況和圖拓撲特征變化情況，結合時間序列模型進行預測。但上述方法通過轉化成靜態圖或考慮局部特征，容易丟失動態網絡中重要拓撲信息，影響預測精度。

本文通過捕捉歷史拓撲特征，并將其作為節點相似度的依據，提出一種基于節點匹配度的動態網絡鏈路預測方法。該方法根據節點原生重要性和次生重要性定義節點匹配度，用于衡量節點間未來產生交互的可能性。進而結合網絡拓撲的歷史變化特征及時間影響力，捕捉網絡拓撲的動態信息。實驗結果表明，本文所提方法在動態網絡鏈路預測方面相比現有方法取得更優的效果。

1 相關工作

1) 任意節點不能形成自閉環；

2) 任意節點之間最多只能含有一條邊；

3) 節點間的交互無方向；

4) 連邊只代表節點之間關系的存在。

2 方法介紹

原生能力[19]與次生能力[20]在現實生活中無處不在，大到生態系統，小至單一細胞，近些年頻發的自然災害也會造成原生災難[21]和次生災難[22]。例如，在社交網絡中，有些個體天生擅長某些事物，稱之為原生能力；個體具備依托已存關系而帶動新關系形成的能力，此能力建立在原生能力的基礎上，稱之為次生能力。復雜網絡作為真實網絡的抽象，需準確刻畫真實網絡的網絡特性及個體屬性。在網絡拓撲中描述實體的節點應反映出實體的原生能力和次生能力。度是衡量節點重要性[23]的指標，是真實網絡中實體原生能力在復雜網絡中的抽象表現，在網絡拓撲中可作為節點原生能力的體現。例如，在社交網絡中，節點度高的節點之間更容易形成連接；在食物鏈網絡中，節點度高象征著在食物鏈中的等級高，這部分節點更傾向于與節點度低的實體形成連邊。在網絡拓撲中，節點的度是由節點自身性質決定的，而連邊是在節點度的基礎上產生的，兩者是真實系統中原生與次生邏輯關系的抽象。作為節點的次生產物[24]，連邊影響力被多次提起。連邊具有帶動新連邊形成的能力，此能力決定于節點本身，這正是真實網絡中次生能力的抽象，在網絡拓撲中，稱之為節點的次生能力。本文根據節點原生能力和次生能力定義節點原生重要性和次生重要性，并結合兩者提出節點匹配度的概念。

2.1 節點重要性

對于節點重要性的衡量可從節點自身和鄰域拓撲兩個角度加以考察。連邊是基于節點性質而形成的，可看作節點的次生產物。在復雜網絡中，節點度可用于衡量節點在網絡中的重要性程度，其可以解釋為節點周圍連邊貢獻的和[25]。然而，節點度將每條邊的貢獻程度設為1，無法區分不同邊的連接能力[25]，因此，本文用連邊連接能力刻畫該貢獻程度，定義節點次生重要性。

下面討論連邊連接能力的量化問題。通常情況下，復雜網絡中連邊的形成不是隨機的，而是具有特定傾向性。該傾向性在無標度網絡中通?？捎谩皟炏冗B接（PA，preferential attachment）[26]”機制解釋。該機制描述了復雜網絡中“富者越富，強者越強”的現象。對于一條連邊而言，可利用優先連接機制刻畫其連接能力。傳統PA方法只考慮端節點度的乘積，對網絡中三角形結構具有的貢獻能力未做區分。

三角形結構[27]穩定性強，結構不容易發生改變，是復雜網絡中最為穩定的局部結構之一。穩定性強則意味著結構不容易發生改變，在動態網絡中則意味著連邊不會隨時間的變化而輕易消失。

圖1 不同時刻網絡拓撲圖示例1

Figure 1 Example of network topology diagram 1 at different times

圖2 不同時刻網絡拓撲圖示例2

Figure 2 Example of network topology diagram 2 at different times

圖3 第時刻網絡拓撲子圖

基于上述分析，本文考慮三角形結構與非三角形結構的貢獻區別，基于PA指標定義連邊的連接能力，如下：

圖3中通過上述方法可計算得出

圖4 第時刻網絡拓撲子圖

在圖4中，有

上述定義考慮了節點原生重要性和節點次生重要性，并對節點間單個節點重要性進行量化，因而對節點重要性的刻畫更加合理。在圖4所示的拓撲子圖中可以看到，通過此方法計算得到的節點重要性數值為

2.2 節點匹配度

節點重要性決定節點的影響力，在實際網絡中，影響力大的個體捕獲資源和信息的能力更強。Wang等[28]提出，在電網中，每個電站都具有有限負載和有限容量，而節點的承載能力決定了電站的負載和容量，重要的節點會承載更多的負載，與其他節點的匹配能力[29]會更強。綜合以上情形，給出節點匹配度的定義，用于刻畫拓撲結構中節點間產生連邊的概率。

2.3 時間衰減因子

結合衰減因子，節點匹配度的定義如下。

3 衡量標準及數據集

3.1 對比方法介紹

（1）傳統方法

共同鄰居（CN，common nodes）方法[31]：以兩節點之間共同鄰居數量為衡量標準，數學公式表示為

Adamic-Adar（AA）方法[32]：此方法是建立在共同鄰居的基礎上的，即兩節點的共同鄰居度越大，則兩節點之間的相似性分數越高，數學公式表示為

資源分配（RA，resource allocation）方法[33]：RA與AA有異曲同工之妙，兩者的思想相同，只是賦予節點權重的方式不同，數學表達式為

局部路徑（LP，local path）方法[34]：將三階路徑考慮進來，數學表達式為

（2）拓展方法

①基于時間序列的拓展方法

首先將在時刻觀察到的網絡劃分成多個時間分段的快照，然后定義一個預測窗口，將這些時間快照按照窗口長度進行劃分。

利用相似性指標計算每個子圖上節點對的相似性分數，構造時間序列，利用平均預測模型，得到相似性分數。預測模型為

此類拓展方法用TCN、TAA、TRA、TLP[35]表示。

②基于時間因子的拓展方法

Güne?等[16]將時間因子應用于相似性方法內，結合時間因子，網絡的鄰接矩陣表示為

相應的拓展方法為

3.2 算法評價標準

RS對所有未連邊按照相似分值大小排序，得到測試集的邊在最終排序中的位置，測試集連邊排名越高，排序分值越小時，說明該算法具有越好預測性能。以為未連邊的集合（測試集中和不存在邊集的集合），網絡中某條測試邊的RS為

整個網絡的平均RS可通過遍歷求和得到，計算方式如下。

3.3 數據集

通過調研近兩年文獻，發現多數文獻選擇郵件數據集進行算法性能對比。為驗證所提方法的性能，使其更具有說服力，本文選用5個來自不同領域的真實動態網絡數據集進行實驗。5個真實數據集的基本特征參數如表1所示。以下詳細介紹各數據集的具體信息。

（1）DNC emails（DNC）[36]：由 2016 年美國民主黨全國委員會郵件泄露事件中采集的郵件往來網絡，其節點表示郵件賬號，有向邊表示某賬號發往另一賬號的郵件。

（2）Manufacturing emails（MAN）[36]：一個制造業工廠內部員工的郵件往來網絡。屬于動態網絡，其中節點表示員工賬號，有向邊表示在某一時刻由員工之間發送的郵件。

（3）LevantMonths（LEM）[37]：一個由堪薩斯事件數據系統基于包含WEIS編碼事件的文件夾收集的交互網絡，其中包含8個國家之間的交互信息。原始數據集涵蓋了1979年4月至2004年6月的事件。

（4）Email-Eu-core-temporal（EEC）[38]：一個由歐洲某大型研究機構內部郵件往來數據構成的有向網絡。節點表示郵件賬號，有向邊表示某一賬號在某時刻發往另一賬號的郵件。根據數據來源，原始數據集包含若干子數據集，代表研究機構內不同部門的郵件往來。本文選用其中的email-Eu-core-temporal-Dept1（EEC1）和email-Eu- core-temporal-Dept2（EEC2）。由于原始數據集的時間戳起始于0，確切起始日期無法確定。

4 實驗結果與分析

為驗證所提TMDN在真實數據集中的預測效果，本文通過對比實驗分析了TMDN在不同參數、時刻下AUC和RS結果，具體分析如下。

4.1 平均性能對比

4.1.1 AUC評價方法

首先研究所提TMDN方法在AUC衡量標準下的性能。圖5為TMDN和現有方法在真實數據集中的AUC對比結果。可以看出，與其他指標相比，TMDN指標在5個網絡中均取得了較高的預測精度。CN、TCN、TF_CN僅考慮了二階鄰居數目，在AUC評價標準下結果普遍一般，但在MAN中，CN明顯高于AA、RA和全局指標LP，預測效果僅次于本文的指標，TCN也優于TAA、TRA、TLP；而加入時間因素的拓展指標性能沒有展示出優勢，性能表現整體不如傳統指標，造成此現象的原因是MAN數據集動態特性不明顯，考慮時間因素的拓展方法無法發揮性能優勢。在MAN數據集中，CN指標優勢明顯，說明此數據集局部特征明顯，局部指標可發揮出性能優勢，而考慮共同鄰居的AA、RA不及CN，說明該數據集共同鄰居特征不明顯。AA、RA及其拓展指標考慮了共同鄰居節點度，也表現出了不錯的預測效果，在DNC、LEM、EEC1、EEC2這4個網絡中預測效果明顯優于CN。而考慮全局信息的LP及其拓展方法TLP、TF_LP，在大部分網絡中表現出了較高的預測精度，甚至在EEC2網絡中，LP、TLP的AUC得分強于TMDN，加入時間因子，將網絡的動態信息考慮進來，全局方法TF_LP明顯高于局部方法TF_CN、TF_AA和TF_RA。整體而言，拓展方法表現優于傳統方法，具體到數據集中表現卻參差不齊，這是由于動態特性只是動態網絡的一個特征，還要考慮其局部特征和全局特征等多個因素，在一些動態特性較高的網絡中，會出現拓展方法低于傳統方法的現象，所以，算法的普適性也是衡量指標性能的重要標準。

表1 5個真實數據集的基本特征參數

在考慮節點匹配度后，TMDN預測效果明顯領先，說明現實網絡連邊構建中均存在一定程度的匹配傾向性。同樣考慮共同鄰居間存在的社團關系，TMDN在5個網絡中的預測效果均優于局部相似性方法及拓展方法TCN、TF_CN、TAA、TF_AA、TRA、TF_RA，且提升精度在1%～33%。相比全局方法LP、TLP、TF_LP，在DNC、MAN、LEM中同樣有較高的提升，提升比例為1%～42%，但在EEC2中，本文的方法效果不如LP和TLP。總體上，相比其他方法，TMDN方法的平均提升比率為19.3%，最高提升比例為42%。

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

Figure 5 Average AUC performance of different methods

4.1.2 RS評價方法

本節在RS衡量標準下對TMDN的性能進行對比分析。圖6為TMDN與其他方法在5個真實網絡中的RS對比結果。

圖6 不同方法的平均RS性能對比

Figure 6 Comparison of average RS performance of different methods

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

TMDN方法在5個網絡中均表現出較好的性能，RS得分普遍低于其他指標。在DNC和MAN網絡中性能提升明顯，相比其他指標，TMDN的預測性能最高提升了49.6%，在DNC中，TF_RA展現出了不俗的預測精度，RS得分甚至低于TMDN，但也僅僅低0.01。在其他3個網絡中，TMDN提升幅度不大，但RS得分低于其他任何指標，性能提升幅度在1%～27%。總體上，TMDN指標表現出了更加穩定的預測性能，RS結果平均提升幅度為16.5%，最高提升幅度為49.6%。

4.2 參數對性能的影響分析

圖7 不同方法關于參數的性能曲線

圖8 不同方法隨時間的AUC性能曲線

圖9 不同方法隨時間的RS性能曲線

4.3 不同時刻t的性能對比

圖8是AUC評價標準下各方法隨時間變化的性能曲線；圖9是RS評價標準下各方法隨時間變化的性能曲線。

從不同方法隨時間的AUC性能曲線中可以看出，整體而言，TMDN方法的性能優于其他拓展指標，尤其是優于基于時間序列的拓展方法。通過不同時刻的AUC對比實驗中，同樣考慮時間影響因素的不同方法能表現出不一致的變化趨勢，這說明時間衰減因子能準確描繪時間影響特征，更驗證了所提算法的普適性和全面性，不僅考慮網絡拓撲的局部信息，也考慮了拓撲信息的三階路徑；而相對加入時間衰減因子的拓展指標，本文方法展現出了較好的預測性能，主要是因為本文方法更加詳細和全面地考慮網絡拓撲的信息。

各指標在5個網絡中的性能表現不太穩定，說明這些方法雖然針對不同的網絡可以表現出比較好的預測效果，但普適性和穩定性遠遠不如TMDN方法。在5個網絡中，TMDN的RS得分最高降低了58%，在這幾個網絡中普遍降低3%～58%。

4.4 時間復雜度分析

其中，為方法的運行時間。

Figure 10 Comparison of time consumption of different methods

從運行時間歸一化對比圖可看出，本文所提TMDN指標在提升性能的同時并未增加太多運行時間。

5 結束語

動態網絡上的鏈路預測問題近年來受到網絡科學領域學者的廣泛關注。針對真實網絡中連邊的形成存在偏好性這一現象，結合網絡節點自身屬性特征，本文提出一種基于節點匹配度的動態網絡鏈路預測方法。該方法首先定義了衡量節點重要性的原生影響力和次生影響力方法；隨后，將節點重要性與時間衰減因子相結合，提出用于動態網絡鏈路預測的節點匹配度方法。在多個真實網絡中的實驗結果表明，所提TMDN方法相比現有方法在AUC和RS評價標準下均表現出更優的預測效果，驗證了節點間匹配程度對動態網絡連邊形成的影響。所提方法實現簡單，計算復雜度較低，可推廣至超大規模動態網絡上的鏈路預測場景。今后的研究中，可不局限于對網絡拓撲的局部結構化研究，通過加入多樣化的特征信息，對動態真實網絡作進一步深層次分析可對更準確預測出其演化規律，具有現實研究意義。

[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] 劉樹新, 季新生, 劉彩霞, 等. 一種信息傳播促進網絡增長的網絡演化模型[J]. 物理學報, 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] 呂琳媛. 復雜網絡鏈路預測[J]. 電子科技大學學報, 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] 呂琳媛, 任曉龍, 周濤. 網絡鏈路預測: 概念與前沿[J]. 中國計算機學會通訊, 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種鄉土水生植物對富營養化水體凈化能力比較[J]. 安徽農業科學, 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] 嚴麗軍. 自然災害的災情信息集成：理論與實證研究[D]. 上海: 上海師范大學, 2016.

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

[22] 苗會強, 劉會平, 范九生, 等. 汶川地震次生災害的成因、成災與治理[J]. 地質災害與環境保護, 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] 陳嘉穎, 于炯, 楊興耀, 等. 基于復雜網絡節點重要性的鏈路預測算法[J]. 計算機應用, 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] 楊育捷. 復雜網絡下基于拓撲相似性的鏈路預測研究[D]. 北京: 北京郵電大學, 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] 劉樹新, 李星, 陳鴻昶, 等. 基于資源傳輸匹配度的復雜網絡鏈路預測方法[J]. 通信學報, 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)

李聰, 季新生, 劉樹新, 等. 基于節點匹配度的動態網絡鏈路預測方法[J]. 網絡與信息安全學報, 2022, 8(4):131-143.

TP393

A

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

李聰（1996?），男，山東菏澤人，信息工程大學碩士生，主要研究方向為復雜網絡、鏈路預測、網絡安全。

季新生（1969?），男，河南駐馬店人，信息工程大學教授、博士生導師，主要研究方向為通信網架構、內生安全、復雜網絡。

劉樹新（1987?），男，山東臨沂人，信息工程大學助理研究員，主要研究方向為復雜網絡、鏈路預測、社交網絡分析等。

李勁松（1992?），男，山東泰安人，信息工程大學博士生，主要研究方向為復雜網絡、鏈路預測、大數據挖掘、網絡安全。

李海濤（1982?），男，山東泰安人，信息工程大學副研究員，主要研究方向通信網安全、數據處理和嵌入式設計。

2021?01?05；

2021?05?04

季新生，jixinsheng@ndsc.com.cn

國家自然科學基金（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.