基于統一描述網絡結構模型的鏈路預測方法

吳翼騰，于洪濤，顧澤宇

（1.信息工程大學 信息技術研究所，鄭州 450002；2.中國人民解放軍61660 部隊，北京 100080）

0 概述

復雜網絡鏈路預測是指運用網絡結構信息對節點對之間存在連接的可能性進行預測［1-2］。鏈路預測具有很強的理論和實際應用價值，可以幫助人們認識復雜網絡演化機制與結構信息［3］，還可以為生物蛋白質結構網絡構建、電子商務商品推薦、資源貿易協調、電信用戶通聯關系挖掘等任務提供技術支持［4-5］。

鏈路預測方法主要分為基于網絡結構信息相似性、融合網絡多維度信息、基于網絡結構模型等方法。基于網絡結構信息進行鏈路預測的主要難點是找到網絡生成演化機理及生成鏈路的誘導因素。例如，無標度網絡僅由2 條基本假設（網絡是不斷增長的、增長過程中節點傾向于與度大的節點相連），即可推導出網絡中節點的度呈長尾分布這一共性規律［6］。這2 條基本假設通過網絡生成機理，解釋了度分布不呈正態分布的原因。同樣地，如何解釋網絡中鏈路的成因來預測未知鏈路也是鏈路預測的難點。

基于網絡結構信息定義節點對之間相似性的鏈路預測方法使用單一維度的網絡信息或直接明確定義多維度信息的關系，具有理論簡潔、效率較高的特點。呂琳媛等［7-8］將節點對的共同鄰居數賦予權重，提出共同鄰居加權的資源分配指標。YAO等［9-11］提出基于局部拓撲信息加權的相似性指標。劉樹新等［12］提出網絡中節點間資源傳輸機理的資源傳輸匹配度指標。BISWAS等［13-15］考慮網絡的社區信息，利用社區信息對經典相似性指標加權，或僅在節點所屬社區內計算經典相似性指標，提升鏈路預測準確度。基于相似性度量的鏈路預測方法通常是對微觀網絡結構進行建模，從節點對及其周圍的微觀結構出發，解析鏈路形成機理預測鏈路。

隨著網絡結構信息研究的深入，網絡多維度信息被充分挖掘。為進一步提高相似性指標的準確性和魯棒性，學者們提出融合網絡多維度信息的鏈路預測方法，例如，組合規則法、OWA 算子融合法［16］、AdaBoost 融合法［17］等基于相似性指標的后端融合方法［18］。基于機器學習或深度學習的鏈路預測方法將鏈路預測問題轉化為有無連邊的二分類問題，本質上也可將其看作多指標經分類器輸出的后端融合方法。吳翼騰等［19］詳細研究了后端融合方法的理論極限問題，提出并證明了采用組合方法進行鏈路預測的理論極限定理。后端融合方法主要針對數據建模，側重于預測的準確性，但卻犧牲了算法的可解釋性，難以解析網絡中鏈路形成的誘導因素［20］。

基于網絡結構模型的鏈路預測方法從宏觀上對網絡結構進行建模，首先給出網絡生成假設，然后根據網絡生成假設求出節點對產生鏈路的概率，最后利用全概率思想計算某條連邊的生成概率，主要包括隨機分塊模型［21-22］和層次結構模型［23］。隨機分塊模型假設節點間的連接概率取決于節點所在社區：同一社區內部節點連接概率相同，不同社區間連接概率僅與所在社區有關，通過隨機劃分節點所在社區，基于某種劃分計算社區內和社區間形成連邊的概率，并計算社區劃分的先驗概率，但無法處理重疊社區結構以及節點間的分級與層次結構。層次結構模型對節點間的層次結構進行建模，建立節點連接關系的譜系圖，與隨機分塊模型計算連接概率的核心思想相似，首先計算基于某種譜系圖和節點間生成連邊概率，然后計算譜系圖的先驗概率，最后采用全概率思想計算最終的鏈路形成概率。在基于網絡結構模型的鏈路預測方法中，連邊的綜合概率加權融合了多種子模型的連邊概率，但該融合方法不同于后端融合方法，需對網絡結構建模，因此將其概括為綜合網絡結構信息的前端融合方法。

隨機分塊模型和層次結構模型從不同角度給出了網絡結構描述方式［24］，但無法有效處理從宏觀、中觀網絡社區結構到微觀低階環或模體［25］結構中的重疊結構信息，而實際網絡中重疊結構無處不在。本文構建一種統一描述網絡結構模型，簡稱USI（Uniform-Structure-Information）模型，既包含節點的層次結構信息，又可使節點從屬于不同集合，并基于USI 模型提出一種鏈路預測方法，通過實驗以驗證該方法的有效性。

1 問題描述和評價指標

給定t時刻的網絡G(V,E)，其中，V和E分別表示節點集合和邊集合。鏈路預測的目的是預測未來的t′時刻將要出現的鏈路或消失的鏈路，或是預測當前t時刻網絡未觀測到的鏈路或錯誤鏈路［20］，即鏈路預測方法賦予節點對間鏈路預測的評分值，按照評分值的大小判定是否存在鏈路。

為了評估鏈路預測方法的準確性，需對網絡進行訓練集和測試集的劃分，鏈路預測方法僅允許運用訓練集進行預測。一般使用AUC（Area Under the Receiver Operation Characteristic Curve）衡量預測準確性。AUC 不受有無連邊兩類樣本非平衡性的影響（無連邊的節點對遠大于有連邊的節點對數量），可以理解為在測試集中隨機選擇一條邊的分數值比隨機選擇一條不存在的邊的分數值高的概率［7］，即每次從測試集中隨機選擇一條邊，再從不存在的邊中隨機選擇一條邊，若前者高則加1 分，若相等則加0.5 分，這樣獨立比較n次。若有n′次測試集得分高，有n″次兩者相等，則AUC 定義如下：

2 統一描述網絡結構模型

2.1 統一描述網絡結構模型定義

定義1在統一描述網絡結構模型中，A0為網絡中所有節點組成的集合，集合族Dk中的元素Di也為集合。

1）定義冪集：

對任意i，Ai中具有指定關系f的元素可以組成集合族Dk,Dk={D1,D2,…，Dn}。

其中：|Ai|表示集合Ai的勢，即集合Ai中元素的個數。

特別地，當i=0 時：

2）假設集合Di內元素建立聯系的概率pi相同：

USI 模型可以解釋無向網絡中各種節點的連接和組織關系，為網絡中各類節點的層次關系、重疊關系等建立簡明清晰的表示方法。定義1 中的第1 個部分可以理解為有共同特性的元素可以組成集合，第2 個部分可以理解為集合內部元素間發生聯系的概率相同。

根據模型定義，組成集合的元素可以是集合或非集合。當集合中元素為非集合時，表示節點對之間存在鏈路的概率；當集合中的元素為集合時，表示集合與集合建立聯系的概率。例如：一個班級中的所有同學組成一個集合，集合中元素為非集合，p表示該班級任意兩個同學存在聯系的概率；一個學校所有班級組成一個集合，集合中元素班級仍為集合，p表示班級之間建立聯系的概率，間接表示班級之間同學建立聯系的概率。

定義2在USI 模型中，Ai及其非空子集的元素為i階元素，i=1,2,…。i階元素記為X(i)，2 階以上元素稱為高階元素。

定義3在USI 模型中，集合所含元素的階數稱為集合的階。i階集合記為X(i)，2 階以上集合稱為高階集合。

例如一個由3 個節點組成的網絡，A0={1,2,3}，根據定義2，元素1、2、3 都是0 階元素，根據定義3，A0是0 階集合。由于元素{?,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}=A1，因此元素{1,2}為1 階元素。設指定關系f為選取A1中包含節點對{1,2} 的元素，則f[(A1)1]=D1={{{1,2}},{{1,2,3}}}，f[(A1)2]=D2={{{1,2},{1,2,3}}}，當k≥3 時，f[(A1)k]=?。顯然為i+1 階集合。由于{1,2}為1 階元素，因此集合{{1,2}}為1 階集合。又如，Λ1={{1,2},{1,3},{1,2,3}}是A1的一個非空子集，即Λ1?A1，因此Λ1中的元素為1 階元素，Λ1為1階集合。同理，因此元素{{1,3},{1,2,3}}為2 階元素。

USI 模型是對隨機分塊模型和層次結構模型的一般化推廣。隨機分塊模型假設網絡被分成若干個群，兩個節點產生鏈路的概率只取決于節點所在的群，無法體現網絡的層次結構和重疊結構信息。層次結構模型將網絡用族譜樹的形式表示，網絡中|A0|個節點作為葉子節點，族譜樹通過|A0| -1 個非葉子節點將它們聯系起來。將每個非葉子節點賦予一個概率值，每兩個葉子節點連邊的概率用它們最近共同非葉子節點處的概率表示。層次結構模型中若一個節點從屬于某一葉子分支，其本身也屬于上一級非葉子節點所屬的葉子分支，即可以表示網絡的層次結構特性。但是，節點不可從屬于同級非葉子節點所屬的其他葉子分支，即無法體現網絡的重疊性。本質上，層次結構模型可以包含隨機分塊模型。USI模型假設有某種共同特性的元素可以組成集合，集合中元素建立聯系的概率相同。若USI 模型的最高階集合為1 階集合，且所有1 階元素的交集為空集時，USI 模型退化為隨機分塊模型。若每個集合有且僅有2 個元素，且所有元素從屬于唯一的對應階集合時，USI 模型退化為層次結構模型，層次結構模型可以包含高階元素。基于該分析，層次結構模型是隨機分塊模型的推廣，USI 模型又是層次結構模型的推廣。由此可以進一步得出，隨機分塊模型和層次結構模型實際上是USI 模型從不同角度退化后的加權組合，加權系數由該模型的合理程度決定，屬于鏈路預測的前端融合方法。當給定指定關系f后，USI 模型可以用于鏈路預測，具體方法將在后文給出。

USI 模型本身可以看作加權網絡模型。只要當i=0、k=2 時，即兩元素構成0 階集合的指定關系f為任意兩節點對組成集合，p根據連邊權重設定后，USI 模型就可轉化為加權網絡模型。

2.2 統一描述網絡結構模型性質

證明根據命題1，i階集合經1 次元素的并集運算g可降為i-1 階集合；該i-1 階集合經第2 次元素的并集運算g可降為i-2 階集合；以此類推，經過i次元素的并集運算g可降為0 階集合。證畢。

推論2i(i≥2)階集合可以將其元素看作i-1 階集合，對每個i-1 階集合通過集合中元素的并集運算g的i-1 次迭代，使原i階集合降階為1 階集合。

證明將i階集合的每個元素看作i-1 階集合，根據推論1，每個i-1 階集合經過i-1 次元素的并集運算g的迭代，可降為0 階集合，則原i階集合降為以0 階集合為元素構成的1 階集合。證畢。

設3階集合X(3)=是3 階元素。根據推論1，該3 階集合可降階為2 階集合，如式（8）所示。該2 階集合可以降階為1 階集合，如式（9）所示。該1 階集合可以降階為0 階集合，如式（10）所示。

3 基于統一描述網絡結構模型的鏈路預測

基于USI 模型的鏈路預測方法的基本假設是兩個節點發生聯系的概率主要依賴于其所在的群體（集合）。因此，基于USI 模型的鏈路預測方法首先根據可利用的信息給出模型中的集合劃分，其次利用最大似然估計法估計概率p，最后假設各條路徑產生的聯系是相互獨立的，根據并聯概率給出鏈路預測得分。

3.1 集合劃分

對于含有屬性信息和真實群組結構的網絡數據，可以根據該信息給出指定關系f確定各階集合的劃分組成。對于只含有節點和連邊拓撲信息的數據，只能通過算法識別和合理策略給出指定關系f。現對只含有拓撲信息數據的集合進行分析。

根據USI 模型可知，節點對之間鏈路的成因取決于節點對所屬的集合及其概率。理論上，無論何種規模的網絡結構均可被USI 模型表示：只需將該種網絡結構視作集合，并建立集合元素間的概率。根據實際應用場景，本文主要給出0 階和1 階集合的劃分方式。

對于0 階集合，復雜網絡的社區發現算法給出了針對僅含拓撲信息數據的0 階集合劃分方式。USI 模型的鏈路預測方法中引入社區發現算法，按特定社區發現算法劃分的結果，規定指定關系f劃分0 階集合。網絡中的環也是十分重要的網絡結構，1 個長度為h的環，是由h個節點{v1,v2,…,vh}和h條邊{,,…,,}組成的封閉回路，其中，表示邊，且=。環的存在尤其是低階環的數量對網絡功能有重要影響。USI 模型的鏈路預測方法也考慮網絡中的低階環作為0 階集合的劃分方式。

對于1 階集合，考慮社區發現算法劃分0 階集合兩兩交互作用的情況，將任意兩個0 階集合組成1 階集合。為減少計算量，估計p時可設置閾值限定1 階集合概率p的建立范圍，且低階環不劃分1 階集合。由于僅含拓撲信息，信息量有限，因此暫不考慮2 階以上集合的劃分。

按照上述分析，給出指定關系f的如下3 種策略：

1）當i=0、k=1，2，…，|A0|時，按社區發現算法的劃分結果作為指定關系f1劃分0 階集合。假設社區發現算法劃分的全體社區結構為集合P，P={V1,V2,…,Vn}，則指定關系f1表示如下：

2）當i=0、k=1，2，…，|A0|時，按指定關系f2將只差1 條邊構成k階環的元素組成0階集合：

3）當i=1、k=2 時，按指定關系f3將f1劃分的0 階集合兩兩組成1 階集合：

3.2 概率估計

根據集合階數的不同，概率p的估計可以分為3 種情況，分別為0 階集合上概率p的估計、1 階集合上概率p的估計以及高階集合上概率p的估計。

3.2.1 0 階集合X(0)上概率p的估計

對于0 階集合X(0)上概率p的估計，假設：

在僅含0 階元素組成的集合中，元素與元素間只有連邊與非連邊，概率p即定義為元素連邊的概率。集合中元素連邊數為隨機變量X，X服從B(N,p)的二項分布，其中，N為集合中元素的最大可能連邊數，N=對0 階集合上概率p的估計采用極大似然估計法，似然函數表示如下：

其中：x是0 階集合觀測到的實際連邊數。

令：

解得：

如圖1 所示，在0 階集合中共有10 個節點、12 條連邊，則概率p的估計值為

圖1 0 階集合上概率p 的估計示例Fig.1 Example of estimating probability p on 0-order set

3.2.2 1 階集合X(1)上概率p的估計

對于1 階集合X(1)上概率p的估計，假設：

考慮到1 階元素可能存在交集，假設：

集合中1階元素的最大可能連邊數定義如下：

因此對于1 階集合X(1)，集合中1 階元素間僅存在0 階元素的連邊與非連邊，問題同樣轉化為二項分布B(N,p)的p值估計問題，估計方法與3.2.1 節相同。

如圖2（a）所示的1 階集合不存在交集，只需考慮集合之間的實際連邊數（為6）和可能最大的連邊數（為6×7=42），則概率p的估計值為=1/7。如圖2（b）所示的集合存在交集，因此實際連邊數僅考慮交集之外的實際連邊（為7）和可能的最大連邊（為9×5=45），則概率p的估計值為

圖2 1 階集合上概率p 的估計示例Fig.2 Examples of estimating probability p on 1-order set

3.2.3 高階集合X(i)(i≥2)上概率p的估計

根據推論2，將高階集合通過元素的并集運算迭代降為1 階集合后，按照1 階集合上概率p的估計方法進行求解。

3.3 基于并聯概率的鏈路預測得分確定

由于USI 模型中同一節點可以從屬于不同階的不同集合，存在兩節點對產生聯系的多條路徑，與生活中人際交往十分類似，每增加一條兩節點產生聯系的路徑，則兩節點產生聯系的概率隨之增大，因此采用節點對之間各條路徑產生聯系的概率值的并聯概率作為最終鏈路預測得分。假設產生聯系的各條路徑在相互獨立的條件下，最終鏈路預測得分可以表示如下：

其中：sxy為節點對xy的最終鏈路預測得分，即連邊概率為節點對在第i個共同集合內連邊的概率；Nxy為節點對xy所處的共同集合個數。

按照USI 模型設計，各種規模的網絡結構對鏈路形成的影響，主要體現在鏈路處于何種網絡結構之中。無論何種網絡結構，USI 模型都將其視為集合以及集合中元素的連接概率。因此，鏈路的形成主要由節點對所屬集合及其概率決定，節點對從屬不同集合，則鏈路的形成由這些集合的共同作用效果決定。本文方法采用簡單的概率并聯策略，綜合衡量不同集合的共同作用效果。

3.4 與其他鏈路預測方法的對比分析

基于USI 模型的鏈路預測方法屬于鏈路預測的前端融合方法。前端融合方法主要包括基于拓撲信息［10-11］、基于社區信息［13-15］加權的相似性、基于網絡結構模型等［21-23］方法，一般具有很好的解釋性，物理意義明確，側重于直接從網絡的生成演化規律出發進行預測，弱化從數據中學習模式。后端融合方法包括基于相似性的指標融合方法［16-18］、基于機器學習的分類方法［20］等，提高預測準確率的機理是將多維度網絡信息擬合成準確率的多元函數，并對目標函數進行優化，使準確率達到最大，側重于從數據中提取特征，以準確率為最終優化目標。因此，前端融合方法的準確率整體低于后端融合方法，尤其是深度學習方法。

USI 模型的鏈路預測方法基于基本假設：兩節點發生聯系的概率主要依賴于其所在群體。使用USI 模型的定義來表述：若節點對從屬于哪個集合，則使用哪個集合的概率p來衡量節點對的關系；若節點對從屬于多個集合，則使用這些集合共同作用的效果（即概率的并聯）衡量節點對之間的關系。由于USI 模型可以將多維度網絡結構信息（包括已知的真實網絡結構信息）輸入進來，因此基于USI 模型的鏈路預測可以綜合利用網絡的層次結構、重疊結構、微觀結構等網絡結構信息。基于以上信息，使用節點對從屬集合的連接概率解釋鏈路的生成方式進行鏈路預測。

4 實驗與結果分析

基于USI 模型的鏈路預測方法在實驗過程中選取2 種社區發現算法：1）Reichardt［26］，該算法將社區結構理解為自旋組態，使其最小化自旋玻璃態的能量而得到一種社區劃分結果；2）SpectralClust［27］，對于圖G(V,E)，利用基于譜分解的圖劃分算法定義代價函數，求解優化問題得到一種社區劃分結果。選取Reichardt算法的尺度參數為［3.0，2.5，2.0，1.5，1.0，0.5］，SpectralClust 算法的尺度參數為6，不同尺度參數的社區結構同時作為輸入，因此具有層次信息和重疊信息。選取網絡中的3 階環，即k=3。由Reichardt 算法、3 階環作為輸入的方法記為USI-1，由SpectralClust 算法、3 階環作為輸入的方法記為USI-2。

基于USI模型的鏈路預測方法在FB（Football）［28］、NS（Netscience）［29］、LT（London transport1）［30］、CKM-3［31］、A01［32］、ER（Euroroad）［33］、OP（Opsahl_powergrid）［34］、FWFB［35］8 個網絡數據集上進行實驗。8 個網絡數據集的統計信息如表1 所示，其中，|V|表示網絡中的節點數，|E|表示網絡中的邊數，表示網絡中節點的平均度，表示網絡中節點對的平均距離，C表示網絡的平均集聚系數，r表示網絡的關聯系數，H表示度的分布熵。

表1 網絡數據集統計信息Table 1 Network dataset statistics

在每個數據集上計算節點對的鏈路預測得分，每個數據集單獨計算10 次，每次獨立劃分訓練集和測試集，訓練集和測試集的占比分別為90%和10%，最終取10 次計算的平均值作為最終鏈路預測結果。

選取若干具有代表性的基于節點相似性的鏈路預測方法進行性能對比，包括基于共同鄰居的CN［36］方法、基于共同鄰居和節點度加權的AA［37］和RA［8］方法、偏好連接相似性的PA［38］方法、基于局部路徑的LP［8］方法、基于 隨機游走的LRW［39］和SRW［39］方法（后面的數字表示步數，例如LRW4 表示隨機游走的步數為4）、全局相似性方法ACT［39］等10 種方法。將AUC 指標作為評價指標，得到如表2 所示的實驗結果，其中排名前2 的指標值用加粗字體標示。由表2 中實驗數據可得知，僅使用網絡社區結構和3 階環信息的USI 模型的鏈路預測方法可顯著提升局部結構相似性和全局相似性方法的AUC 指標。尤其在LT、ER、OP 數據集上，USI 模型的AUC 達到0.9 左右，相比其他基于節點相似性的鏈路預測方法的最優值提升了0.075～0.143，預測準確性顯著提升，從而驗證了不同規模的網絡結構信息對鏈路形成的影響。

表2 鏈路預測方法的AUC 結果比較Table 2 Comparison of AUC results of link prediction methods

從方法效率上看，設網絡節點數為N1，隨機游走的步數為n1，網絡中節點平均度為k1，則CN、AA、RA、PA 的時間復雜度為的時間復雜度為LRW、SRW 的時間復雜度為ACT 的時間復雜度為基于USI 模型的鏈路預測方法的時間復雜度主要分為劃分社區結構、集合上度量p的估計、計算并聯概率3 個部分。Reichardt 算法的時間復雜度為SpectralClust算法的時間復雜度為O(N1)。設 Reichardt、SpectralClust兩種社區發現算法劃分了M(M?N1)個社區結構，組成M個0 階集合和CM2個1 階集合，則根據式（22），0 階集合和1 階集合上概率p的估計時間復雜度分別為O(M)和3 階環組成的0 階集合上概率p的估計可以等價轉換為1 次稀疏矩陣的乘法和歸一化操作，時間復雜度為設共有個節點對同時從屬于2 個以上集合，設N3表示節點對所屬共同集合個數的平均值，則根據式（27）并聯概率的時間復雜度為O(N3?N2) ≈N3O(N2)。因此，USI-1 的時間復雜度約為USI-2的時間復雜度約為O(N1+M2+N2)。由實驗結果可知，USI-1 方法的鏈路預測準確性普遍高于USI-2 方法，預測準確性的提升是以方法的時間復雜度換取的，也間接說明網絡中觀社區結構質量對鏈路預測具有重要影響，進而驗證了基于USI 模型的鏈路預測方法假設的合理性。對于大規模網絡，可選用USI-2 方法，或在集合的劃分中選用其他時間復雜度較低的社區發現算法。另外，1 階集合的劃分具有靈活性，在大規模網絡中可靈活調整1 階集合的劃分數量，降低時間復雜度。

5 結束語

本文采用笛卡兒積、冪集等概念對多維度網絡特征進行統一描述，建立統一描述網絡結構模型（USI），并提出一種基于USI 模型的鏈路預測方法。該方法利用USI 模型對輸入信息進行前端融合，描述實際網絡的演化機理，并且明確了網絡規模對鏈路形成的影響。實驗結果驗證了基于USI 模型的鏈路預測方法的有效性。后續將融合其他的網絡結構信息以及連邊概率的組合方式，進一步提高鏈路預測準確率。此外，當USI 模型輸入僅為社區發現算法劃分的社區結構信息時，即可利用USI 模型的AUC 值對重疊與非重疊社區結構的劃分質量進行評價，下一步也將對此進行深入研究。