動態(tài)網(wǎng)絡(luò)下的鏈路預(yù)測研究

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

關(guān)鍵詞：復雜網(wǎng)絡(luò)；靜態(tài)網(wǎng)絡(luò)；動態(tài)網(wǎng)絡(luò)；物聯(lián)網(wǎng)；鏈路預(yù)測；時間感知

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

0 引 言

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

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

目前人們已經(jīng)做出了很大的努力來預(yù)測靜態(tài)網(wǎng)絡(luò)中的鏈路，然而實際情況是，世界上很少有網(wǎng)絡(luò)是靜態(tài)的。大部分網(wǎng)絡(luò)隨著時間的推移而變化，并攜帶其他時間信息，例如物聯(lián)網(wǎng)中網(wǎng)絡(luò)節(jié)點和邊緣的變化。由于物聯(lián)網(wǎng)是一個分布式系統(tǒng)，其中包含大量節(jié)點和設(shè)備，這些節(jié)點和設(shè)備可以在任何時間加入或離開網(wǎng)絡(luò)，導致網(wǎng)絡(luò)的拓撲結(jié)構(gòu)可能會動態(tài)變化，同時鏈路質(zhì)量也會因為干擾、距離、設(shè)備限制和其他因素而變化。因此，動態(tài)網(wǎng)絡(luò)的鏈路預(yù)測研究更具有實際意義?；诖?，文中綜述了動態(tài)網(wǎng)絡(luò)下鏈路預(yù)測的方法。

1 網(wǎng)絡(luò)表示

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

（1）有向：網(wǎng)絡(luò)中的邊是有方向的，即從一個節(jié)點指向另一個節(jié)點的箭頭有明確方向；

（2）有權(quán)：網(wǎng)絡(luò)中的邊有權(quán)重或者權(quán)值，表示2個節(jié)點之間的關(guān)系強度或者距離大??；

（3）有環(huán)：網(wǎng)絡(luò)中存在環(huán)路，即從一個節(jié)點出發(fā)，經(jīng)過若干條邊后可以回到該節(jié)點。其中，有向網(wǎng)絡(luò)中的環(huán)路必須是有向的，即沿箭頭的方向才能形成環(huán)路。

節(jié)點vi和節(jié)點vj之間有且只有一條連續(xù)邊，而且不存在ex=ey={vi， vj}的情況。有向網(wǎng)絡(luò)通常用鄰接矩陣和關(guān)聯(lián)矩陣表示。

（1）鄰接矩陣

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

（2）關(guān)聯(lián)矩陣

一個具有N個節(jié)點和M條邊的網(wǎng)絡(luò)可以用關(guān)聯(lián)矩陣N×M表示，表示為AC，矩陣元素ACix=1表示節(jié)點vi是邊ex的開始，矩陣元素ACix=-1表示節(jié)點vi是邊ex的結(jié)束，矩陣元素ACix=0表示節(jié)點vi不與邊ex相鄰。

（3）出入度

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

（1）

（4）聚類系數(shù)

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

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

對以上4個三角形結(jié)構(gòu)計算聚類系數(shù)，并由下列方程給出：

（2）

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

2 鏈路預(yù)測

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

2.1 鏈路預(yù)測描述

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

2.2 評價方法

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

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

2.2.1 AUC

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

（3）

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

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

（4）

2.2.2 Ranking Score

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

（5）

3 動態(tài)網(wǎng)絡(luò)下的鏈路預(yù)測

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

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

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

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

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

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

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

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

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

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

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

（3）多個時間點：起始點和結(jié)束點。

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

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

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

4 結(jié) 語

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

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

在未來的工作中，我們將嘗試結(jié)合動態(tài)快速變化的復雜網(wǎng)絡(luò)中的真實數(shù)據(jù)，并利用時間感知特征以進行鏈接預(yù)測。我們計劃集成蟻群優(yōu)化算法，以提高鏈路預(yù)測的準確性。

參考文獻

[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—），女，本科在讀，研究方向為信息安全。