基于統(tǒng)一描述網(wǎng)絡結構模型的鏈路預測方法

吳翼騰，于洪濤，顧澤宇

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

0 概述

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

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

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

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

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

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

1 問題描述和評價指標

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

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

2 統(tǒng)一描述網(wǎng)絡結構模型

2.1 統(tǒng)一描述網(wǎng)絡結構模型定義

定義1在統(tǒng)一描述網(wǎng)絡結構模型中，A0為網(wǎng)絡中所有節(jié)點組成的集合，集合族Dk中的元素Di也為集合。

1）定義冪集：

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

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

特別地，當i=0 時：

2）假設集合Di內(nèi)元素建立聯(lián)系的概率pi相同：

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

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

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

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

例如一個由3 個節(jié)點組成的網(wǎng)絡，A0={1,2,3}，根據(jù)定義2，元素1、2、3 都是0 階元素，根據(jù)定義3，A0是0 階集合。由于元素{?,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}=A1，因此元素{1,2}為1 階元素。設指定關系f為選取A1中包含節(jié)點對{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 模型是對隨機分塊模型和層次結構模型的一般化推廣。隨機分塊模型假設網(wǎng)絡被分成若干個群，兩個節(jié)點產(chǎn)生鏈路的概率只取決于節(jié)點所在的群，無法體現(xiàn)網(wǎng)絡的層次結構和重疊結構信息。層次結構模型將網(wǎng)絡用族譜樹的形式表示，網(wǎng)絡中|A0|個節(jié)點作為葉子節(jié)點，族譜樹通過|A0| -1 個非葉子節(jié)點將它們聯(lián)系起來。將每個非葉子節(jié)點賦予一個概率值，每兩個葉子節(jié)點連邊的概率用它們最近共同非葉子節(jié)點處的概率表示。層次結構模型中若一個節(jié)點從屬于某一葉子分支，其本身也屬于上一級非葉子節(jié)點所屬的葉子分支，即可以表示網(wǎng)絡的層次結構特性。但是，節(jié)點不可從屬于同級非葉子節(jié)點所屬的其他葉子分支，即無法體現(xiàn)網(wǎng)絡的重疊性。本質(zhì)上，層次結構模型可以包含隨機分塊模型。USI模型假設有某種共同特性的元素可以組成集合，集合中元素建立聯(lián)系的概率相同。若USI 模型的最高階集合為1 階集合，且所有1 階元素的交集為空集時，USI 模型退化為隨機分塊模型。若每個集合有且僅有2 個元素，且所有元素從屬于唯一的對應階集合時，USI 模型退化為層次結構模型，層次結構模型可以包含高階元素?；谠摲治?，層次結構模型是隨機分塊模型的推廣，USI 模型又是層次結構模型的推廣。由此可以進一步得出，隨機分塊模型和層次結構模型實際上是USI 模型從不同角度退化后的加權組合，加權系數(shù)由該模型的合理程度決定，屬于鏈路預測的前端融合方法。當給定指定關系f后，USI 模型可以用于鏈路預測，具體方法將在后文給出。

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

2.2 統(tǒng)一描述網(wǎng)絡結構模型性質(zhì)

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

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

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

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

3 基于統(tǒng)一描述網(wǎng)絡結構模型的鏈路預測

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

3.1 集合劃分

對于含有屬性信息和真實群組結構的網(wǎng)絡數(shù)據(jù)，可以根據(jù)該信息給出指定關系f確定各階集合的劃分組成。對于只含有節(jié)點和連邊拓撲信息的數(shù)據(jù)，只能通過算法識別和合理策略給出指定關系f?，F(xiàn)對只含有拓撲信息數(shù)據(jù)的集合進行分析。

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

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

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

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

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

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

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

3.2 概率估計

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

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

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

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

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

令：

解得：

如圖1 所示，在0 階集合中共有10 個節(jié)點、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階元素的最大可能連邊數(shù)定義如下：

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

如圖2（a）所示的1 階集合不存在交集，只需考慮集合之間的實際連邊數(shù)（為6）和可能最大的連邊數(shù)（為6×7=42），則概率p的估計值為=1/7。如圖2（b）所示的集合存在交集，因此實際連邊數(shù)僅考慮交集之外的實際連邊（為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的估計

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

3.3 基于并聯(lián)概率的鏈路預測得分確定

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

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

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

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

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

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

4 實驗與結果分析

基于USI 模型的鏈路預測方法在實驗過程中選取2 種社區(qū)發(fā)現(xiàn)算法：1）Reichardt［26］，該算法將社區(qū)結構理解為自旋組態(tài)，使其最小化自旋玻璃態(tài)的能量而得到一種社區(qū)劃分結果；2）SpectralClust［27］，對于圖G(V,E)，利用基于譜分解的圖劃分算法定義代價函數(shù)，求解優(yōu)化問題得到一種社區(qū)劃分結果。選取Reichardt算法的尺度參數(shù)為［3.0，2.5，2.0，1.5，1.0，0.5］，SpectralClust 算法的尺度參數(shù)為6，不同尺度參數(shù)的社區(qū)結構同時作為輸入，因此具有層次信息和重疊信息。選取網(wǎng)絡中的3 階環(huán)，即k=3。由Reichardt 算法、3 階環(huán)作為輸入的方法記為USI-1，由SpectralClust 算法、3 階環(huán)作為輸入的方法記為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 個網(wǎng)絡數(shù)據(jù)集上進行實驗。8 個網(wǎng)絡數(shù)據(jù)集的統(tǒng)計信息如表1 所示，其中，|V|表示網(wǎng)絡中的節(jié)點數(shù)，|E|表示網(wǎng)絡中的邊數(shù)，表示網(wǎng)絡中節(jié)點的平均度，表示網(wǎng)絡中節(jié)點對的平均距離，C表示網(wǎng)絡的平均集聚系數(shù)，r表示網(wǎng)絡的關聯(lián)系數(shù)，H表示度的分布熵。

表1 網(wǎng)絡數(shù)據(jù)集統(tǒng)計信息Table 1 Network dataset statistics

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

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

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

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

5 結束語

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