動態網絡下的鏈路預測研究

摘 要：隨著物聯網技術的不斷發展，越來越多的設備和傳感器被部署在各種應用場景中，這些設備之間的通信鏈路質量對于物聯網應用的性能和可靠性至關重要。鏈路預測是指利用網絡中已知的部分信息來推測網絡中未知節點之間的連接或關系，是一種基于網絡拓撲結構分析的方法。因此，鏈路預測技術成為了物聯網領域的研究熱點之一。鏈路預測經過十多年的研究得到了迅速發展，它能夠發現網絡中缺失的鏈路或預測網絡中未來鏈路的可能性，但現有的研究大多停留在靜態網絡上，沒有考慮網絡的方向和時間。因此，文中總結了目前動態網絡下的鏈路預測研究方法，指出了現階段面臨的研究挑戰，并做出了展望。

關鍵詞：復雜網絡；靜態網絡；動態網絡；物聯網；鏈路預測；時間感知

中圖分類號：TP39 文獻標識碼：A 文章編號：2095-1302（2024）06-00-04

0 引 言

當今社會，物聯網技術被廣泛應用于各個領域，如智能家居、智能交通、智能醫療等。這些網絡最典型的特征是由許多節點和相互連接的邊組成，節點代表網絡中的不同實體，邊代表實體之間的關系。在物聯網中，各設備之間的通信至關重要，而鏈路預測技術是保證設備通信質量的關鍵。鏈路預測利用現有信息尋找網絡中缺失的信息，識別虛假邊緣，預測未來鏈路的可能性。通過對設備之間的通信數據進行分析和建模，鏈路預測可以提前預測未來鏈路的質量和穩定性，從而采取措施，保證設備之間的通信質量。

鏈路預測方法在靜態網絡中得到了很好的應用。例如，文獻[1]通過局部路徑來預測網絡邊緣的方向，可以應用于大規模網絡。文獻[2]提出一種相位動態算法，用于分析有向網絡節點的鏈路方向，論證了雙向鏈路和單向鏈路在鏈路預測和網絡結構形成中的不同作用。文獻[3]在分析微信號網絡的基礎上，提出了一種基于平均場理論的進化模型，用于解釋網絡鏈路產生和動態傳播的機理。

目前人們已經做出了很大的努力來預測靜態網絡中的鏈路，然而實際情況是，世界上很少有網絡是靜態的。大部分網絡隨著時間的推移而變化，并攜帶其他時間信息，例如物聯網中網絡節點和邊緣的變化。由于物聯網是一個分布式系統，其中包含大量節點和設備，這些節點和設備可以在任何時間加入或離開網絡，導致網絡的拓撲結構可能會動態變化，同時鏈路質量也會因為干擾、距離、設備限制和其他因素而變化。因此，動態網絡的鏈路預測研究更具有實際意義。基于此，文中綜述了動態網絡下鏈路預測的方法。

1 網絡表示

給定一個有向網絡D（V， E），V表示網絡中節點的集合{v1， v2， ...， vn}，E表示連接的邊的集合{e1， e2， ...， en}，任何一條邊對應一對節點，ex={vi， vj}，vi為起點，vj為終點。一個有向網絡需要滿足以下3個條件：

（1）有向：網絡中的邊是有方向的，即從一個節點指向另一個節點的箭頭有明確方向；

（2）有權：網絡中的邊有權重或者權值，表示2個節點之間的關系強度或者距離大小；

（3）有環：網絡中存在環路，即從一個節點出發，經過若干條邊后可以回到該節點。其中，有向網絡中的環路必須是有向的，即沿箭頭的方向才能形成環路。

節點vi和節點vj之間有且只有一條連續邊，而且不存在ex=ey={vi， vj}的情況。有向網絡通常用鄰接矩陣和關聯矩陣表示。

（1）鄰接矩陣

網絡鄰接矩陣是表示有向節點以及連接邊之間關系的非對稱矩陣。其中每個元素表示2個節點之間是否存在邊。如果節點i和節點j之間存在一條邊，則鄰接矩陣中第i行第j列的元素為1，否則為 0。鄰接矩陣可以用于描述復雜網絡下的拓撲結構。

（2）關聯矩陣

一個具有N個節點和M條邊的網絡可以用關聯矩陣N×M表示，表示為AC，矩陣元素ACix=1表示節點vi是邊ex的開始，矩陣元素ACix=-1表示節點vi是邊ex的結束，矩陣元素ACix=0表示節點vi不與邊ex相鄰。

（3）出入度

有向網絡節點的度由出度和入度組成。節點vi的出度等于與起始點相鄰邊的個數，記為。節點vi的入度等于以vi結尾的相鄰邊的個數，記為。單個節點的出入度可能不同，但整個網絡的平均入度始終等于網絡的平均出度，表示為：

（1）

（4）聚類系數

聚類系數最早由Watts和Strogatz等人提出，定義為相鄰節點間的邊數與可能的最大邊數之比。在無向網絡中三角形結構是唯一的，而在有向網絡中考慮連接邊的方向，三角形結構有7種類型，如圖1所示。

其中一種定義方法是分別計算不同三角形結構的聚類系數。節點和2個鄰居（不區分鄰居的順序）可以形成3個局部結構和4個三角形結構，如圖2所示。

對以上4個三角形結構計算聚類系數，并由下列方程給出：

（2）

式中：MiA、MiB、MiC分別表示結構A、B、C的個數；NiFB、NiFFA、NiFFB、NiFFC表示結構FB、FFA、FFB、FFC的個數。這個定義的優點是有利于對有向網絡的結構和功能特征進行更詳細的研究。研究表明，在某些網絡中，結構A的聚類因子越小，節點產生新連接的可能性越大。在此基礎上，陳端兵等人提出了一種算法，該算法考慮節點的聚類系數，以識別大規模有向網絡中傳播影響較大的節點。

2 鏈路預測

網絡中的鏈路預測旨在從已知的網絡節點、結構信息[3-4]中預測網絡中一對節點之間建立連接的可能性，其主要任務為預測未知鏈路和未來鏈路。下面簡要介紹鏈路預測的概念和評價方法。

2.1 鏈路預測描述

對于有向網絡D（V， E），V表示網絡中節點的集合，E表示網絡中連通邊的集合。網絡中連通邊的總數M=N（N-1），給定一種預測方法，Sxy表示vx→vy單向連通邊的預測分數，通常有Sxy≠Syx。所有節點對按得分降序排列，排名越高的節點產生連續邊的概率越高。

2.2 評價方法

為了進行性能比較，將網絡分為訓練集ET和測試集EP，其中ET∪EP=E，ET∩EP=，將屬于U但不屬于E的邊定義為不存在邊的集合。對于給定的鏈路預測算法，基于訓練集ET計算節點對的分數，并在測試集EP中進行驗證。

3種主流的評價方法是AUC、Precision和Ranking Score。AUC衡量的是算法的整體精度[4]；Precision考慮前L排名的預測精度[5]；排名分數考慮預測邊緣的排名[6]。

2.2.1 AUC

AUC原指接收者工作特征曲線（ROC）下的面積，可以理解為在隨機選擇相鄰邊作為測試集的情況下，分數值高于隨機選擇不存在邊作為測試集的情況的概率[6]。假設上述2個測試集中樣本數量的乘積為n，AUC計算公式定義如下：

（3）

式中：n'和n''分別代表在隨機挑選相鄰邊作為測試集的情況下，得分值大于和等于隨機挑選不存在的邊作為測試集的次數。

精度定義為在前L個預測邊中準確預測的比例[7]。如果有m條連續邊被準確預測并根據預測得分大小排序，則假設前L條連續邊中有m條屬于測試集，其精度定義為：

（4）

2.2.2 Ranking Score

在某些情況下，邊緣在測試集中的位置在最終排名中更為重要，可以通過排名分數（Ranking Score）來衡量。設H=U-ET為未知邊的集合，re表示測試邊e∈EP在排序中的排名。測試邊的排名分數為：。對測試集中的所有邊進行迭代，得到系統排序分數如下：

（5）

3 動態網絡下的鏈路預測

據文獻[8]所述，鏈路強度的變化不僅取決于共同鄰居出現的頻率或次數，還取決于共同鄰居接觸到該消息的時間戳。這種互動是有意義的，因為它引入了一種新的時間評分方法來設計該指標。該方法結合了共同鄰居的有效性和時間性，并使用以下概念：如果節點相對于當前時間沒有交互很長時間，那么鏈路強度就會變弱；如果2個節點與其公共鄰居進行了交互，則鏈路強度表示為在時間上更接近的權重，且公共鄰居更有效，未來發生的可能性最大。

在文獻[9]中，考慮時變二部圖，采用基于矩陣和張量的方法來預測未來的鏈接。我們提出了一種基于權重的方法，把多年數據折疊成矩陣，將用于鏈路預測的Katz方法擴展到二部圖，采用截斷的奇異值分解，并以可擴展的方式逼近最終的鏈路預測值。盡管噪聲水平較高，但CP方法的AUC得分為0.845，遠優于“最后一個周期”方法的0.686。我們還考慮了前1 000個返回值的準確性。基于CP方法前

1 000個分數的準確率為100%，而Last Period方法的準確率僅為70%。

在文獻[10]中，提供了一種結合時間信息的方法。這種方法的靈感來源于一個事實，即近期事件之間的相關性更強，而早期事件與未來的聯系則較為薄弱。例如，作者的興趣可能會隨著時間的推移而改變，因此舊出版物可能與他當前的研究領域不太相關。

文獻[11]提出了一套新的基于時間距離的指標，用于量化和比較信息的速度（延遲）。相較于過去用于靜態圖形和社交網絡數據傳播效率的度量，基于距離的度量可以更有效地描述時變圖形的時間動態，例如延遲、連接和交互的時間順序（交互）、本地和全局視圖。通過考慮之前交互的時間戳，可以大大提高鏈路預測模型的精度。

文獻[12]呈現了一個詳細的概率模型，其中包括時間感知和使用時間特征來獲得相應的邊緣權重。該模型可用于基于Adam-Adar距離和基于Roger PageRank的技術，并提出了一種評估性能的測試方法，即通過對所選節點的鄰域進行排序來評估其能力。

文獻[13]中引入了一種將時間數據編碼為圖的表示方法，即時間圖。時間圖將原始數據與時間信息一起保留，為獲取內在動態數據提供了基礎，這些數據用于描述和傳遞數據本身，并用于分析和理解其屬性。

文獻[14]提出了一種有效的學習和推理技術，該技術是通過考慮一組有限的時間相關性而開發的。動態關系數據的表示也采用了兩階段過程，首先使用核平滑的時態關系信息，其次使用關系信息來調節屬性依賴關系。同時，還介紹了時間局部性和時間重現性。時間局部性指的是最近發生的事件比過去事件對當前的影響更大；時間重現性則指2個實例之間存在規律的事件序列，這種序列比孤立的事件更有潛在的關聯性。此外，他們還將時間信息納入統計關系模型，來尋找時間局部性和時間遞歸的模式，以便確定更有可能表現出更強關聯關系的相關屬性的值。

文獻[15]中提供了一種名為C-Group的工具，它允許用戶隨著時間的推移添加或刪除節點（角色）和邊（關系），主要貢獻在于對組成員的承諾進行時間跟蹤。這種方式使用戶能夠研究Pair的臨時組成員關系的背景信息。C-Group提供了一個靈活的界面，用戶可以交互式定義（和重新定義）組，并支持2種新穎的可視化表示不斷發展的組成員關系。這種靈活性為用戶提供了適合不同網絡規模的替代視圖，以及關于群體行為的不同見解。考慮到復雜網絡的時間行為，每個事件在網絡中具有以下時間關聯：

（1）時間段：定義的時間間隔；

（2）時間點+時長：起始時間點和時間段；

（3）多個時間點：起始點和結束點。

根據文獻[16]～文獻[18]的研究結果可知，鏈路預測方法存在局限性，它試圖通過獲取前一個時間步的快照，根據網絡增長的持續時間來預測復雜實體隨時間的演變。因此，我們需要檢查更多的時間步長以獲得更準確的預測結果。例如，目前社交網絡的狀態是通過傳統的社交網絡分析度量方法進行快照計算得出的，但是對于更多的時間步長（速度），度量使用網絡變化歷史來計算，而網絡變化歷史則通過時間統計來計算。

文獻[19]提出了一種明確包含時間和順序的網絡分析方法，適用于處理關注時間屬性的事件數據集（特定時間鏈接預測問題）。該方法通過節點排名預測實體和未來事件的排名，導致個體排名隨時間變化。實驗結果表明，這些方法可以準確預測組織結構，并對實體未來可能共同參與的情況進行排序。

文獻[20-21]描述了一種與時間變化相關的建模方法。其中歷史數據用于深化對未來相互作用的理解，從而更準確地預測未來的變化。這個模型可以用于研究個體關系的行為，但需要進行調整以模擬群體行為。

4 結 語

現如今，物聯網已經成為了研究的熱點之一。在物聯網中，各種設備和傳感器需要不斷向中心節點發送數據，并且這些數據必須及時、準確地到達目標節點，這個過程可以用網絡圖很好地描述，節點代表各終端，節點之間的邊代表它們的交互。鏈路預測技術可以用于優化復雜網絡下的數據傳輸鏈路，以保證數據能夠高效傳輸，從而提高復雜網絡的可靠性和性能。此外，鏈接預測還可用于其他方面，如一些應用程序，Facebook、Twitter，刑事調查，信息檢索等，以預測鏈接之間的未來關聯。在該研究中，鏈接預測分為2類。

首先，基于用于預測鏈接的特征，使用圖的結構屬性（例如節點度）。一些研究人員使用監督機器學習技術和概率模型來預測使用這些特征的鏈接。其次，研究人員將基于時間感知的時間特征進行鏈路預測。以往的鏈路預測方法精度較低，因為社會服務呈指數級增長，使得網絡具有動態性，單個快照不足以全面考慮，因此需要考慮特定時間間隔內的多個快照。此外，由于網絡的復雜性，需要更多的計算時間。由于鏈接預測在各個研究領域都有廣泛的應用，一篇文章無法對所有領域的研究進行全面綜述。因此，文中僅就在復雜網絡下基于局部特征、全局特征和時間感知的時間特征的鏈路預測研究進行綜述。文中總結了近年來在各種方法上進行的研究工作，并指出了現有研究所面臨的挑戰。我們希望這份調查能夠為對基于時間的特征屬性感興趣的研究人員提供有用的指導，這些特征屬性可用于最近的鏈接預測研究工作，并提供比以往更準確的結果。

在未來的工作中，我們將嘗試結合動態快速變化的復雜網絡中的真實數據，并利用時間感知特征以進行鏈接預測。我們計劃集成蟻群優化算法，以提高鏈路預測的準確性。

參考文獻

[1] FENG Y X，ZHANG Y X. A Method of link prediction intemporal directed net-work [J/OL]. Computer engineering and applications.

[2] YAN Y，XIN X W. Link prediction in directed network and its application in microblog [J]. Mathematical problems in engineering，2014，2014：1-8.

[3] NOWELL L D，KLEINBERG J. The link‐prediction problem for social net-works [J]. Journal of the American society for information science and technology，2007，58（7）：1019-1031.

[4] ADAMIC L A，ADAR E. Friends and neighbors on the web [J]. Social networks，2003，25（3）：211-230.

[5] ZHOU T，Lü L Y，ZHANG Y C. Predicting missing links via local information [J]. The European physical journal B，2009，71（4）：623-630.

[6] KATZ L. A new status index derived from sociometric analysis [J]. Psychometrika，1953，18（1）：39-43

[7] Lü L Y，JIN C H，ZHOU T. Similarity index based on local paths for link prediction of complex networks [J]. Physical review E，2009，80（4）：046122.

[8] LEICHT E A，HOLME P，NEWMAN M E J. Vertex similarity in networks [J]. Phys. Rev. E，2005.

[9] MUNASINGHE L，ICHISE R. Time aware index for link prediction in social net-works-data warehousing and knowledge discovery [Z]. Springer，2011.

[10] DUNLAVY M D，KOLDA G T，ACAR E. Temporal link prediction using matrix and tensor factorizations [J]. ACM transactions on knowledge discovery from Data （TKDD），2011，5（2）：1-27.

[11] Lü L Y，ZHOU T. Link prediction in complex networks：A survey [J]. in Physica A：Statistical mechanics and its applications，2011，390（6）：1150-1170.

[12] TANG J，MUSOLESI M，MASCOLO C，et al. Temporal distance metrics for social network analysis [Z]. In Proceedings of WOSN ‘09，2009.

[13] TYLENDA T，ANGELOVA R，BEDATHUR S. Towards time-aware link prediction in evolving Social networks [C]// In：Proceedings 3rd Workshop on Social Network Mining and Analysis （SNA-KDD’ 2009）：1-9.

[14] KOSTAKOS V. Temporal graphs [J]. Physica A，2009，388（6）：1007.

[15] UMANG S，NEVILLE J. Temporal-relational classifiers for predic-tion in evolving domains [C]// In：Proceedings Eighth IEEE International Conference ICDM ’08. On Data Mining，2008.

[16] HYUNMO K K H，GETOOR L，SINGH L. Visual analysis of dynamic group membership in temporal social networks [J]. SIGKDD explor newsl，2007，9（2）：13-21.

[17] JEREMY R，COOKE E. Link prediction and link detection in se-quences of large social network using temporal and local metrics [Z]. Liben Nowel，2006.

[18] LIBEN N D，KLEINBERG J. The link prediction problem for social net-works [C]// In：Proceedings 12th International Conference on Information and Knowledge Management，CIKM 2003.

[19] LIBEN N D，KLEINBERG J. The link prediction problem for social networks [J]. Journal of the American society for information science and technology，2007，58（7）：1019-1031.

[20] JOSHUA O M，HUTCHINS J，PADHRAIC S. Prediction and rank-ing algorithms for event-based network data [J]. SIGKDD explor. newsl.，2005，7（2）：23.

[21] SARKAR P，MOORE A W. Dynamic social network analysis using latent space models [J]. SIGKDD explor. Newsl.，2005，7（2）：31-40.

作者簡介：杜 科（2003—），女，本科在讀，研究方向為信息安全。