吳翼騰，于洪濤，顧澤宇

（1.信息工程大學(xué) 信息技術(shù)研究所，鄭州 450002；2.中國(guó)人民解放軍61660 部隊(duì)，北京 100080）

0 概述

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

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

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

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

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

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

1 問(wèn)題描述和評(píng)價(jià)指標(biāo)

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

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

2 統(tǒng)一描述網(wǎng)絡(luò)結(jié)構(gòu)模型

2.1 統(tǒng)一描述網(wǎng)絡(luò)結(jié)構(gòu)模型定義

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

1）定義冪集：

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

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

特別地，當(dāng)i=0 時(shí)：

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

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

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

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

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

例如一個(gè)由3 個(gè)節(jié)點(diǎn)組成的網(wǎng)絡(luò)，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 階元素。設(shè)指定關(guān)系f為選取A1中包含節(jié)點(diǎn)對(duì){1,2} 的元素，則f[(A1)1]=D1={{{1,2}},{{1,2,3}}}，f[(A1)2]=D2={{{1,2},{1,2,3}}}，當(dāng)k≥3 時(shí)，f[(A1)k]=?。顯然為i+1 階集合。由于{1,2}為1 階元素，因此集合{{1,2}}為1 階集合。又如，Λ1={{1,2},{1,3},{1,2,3}}是A1的一個(gè)非空子集，即Λ1?A1，因此Λ1中的元素為1 階元素，Λ1為1階集合。同理，因此元素{{1,3},{1,2,3}}為2 階元素。

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

USI 模型本身可以看作加權(quán)網(wǎng)絡(luò)模型。只要當(dāng)i=0、k=2 時(shí)，即兩元素構(gòu)成0 階集合的指定關(guān)系f為任意兩節(jié)點(diǎn)對(duì)組成集合，p根據(jù)連邊權(quán)重設(shè)定后，USI 模型就可轉(zhuǎn)化為加權(quán)網(wǎng)絡(luò)模型。

2.2 統(tǒng)一描述網(wǎng)絡(luò)結(jié)構(gòu)模型性質(zhì)

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

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

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

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

3 基于統(tǒng)一描述網(wǎng)絡(luò)結(jié)構(gòu)模型的鏈路預(yù)測(cè)

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

3.1 集合劃分

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

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

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

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

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

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

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

3）當(dāng)i=1、k=2 時(shí)，按指定關(guān)系f3將f1劃分的0 階集合兩兩組成1 階集合：

3.2 概率估計(jì)

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

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

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

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

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

令：

解得：

如圖1 所示，在0 階集合中共有10 個(gè)節(jié)點(diǎn)、12 條連邊，則概率p的估計(jì)值為

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.4 與其他鏈路預(yù)測(cè)方法的對(duì)比分析

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

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

4 實(shí)驗(yàn)與結(jié)果分析

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

基于USI模型的鏈路預(yù)測(cè)方法在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 個(gè)網(wǎng)絡(luò)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)。8 個(gè)網(wǎng)絡(luò)數(shù)據(jù)集的統(tǒng)計(jì)信息如表1 所示，其中，|V|表示網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)，|E|表示網(wǎng)絡(luò)中的邊數(shù)，表示網(wǎng)絡(luò)中節(jié)點(diǎn)的平均度，表示網(wǎng)絡(luò)中節(jié)點(diǎn)對(duì)的平均距離，C表示網(wǎng)絡(luò)的平均集聚系數(shù)，r表示網(wǎng)絡(luò)的關(guān)聯(lián)系數(shù)，H表示度的分布熵。

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

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

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

表2 鏈路預(yù)測(cè)方法的AUC 結(jié)果比較Table 2 Comparison of AUC results of link prediction methods

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

5 結(jié)束語(yǔ)

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