譚索怡 祁明澤 吳俊 呂欣?

1)(國(guó)防科技大學(xué)系統(tǒng)工程學(xué)院,長(zhǎng)沙 410073)

2)(國(guó)防科技大學(xué)文理學(xué)院,長(zhǎng)沙 410073)

3)(北京師范大學(xué)復(fù)雜系統(tǒng)國(guó)際科學(xué)中心,珠海 519087)

近年來(lái)鏈路預(yù)測(cè)的理論和實(shí)證研究發(fā)展迅速,大部分工作關(guān)注于提出更精確的預(yù)測(cè)算法.事實(shí)上,鏈路預(yù)測(cè)的前提是網(wǎng)絡(luò)的結(jié)構(gòu)本身能夠被預(yù)測(cè),這種“可被預(yù)測(cè)的程度”可以看作是網(wǎng)絡(luò)自身的基本屬性.本文擬從特征譜的視角去解釋網(wǎng)絡(luò)的鏈路可預(yù)測(cè)性,并刻畫網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)信息,通過(guò)對(duì)網(wǎng)絡(luò)特征譜進(jìn)行分析,構(gòu)造了復(fù)雜網(wǎng)絡(luò)鏈路可預(yù)測(cè)性評(píng)價(jià)指標(biāo).通過(guò)該指標(biāo)計(jì)算和分析不同網(wǎng)絡(luò)的鏈路可預(yù)測(cè)性,能夠在選擇算法前獲取目標(biāo)網(wǎng)絡(luò)能夠被預(yù)測(cè)的難易程度,解決到底是網(wǎng)絡(luò)本身難以預(yù)測(cè)還是預(yù)測(cè)算法不合適的問(wèn)題,為復(fù)雜網(wǎng)絡(luò)與鏈路預(yù)測(cè)算法的選擇和匹配問(wèn)題提供幫助.

1 引 言

近年來(lái),復(fù)雜網(wǎng)絡(luò)研究迅速發(fā)展,其學(xué)科分支在包括數(shù)學(xué)、統(tǒng)計(jì)物理、生物醫(yī)學(xué)、化學(xué)、計(jì)算機(jī)等領(lǐng)域掀起研究熱潮[1?5].在現(xiàn)代信息科學(xué)領(lǐng)域中,鏈路預(yù)測(cè)作為將復(fù)雜網(wǎng)絡(luò)與信息科學(xué)連接起來(lái)的重要橋梁,關(guān)心的是信息科學(xué)中最基本的問(wèn)題—缺失信息的預(yù)測(cè)和還原問(wèn)題[6,7].即在一個(gè)網(wǎng)絡(luò)中,如何基于已知連邊信息,刻畫網(wǎng)絡(luò)的相似性,進(jìn)而重現(xiàn)因?yàn)閿?shù)據(jù)缺失尚未觀察到的連邊,或者預(yù)測(cè)未來(lái)網(wǎng)絡(luò)演化過(guò)程中將要出現(xiàn)的連邊.

目前鏈路預(yù)測(cè)相關(guān)理論方法研究主要圍繞基于馬爾科夫鏈、最大似然估計(jì)、概率模型、網(wǎng)絡(luò)結(jié)構(gòu)相似性等數(shù)學(xué)領(lǐng)域和統(tǒng)計(jì)物理的觀點(diǎn)和方法展開(kāi).早期的鏈路預(yù)測(cè)領(lǐng)域普遍關(guān)注的是馬爾科夫鏈和機(jī)器學(xué)習(xí),主要存在著計(jì)算復(fù)雜度較高,參數(shù)設(shè)置不具有普適性等問(wèn)題[8].也有學(xué)者提出從似然分析的角度構(gòu)建鏈路預(yù)測(cè)框架,比較經(jīng)典的有層次結(jié)構(gòu)模型[9]和隨機(jī)分塊模型[10].Pan等[11]提出的閉路模型,擁有比前兩者更好的預(yù)測(cè)精度.似然分析的優(yōu)點(diǎn)在于能夠從理論上幫助我們理解網(wǎng)絡(luò)結(jié)構(gòu)特征,然而受限其自身理論的復(fù)雜性,這類方法不是應(yīng)用性很強(qiáng)的方法,即使構(gòu)思巧妙,在處理大規(guī)模網(wǎng)絡(luò)時(shí)也會(huì)顯得吃力.最早由 Taskar等[12]提出的概率模型是數(shù)據(jù)挖掘領(lǐng)域的傳統(tǒng)模型,該模型在預(yù)測(cè)時(shí)同時(shí)運(yùn)用了網(wǎng)絡(luò)的結(jié)構(gòu)信息和節(jié)點(diǎn)的屬性信息,概率模型擁有較高的預(yù)測(cè)精確度,但是同時(shí)產(chǎn)生的高計(jì)算復(fù)雜度以及其參數(shù)設(shè)置存在非普適性,都限制了該類方法的應(yīng)用范圍.得益于David和Kleinberg[13]在2007年有關(guān)鏈路預(yù)測(cè)結(jié)構(gòu)相似性的論文,基于網(wǎng)絡(luò)結(jié)構(gòu)相似性的鏈路預(yù)測(cè)問(wèn)題在近年受到越來(lái)越多的關(guān)注.Zhou等[14]把鏈路預(yù)測(cè)問(wèn)題和評(píng)價(jià)指標(biāo)都進(jìn)行了簡(jiǎn)化,很多研究人員開(kāi)始利用同樣的數(shù)據(jù)和指標(biāo)分析鏈路預(yù)測(cè)問(wèn)題.基于相似性的算法,作為最簡(jiǎn)單的鏈路預(yù)測(cè)算法框架,其中一系列算法復(fù)雜性低但預(yù)測(cè)精度不錯(cuò)的局部相似性指標(biāo)的提出,大幅度增加了鏈路預(yù)測(cè)在超大規(guī)模網(wǎng)絡(luò)中的可應(yīng)用性.

利用鏈路預(yù)測(cè)算法精準(zhǔn)地預(yù)測(cè)網(wǎng)絡(luò)的未知結(jié)構(gòu)有著廣泛的應(yīng)用前景.例如,在軍事對(duì)抗中,通常只能偵測(cè)到敵方作戰(zhàn)網(wǎng)絡(luò)的部分結(jié)構(gòu)信息,如果我們可以獲得更多更準(zhǔn)確的信息,就可以制定一定的優(yōu)先級(jí)規(guī)則或重要性標(biāo)準(zhǔn)來(lái)選擇性地攻擊網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)或連邊[15,16];在生物實(shí)驗(yàn)中,研究人員需要通過(guò)大量的實(shí)驗(yàn)研究去推斷探索細(xì)胞組分內(nèi)部的交互作用,一個(gè)具有指導(dǎo)作用的預(yù)測(cè)結(jié)果能有效降低實(shí)驗(yàn)成本并幫助人類理解生物網(wǎng)絡(luò)連邊演化機(jī)制的規(guī)律[17,18];社交網(wǎng)絡(luò)中,讀懂用戶的興趣偏好和喜怒哀樂(lè),對(duì)企業(yè)的發(fā)展事至關(guān)重要,一個(gè)好的“猜你要關(guān)注”推薦能夠牢牢地黏住老用戶、吸引新用戶[19,20].此外,一個(gè)優(yōu)秀的鏈路預(yù)測(cè)算法往往蘊(yùn)含著一種可能的網(wǎng)絡(luò)演化機(jī)制[21?24].遺憾的是,除非站在上帝視角,否則沒(méi)有人能判斷一個(gè)鏈路預(yù)測(cè)算法是否足夠精準(zhǔn).如果網(wǎng)絡(luò)的節(jié)點(diǎn)對(duì)之間隨機(jī)連接,任何算法可能都會(huì)無(wú)功而返,難以做出有效預(yù)測(cè);相反,面對(duì)一個(gè)有特定的連邊演化機(jī)制,非常規(guī)則的網(wǎng)絡(luò),一個(gè)足夠優(yōu)秀的方法能夠?qū)崿F(xiàn)精度很高的預(yù)測(cè).此外,即使是同一個(gè)網(wǎng)絡(luò),不同鏈路預(yù)測(cè)算法的準(zhǔn)確性也不盡相同,這種精度值只能相對(duì)地反映出網(wǎng)絡(luò)對(duì)于某種特定預(yù)測(cè)算法的預(yù)測(cè)精度,算法不同,精度也隨之改變,并不能刻畫網(wǎng)絡(luò)自身的固有的鏈路可預(yù)測(cè)性,很多時(shí)候,我們都面臨著是預(yù)測(cè)算法不合適還是網(wǎng)絡(luò)本身就難以預(yù)測(cè)這樣一個(gè)網(wǎng)絡(luò)與算法的選擇和匹配問(wèn)題.

顯然,網(wǎng)絡(luò)中待預(yù)測(cè)的連邊集合與網(wǎng)絡(luò)中不存在的連邊集合交集為空集,無(wú)論預(yù)測(cè)的準(zhǔn)確性和效率如何,理論上我們總可以通過(guò)無(wú)限加邊命中所有待預(yù)測(cè)的鏈接.然而這種上界是沒(méi)有價(jià)值的,不考慮成本的加邊會(huì)帶來(lái)巨大的成本消耗和結(jié)構(gòu)噪音,這樣的情況顯然偏離了鏈路預(yù)測(cè)的初衷.如果能夠獲悉一個(gè)網(wǎng)絡(luò)的鏈路信息能夠多大程度被預(yù)測(cè)出來(lái),就能夠提供一個(gè)導(dǎo)向,確定當(dāng)前算法是否接近或者已經(jīng)達(dá)到目標(biāo)網(wǎng)絡(luò)的可預(yù)測(cè)上限.因此,刻畫網(wǎng)絡(luò)多大程度上能夠被預(yù)測(cè)是鏈路預(yù)測(cè)中首先需要解決的問(wèn)題,這個(gè)問(wèn)題在相關(guān)文獻(xiàn)中被稱為復(fù)雜網(wǎng)絡(luò)的鏈路可預(yù)測(cè)性問(wèn)題.

近年來(lái)鏈路預(yù)測(cè)的理論和實(shí)證研究發(fā)展迅速,但絕大部分研究的目的都是希望提出更準(zhǔn)確的預(yù)測(cè)算法[25,26],關(guān)于復(fù)雜網(wǎng)絡(luò)鏈路可預(yù)測(cè)性的研究起步較晚,相關(guān)成果少見(jiàn)報(bào)道.許小可等[27]最早從理論上比較了各種算法的優(yōu)劣,分析多個(gè)網(wǎng)絡(luò)演化過(guò)程中形成鏈接的兩個(gè)節(jié)點(diǎn)之間的拓?fù)渚嚯x分布,闡明了傳統(tǒng)基于共同鄰居相似性指標(biāo)可有效進(jìn)行鏈路預(yù)測(cè)的機(jī)理,從理論上分析了9 種基于共同鄰居相似性算法的預(yù)測(cè)上限.Lü等[28]提出結(jié)構(gòu)一致性的概念,認(rèn)為網(wǎng)絡(luò)“可被預(yù)測(cè)的程度”,是網(wǎng)絡(luò)的一種重要固有屬性.通過(guò)對(duì)已知網(wǎng)絡(luò)進(jìn)行擾動(dòng),刻畫重構(gòu)的鄰接矩陣和真實(shí)鄰接矩陣的差異.如果丟失的連邊沒(méi)有顯著改變網(wǎng)絡(luò)的結(jié)構(gòu),那么這個(gè)網(wǎng)絡(luò)是可預(yù)測(cè)的,即網(wǎng)絡(luò)的結(jié)構(gòu)一致性越強(qiáng),網(wǎng)絡(luò)可預(yù)測(cè)性越好.熵被廣泛用來(lái)測(cè)量物理系統(tǒng)中的無(wú)序度,Yin等[29]設(shè)計(jì)了基于證據(jù)推理(Dempster-Shafer theory)的鏈路預(yù)測(cè)算法,從香農(nóng)信息熵的視角出發(fā),分析了網(wǎng)絡(luò)鏈路信息的可預(yù)測(cè)性.

本文擬從特征譜的視角去理解網(wǎng)絡(luò)拓?fù)湫畔?并刻畫網(wǎng)絡(luò)的鏈路可預(yù)測(cè)性.首先基于特征譜理論給出復(fù)雜網(wǎng)絡(luò)鏈路可預(yù)測(cè)性的數(shù)學(xué)描述,提出可預(yù)測(cè)性指標(biāo).在此基礎(chǔ)上,通過(guò)計(jì)算和分析不同實(shí)證網(wǎng)絡(luò)的鏈路可預(yù)測(cè)性,驗(yàn)證該指標(biāo)的有效性.

2 鏈路預(yù)測(cè)問(wèn)題描述

在本文的研究中,主要討論無(wú)向無(wú)權(quán)網(wǎng)絡(luò).令G(V,E)表示無(wú)向無(wú)權(quán)網(wǎng)絡(luò),V 表示節(jié)點(diǎn),E 表示連邊.令 U=N(N-1)/2 表示連邊的全集.對(duì)于網(wǎng)絡(luò)中未連邊的節(jié)點(diǎn)對(duì)(vi,vj),可以通過(guò)某種預(yù)測(cè)算法得到其得分矩陣,將所有未連邊列表中節(jié)點(diǎn)對(duì)的得分降序排列,排在前面的節(jié)點(diǎn)對(duì)之間產(chǎn)生鏈接的可能性大.

在網(wǎng)絡(luò)進(jìn)行鏈路預(yù)測(cè)之前,我們并不知道網(wǎng)絡(luò)缺失的部分和未來(lái)演化中可能出現(xiàn)的連邊連接情況,因此,在實(shí)驗(yàn)中,將網(wǎng)絡(luò)中已有的連邊集合E劃分為訓(xùn)練集 ET和測(cè)試集 EP.顯然,E=ET∪EP,ET∩EP=? .鏈路預(yù)測(cè)算法通過(guò)學(xué)習(xí)訓(xùn)練集 ET中的相似性進(jìn)行預(yù)測(cè),并通過(guò)測(cè)試集 EP檢測(cè)算法預(yù)測(cè)效果,測(cè)試集中存在的預(yù)測(cè)連邊越多,算法的準(zhǔn)確性越高.其中,數(shù)據(jù)集的劃分存在多種方式,為排除其干擾,本文所有實(shí)驗(yàn)中均采用隨機(jī)抽樣法.常見(jiàn)的算法評(píng)價(jià)指標(biāo)有 AUC(area under the receiver operating characteristic curve)[30],精 確度(precision)[31]和排序分(ranking score)[32],本文選用 precision 對(duì)預(yù)測(cè)結(jié)果進(jìn)行評(píng)價(jià).precision 定義為在前 L 條邊的預(yù)測(cè)中,正確預(yù)測(cè)連邊的比例.如果有 m 條邊被正確預(yù)測(cè),則 precision 的定義為

為了更好地解釋鏈路預(yù)測(cè)問(wèn)題,圖1給出了一個(gè)簡(jiǎn)單的例子.圖1(a)為8個(gè)節(jié)點(diǎn)和13 條連邊的完全信息網(wǎng)絡(luò).我們采取隨機(jī)抽樣的方法選擇3條連邊作為測(cè)試集,如圖 1(b)中黃色連邊所示,顯然,訓(xùn)練集包含10 條連邊.由于8 個(gè)節(jié)點(diǎn)的全連通網(wǎng)絡(luò)共有28 條連邊,則未連邊的數(shù)目為 2 8-10=18 .選擇一種鏈路預(yù)測(cè)算法,對(duì)18 條未知連邊進(jìn)行打分,并將得分按從大到小排序,精確度越高的算法能更多地將測(cè)試集中的3 條連邊 { e15,e17,e34} 排在其余15 條不存在邊的前面.

圖1 鏈路預(yù)測(cè)問(wèn)題示意圖Fig.1.Illustration of link prediction problem.

在這個(gè)例子中我們選擇資源分配算法[14]進(jìn)行鏈路預(yù)測(cè),選取該算法認(rèn)為存在可能性最高的3 條連邊添加到網(wǎng)絡(luò)中,如圖1(c)所示,紅色連邊表示正確預(yù)測(cè),藍(lán)色連邊表示錯(cuò)誤預(yù)測(cè),可以看到,算法正確預(yù)測(cè)了連邊 e15和e17,未能正確預(yù)測(cè)出節(jié)點(diǎn)3和節(jié)點(diǎn)4之間的連邊 e34而是錯(cuò)誤的認(rèn)為連邊 e23存在的可能性更高,易計(jì)算得到,此次預(yù)測(cè)精度(precision)為2/3.

3 基于特征譜的復(fù)雜網(wǎng)絡(luò)鏈路可預(yù)測(cè)性

3.1 復(fù)雜網(wǎng)絡(luò)的特征譜

復(fù)雜網(wǎng)絡(luò)的特征譜是代數(shù)圖論的基本研究課題,經(jīng)過(guò)多年的研究,如文獻(xiàn) [33] 所述,已有成熟的理論體系和豐富的研究成果.網(wǎng)絡(luò)的特征譜提供了包含網(wǎng)絡(luò)功能和動(dòng)力學(xué)行為在內(nèi)的大量信息,可以被形容為網(wǎng)絡(luò)的“指紋”,即網(wǎng)絡(luò)與其特征譜是一一對(duì)應(yīng)的,不同類別的網(wǎng)絡(luò)有著完全不同的特征譜.因此,通過(guò)分析和識(shí)別特征譜,我們就能夠鎖定目標(biāo)網(wǎng)絡(luò).進(jìn)一步,特征譜不僅是網(wǎng)絡(luò)的“指紋”,還是網(wǎng)絡(luò)的“脈象”.通過(guò)分析特征譜這一網(wǎng)絡(luò)“脈象”,可以得到大量的網(wǎng)絡(luò)結(jié)構(gòu)信息.例如,通過(guò)拉普拉斯矩陣(Laplace matrix)的最大特征根我們可以估計(jì)網(wǎng)絡(luò)的度序列;分析特征譜還可以挖掘網(wǎng)絡(luò)社區(qū)結(jié)構(gòu);網(wǎng)絡(luò)的中心性和二部分性也可從特征譜得出[34?37].最近有研究表明,網(wǎng)絡(luò)的特征值譜還可以表現(xiàn)網(wǎng)絡(luò)結(jié)構(gòu)和動(dòng)力學(xué)(例如神經(jīng)與激發(fā)序列)的層次性[38].

令 G 表示無(wú)向無(wú)權(quán)圖,A(G)=(aij)N×N表示 G 的鄰接矩陣,其中若節(jié)點(diǎn)對(duì) vi與vj之間有連邊,則 aij=1,否則 aij=0 .令λ1≥ λ2≥ ···≥ λN為 A(G)的特征根,則稱集合{ λi} 為 G 的特征譜(spectrum).定義 di為節(jié)點(diǎn) vi的度.G 的拉普拉斯矩陣(Laplace matrix)可用數(shù)學(xué)公式表示為L(zhǎng)(G)=D(G)-A(G),式 中,D(G)=diag{di}表示節(jié)點(diǎn)度的對(duì)角矩陣,顯然,L(G)是對(duì)稱半正定矩陣.令 μ1≥ μ2≥ ···≥ μN(yùn)表示 L(G)的特征根,則稱集合 { μi} 為圖 G 的拉普拉斯特征譜.

3.2 基于特征譜視角的網(wǎng)絡(luò)鏈路可預(yù)測(cè)性

近年來(lái),很多統(tǒng)計(jì)物理領(lǐng)域的學(xué)者基于特征譜研究了圖的溝通性(communicability)[34]和可擴(kuò)張性(good expansion,GE)[39].圖的溝通性指網(wǎng)絡(luò)中不同節(jié)點(diǎn)之間進(jìn)行交流或傳遞信息的能力,而可擴(kuò)張性指那些既稀疏同時(shí)又高度連通的節(jié)點(diǎn)間的溝通能力.實(shí)際上,統(tǒng)計(jì)物理角度的溝通和擴(kuò)張,在網(wǎng)絡(luò)信息的視角中,可以理解為網(wǎng)絡(luò)結(jié)構(gòu)某種程度上的演化和發(fā)展.鏈路預(yù)測(cè),作為網(wǎng)絡(luò)信息挖掘的技術(shù)手段,一個(gè)很重要的功能便是預(yù)測(cè)缺失連邊和未來(lái)可能存在的連邊.可以說(shuō),鏈路預(yù)測(cè)算法與網(wǎng)絡(luò)連邊形成機(jī)制相輔相成,好的鏈路預(yù)測(cè)算法本身就給出了很多網(wǎng)絡(luò)演化可能機(jī)制的暗示;反之網(wǎng)絡(luò)的鏈路可預(yù)測(cè)性也可以理解為網(wǎng)絡(luò)連邊演化機(jī)制的另一種表現(xiàn)形式.因此,我們可以認(rèn)為,溝通性和可擴(kuò)張性這兩個(gè)指標(biāo)所刻畫的拓?fù)湫畔哪撤N程度上來(lái)說(shuō)和網(wǎng)絡(luò)的鏈路可預(yù)測(cè)性是相似的,即具備較好的鏈路可預(yù)測(cè)性的網(wǎng)絡(luò),一般也具有較好的溝通性和可擴(kuò)張性.

已有研究表明,可擴(kuò)張性好的網(wǎng)絡(luò)同時(shí)也表現(xiàn)出良好的溝通性,且這些網(wǎng)絡(luò)特征譜的最大特征根λ1遠(yuǎn)大于次大特征根 λ2,即 λ1? λ2.我們?cè)谥暗墓ぷ髦衃40]研究了無(wú)標(biāo)度網(wǎng)絡(luò)特征譜,同樣發(fā)現(xiàn)不同參數(shù)的無(wú)標(biāo)度網(wǎng)絡(luò)中存在著不同程度的λ1? λ2,即存在譜隙(spectrum gap)現(xiàn)象,如圖2所示.因此,如果能夠定量地刻畫特征譜中λ1和其他特征根之間的差距,就能夠像中醫(yī)把脈一樣,定量刻畫網(wǎng)絡(luò)的鏈路可預(yù)測(cè)性.

圖2 無(wú)標(biāo)度網(wǎng)絡(luò)特征譜直方圖Fig.2.The histograms of eigenvalues of random sacle-free networks.

3.3 可預(yù)測(cè)性的數(shù)學(xué)表達(dá)式

在各種各樣衡量網(wǎng)絡(luò)結(jié)構(gòu)屬性的指標(biāo)中,文獻(xiàn)[41]提出的子圖中心性是基于網(wǎng)絡(luò)特征譜的指標(biāo).其認(rèn)為閉環(huán)回路的路徑長(zhǎng)度越小,回路信息交流越便利,節(jié)點(diǎn)之間的聯(lián)系越緊密,對(duì)節(jié)點(diǎn)的中心性貢獻(xiàn)越大.節(jié)點(diǎn) i 的子圖中心性可以定義為

此后從11月23日，我國(guó)再發(fā)布了多起非洲豬瘟疫情，其中涉及北京市房山區(qū)青龍湖鎮(zhèn)、琉璃河鎮(zhèn)各一個(gè)養(yǎng)殖場(chǎng)，內(nèi)蒙古自治區(qū)包頭市昆都侖區(qū)一養(yǎng)殖戶；湖北省黃石市陽(yáng)新縣一養(yǎng)殖戶，天津市寧河區(qū)一養(yǎng)殖場(chǎng)，江西省九江市柴桑區(qū)一養(yǎng)殖場(chǎng)，陜西省西安市鄠邑區(qū)一養(yǎng)殖場(chǎng)，北京市通州區(qū)一規(guī)模養(yǎng)殖場(chǎng)，黑龍江省農(nóng)墾總局北安管理局一野豬養(yǎng)殖場(chǎng)，四川省瀘州市合江縣一養(yǎng)殖戶，陜西省西安市長(zhǎng)安區(qū)一養(yǎng)殖戶，北京市順義區(qū)一種豬場(chǎng)，山西省臨汾市堯都區(qū)一養(yǎng)殖戶。其中，受到規(guī)?；B(yǎng)殖的影響，北京市通州、順義、房山三個(gè)出現(xiàn)非洲豬瘟疫情的養(yǎng)殖場(chǎng)生豬存欄量最大，分別達(dá)到9835頭、2461頭和1325頭。

其中 λj(j=1,2,···,n)是 鄰接矩陣A 第 j 個(gè)特征向量的特征值,ξj是 λj所對(duì)應(yīng)的特征向量,是鄰接矩陣第 j 個(gè)特征向量的第 i 個(gè)組分,例如,λ1和ξ1分別是鄰接矩陣A的最大特征值及其對(duì)應(yīng)的特征向量.對(duì)于(2)式而言,顯然,SC(i)包含了從節(jié)點(diǎn) i 出發(fā),偶數(shù)長(zhǎng)度和奇數(shù)長(zhǎng)度的所有的閉途徑.因此,(2)式也可以表示為

顯然,偶數(shù)長(zhǎng)度的閉途徑更多的是一些無(wú)環(huán)的軌跡,更多地出現(xiàn)在二部分圖中;而奇數(shù)長(zhǎng)度的閉途徑則不包含這部分無(wú)效的路徑.本文的研究對(duì)象是簡(jiǎn)單無(wú)權(quán)圖,因此,奇數(shù)長(zhǎng)度的閉途徑更適合于用來(lái)描述網(wǎng)絡(luò)中節(jié)點(diǎn)與其鄰居間的拓?fù)浣Y(jié)構(gòu)關(guān)系.我們可以將SCodd(i)寫成如下形式[39]:

其中 λ1是 網(wǎng)絡(luò)的主特征值,是主特征向量的第i個(gè)組分.當(dāng)網(wǎng)絡(luò)存在一個(gè)巨大的譜隙(spectral gap)時(shí),有 λ1? λ2≥ λ3≥ ···≥ λN.因此,在這種情況下,

則

也就是說(shuō),要判斷網(wǎng)絡(luò)特征譜中 λ1和λ2之間是否有足夠大的譜隙.需要檢測(cè)

令 A=[sinh(λ1)]-0.5,η =0.5,(7)式可以表示為顯然,和S Codd(i)之間存在著線性關(guān)系.因此,我們可以在雙對(duì)數(shù)形式下將(7)式改寫成:

易知,可預(yù)測(cè)性 p 的值域?yàn)?[ 0 ,1],如果偏差趨近于0,那么 p 趨近于 1,表示網(wǎng)絡(luò)的鏈路可預(yù)測(cè)性很好;反之,若網(wǎng)絡(luò) p 值較小,表示網(wǎng)絡(luò)的可預(yù)測(cè)性差.

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

4.1 模型網(wǎng)絡(luò)的可預(yù)測(cè)性分析

相比于隨機(jī)網(wǎng)絡(luò),BA無(wú)標(biāo)度網(wǎng)絡(luò)具有節(jié)點(diǎn)生長(zhǎng)和邊的偏好鏈接(preferential attachment)兩種明確的生成機(jī)制,即新加入的節(jié)點(diǎn)更傾向于與那些具有較大連接度的節(jié)點(diǎn)相連.一個(gè)新節(jié)點(diǎn)與一個(gè)已經(jīng)存在的節(jié)點(diǎn) vi相連接的概率 Πi與 節(jié)點(diǎn)的度di成正比:

這意味著,如果我們的指標(biāo)能夠有效刻畫網(wǎng)絡(luò)的可預(yù)測(cè)性,則 p 值會(huì)隨著網(wǎng)絡(luò)演化機(jī)制的變化而改變.為全面比較網(wǎng)絡(luò)演化機(jī)制對(duì) p 刻畫可預(yù)測(cè)性能力的影響,我們基于(11)式,加入?yún)?shù) α,調(diào)控 BA 模型中偏好鏈接機(jī)制的強(qiáng)度.構(gòu)造連接概率

當(dāng) α=0 時(shí),網(wǎng)絡(luò)生成僅由生長(zhǎng)機(jī)制決定(在此情況下老的節(jié)點(diǎn)仍有更高的概率獲得更多連接);當(dāng)α=1 時(shí),網(wǎng)絡(luò)生成過(guò)程具有顯著的偏好鏈接特征.圖3展示了當(dāng)網(wǎng)絡(luò)平均度為4時(shí),不同節(jié)點(diǎn)規(guī)模下可預(yù)測(cè)性 p值隨參數(shù) α 的 變化,結(jié)果表明,隨著 α 的增加,優(yōu)先鏈接特性逐漸增強(qiáng),我們的指標(biāo)能夠捕捉到網(wǎng)絡(luò)逐漸明顯的優(yōu)先鏈接特性,網(wǎng)絡(luò)的可預(yù)測(cè)性越來(lái)越好.并且在連邊機(jī)制固定的情況下,可預(yù)測(cè)性隨網(wǎng)絡(luò)規(guī)模的變化不大,證明 p 指標(biāo)具有良好的穩(wěn)定性.

圖3 不同節(jié)點(diǎn)規(guī)模下,模型網(wǎng)絡(luò)可預(yù)測(cè)性 p 隨 α 的變化Fig.3.The link predictability of model network versus α with various N .

同時(shí),為了清晰地對(duì)比各種鏈路預(yù)測(cè)算法在這兩類模型網(wǎng)絡(luò)中的表現(xiàn),我們生成一個(gè)節(jié)點(diǎn)數(shù)為1000,平均度為6的BA無(wú)標(biāo)度網(wǎng)絡(luò)和與之同樣規(guī)模的隨機(jī)網(wǎng)絡(luò)進(jìn)行對(duì)比實(shí)驗(yàn),實(shí)驗(yàn)結(jié)果如圖4和表1所示.表1給出了12種基于相似性的鏈路預(yù)測(cè)算法在這兩個(gè)模型網(wǎng)絡(luò)中的精確度(precision).包括 6種基于節(jié)點(diǎn)局部信息的相似性指標(biāo): 共同鄰居(CN),Adamic-Adar(AA),資源分配(RA),偏好 連 接(PA),Individual Attraction(IA)和CAR 指標(biāo);3 種基于路徑的相似性指標(biāo): 局部路徑(LP),Katz和LHN-II指標(biāo);3 種基于隨機(jī)游走的相似性指標(biāo): 平均通勤時(shí)間(ACT),重啟的隨機(jī)游走(RWR),局部隨機(jī)游走指標(biāo)(LRW),具體的算法原理參見(jiàn)文獻(xiàn)[25].實(shí)驗(yàn)通過(guò)隨機(jī)抽樣的方式,將訓(xùn)練集和測(cè)試集按照 9∶1 的比例進(jìn)行劃分,我們固定預(yù)測(cè)連邊的比例,令L等于測(cè)試集中的連邊數(shù)量.

可以看到,由于BA無(wú)標(biāo)度網(wǎng)絡(luò)中,新的節(jié)點(diǎn)進(jìn)入網(wǎng)絡(luò)后會(huì)選擇網(wǎng)絡(luò)中已存在的大度節(jié)點(diǎn)產(chǎn)生鏈接.網(wǎng)絡(luò)具有固定的網(wǎng)絡(luò)連邊演化機(jī)制,連邊都是按照優(yōu)先鏈接產(chǎn)生,因此,網(wǎng)絡(luò)具有很好的可預(yù)測(cè)性.在圖 4(c)中表現(xiàn)為和S Codd(i)在一條直線上,體現(xiàn)出(7)式表示的線性關(guān)系;反觀同樣規(guī)模的隨機(jī)網(wǎng)絡(luò),網(wǎng)絡(luò)中的連邊以固定概率隨機(jī)產(chǎn)生,不根據(jù)任何演化機(jī)制和節(jié)點(diǎn)屬性,很難基于某一演化機(jī)制去預(yù)測(cè)連邊是否存在,網(wǎng)絡(luò)可預(yù)測(cè)性較差.在圖4(a)中表現(xiàn)為和S Codd(i)并不具有很強(qiáng)的線性關(guān)系.圖4(b)的雷達(dá)圖直觀地展示了鏈路預(yù)測(cè)算法在兩類模型網(wǎng)絡(luò)中的表現(xiàn),結(jié)果表明,各類算法在BA無(wú)標(biāo)度網(wǎng)絡(luò)中的精確度顯著優(yōu)于隨機(jī)網(wǎng)絡(luò),這與我們對(duì)這兩類網(wǎng)絡(luò)可預(yù)測(cè)性的判斷是一致的.觀察各個(gè)算法的表現(xiàn),在BA無(wú)標(biāo)度網(wǎng)絡(luò)中,PA指標(biāo)表現(xiàn)最為出色,這是因?yàn)镻A算法的思想來(lái)源于優(yōu)先鏈接的方法,即連邊存在的可能性大小正比于兩端度值的積.因此,PA算法對(duì)于相似性的定義更貼近于BA無(wú)標(biāo)度網(wǎng)絡(luò)的連邊演化機(jī)制,故在這類網(wǎng)絡(luò)中有著優(yōu)異的表現(xiàn).縱使BA無(wú)標(biāo)度網(wǎng)絡(luò)具有優(yōu)秀的可預(yù)測(cè)性,LHN-II算法在網(wǎng)絡(luò)中的表現(xiàn)卻很差.這是因?yàn)長(zhǎng)HN-II算法是基于一般等價(jià)(regular equivalence)的思想,其相似性的定義更多地取決于節(jié)點(diǎn)連接的節(jié)點(diǎn)之間的相似性,即使節(jié)點(diǎn)對(duì)之間不存在共同鄰居.然而,節(jié)點(diǎn)的屬性如果不是特殊背景的網(wǎng)絡(luò)或者有特定的標(biāo)準(zhǔn)往往是很難去量化的,因此,雖然無(wú)標(biāo)度網(wǎng)絡(luò)有著高的可預(yù)測(cè)性,但LHN-II算法卻不是適用于該網(wǎng)絡(luò)的合適的鏈路預(yù)測(cè)算法.上述結(jié)果初步表明,通過(guò)計(jì)算鏈路可預(yù)測(cè)性 p 的值,能夠回答到底是不可預(yù)測(cè)的網(wǎng)絡(luò)還是不合適的算法這個(gè)問(wèn)題,從而為決策者篩選算法提供指導(dǎo)意見(jiàn).上述模型網(wǎng)絡(luò)只是真實(shí)網(wǎng)絡(luò)一種演化機(jī)制的抽象,真實(shí)網(wǎng)絡(luò)在生長(zhǎng)演化過(guò)程中往往表現(xiàn)出如集聚性、社團(tuán)性、無(wú)標(biāo)度性等多種復(fù)雜的結(jié)構(gòu)特征,為更進(jìn)一步證明指標(biāo)的有效性,我們?cè)诟嗾鎸?shí)網(wǎng)絡(luò)中進(jìn)行了實(shí)驗(yàn).

圖4 無(wú)標(biāo)度網(wǎng)絡(luò)和隨機(jī)網(wǎng)絡(luò)可預(yù)測(cè)性示意圖Fig.4.The link predictability of BA scale-free network and random graph.

表1 鏈路預(yù)測(cè)算法在模型網(wǎng)絡(luò)中的表現(xiàn)Table 1.Performance of link prediction algorithms in model networks.

4.2 真實(shí)網(wǎng)絡(luò)的鏈路可預(yù)測(cè)性分析

本節(jié)進(jìn)一步考察可預(yù)測(cè)性指標(biāo)在真實(shí)世界網(wǎng)絡(luò)中的表現(xiàn).我們選取了各個(gè)不同領(lǐng)域的15個(gè)真實(shí)網(wǎng)絡(luò)作為實(shí)驗(yàn)網(wǎng)絡(luò).網(wǎng)絡(luò)拓?fù)鋵傩匀绫?所列,V和E 表示網(wǎng)絡(luò)中的節(jié)點(diǎn)和邊,〈 k〉 表示平均度,C 表示集聚系數(shù),r 表示同配系數(shù),〈l〉 表示平均最短路徑長(zhǎng)度.

在實(shí)驗(yàn)中,我們采用隨機(jī)抽樣的方法,將訓(xùn)練集和測(cè)試集按照9∶1的比例進(jìn)行劃分,即測(cè)試集包含10%的真實(shí)連邊.針對(duì)預(yù)測(cè)結(jié)果采取precision衡量算法的表現(xiàn),由于真實(shí)網(wǎng)絡(luò)規(guī)模不同,在實(shí)驗(yàn)時(shí)固定預(yù)測(cè)連邊的比例,令L等于測(cè)試集中的連邊數(shù)量.

表3為鏈路預(yù)測(cè)算法在真實(shí)網(wǎng)絡(luò)中的最大精確度(precision)測(cè)試結(jié)果,每個(gè)鏈路預(yù)測(cè)算法在每個(gè)網(wǎng)絡(luò)運(yùn)行100次取平均.從網(wǎng)絡(luò)間縱向比較來(lái)看,算法在可預(yù)測(cè)性高的網(wǎng)絡(luò)上的預(yù)測(cè)精度要明顯高于可預(yù)測(cè)低的網(wǎng)絡(luò),如圖5大圖所示,不同顏色的圓代表不同的網(wǎng)絡(luò),圓的大小與網(wǎng)絡(luò)可預(yù)測(cè)性 p成正比.橫坐標(biāo)表示網(wǎng)絡(luò)可預(yù)測(cè)性的值,縱坐標(biāo)表示鏈路預(yù)測(cè)算法的最大precision值,縱坐標(biāo)越大,算法的最大精度越高.可以看到,那些可預(yù)測(cè)性好的網(wǎng)絡(luò)對(duì)應(yīng)的precision值也相對(duì)較高,如圖中右側(cè)較大的圓所示.相比之下,圖中左下方網(wǎng)絡(luò)的precision值較低,其對(duì)應(yīng)的網(wǎng)絡(luò)可預(yù)測(cè)性值也較差.值得注意的是,C_elegans網(wǎng)絡(luò)的可預(yù)測(cè)值很高,然而實(shí)驗(yàn)選取的多種基于結(jié)構(gòu)相似性的鏈路算法在網(wǎng)絡(luò)中的precision值普遍不高,我們進(jìn)一步計(jì)算了各類算法在該網(wǎng)絡(luò)中的AUC值,結(jié)果表明,最大 AUC值同樣來(lái)自于 LRW指標(biāo),達(dá)到了0.907,各類算法的平均AUC值為0.848.因?yàn)锳UC值是基于整個(gè)邊列表,而這里的L是基于前10%的邊,說(shuō)明這些算法對(duì)于該網(wǎng)絡(luò)的正確預(yù)測(cè)大部分來(lái)自于邊列表的后半段,測(cè)試的算法在該網(wǎng)絡(luò)上的預(yù)測(cè)效率均較低,對(duì)于該網(wǎng)絡(luò)有待挖掘能夠快速找到更多正確連邊的預(yù)測(cè)算法.圖5里的箱線圖則顯示了對(duì)每個(gè)網(wǎng)絡(luò)預(yù)測(cè)算法之間的比較結(jié)果.我們發(fā)現(xiàn),除了少數(shù)網(wǎng)絡(luò)各個(gè)預(yù)測(cè)算法的表現(xiàn)基本維持在同一水準(zhǔn)外,大多數(shù)預(yù)測(cè)算法在網(wǎng)絡(luò)中的效果差別很大,這也體現(xiàn)出網(wǎng)絡(luò)和算法選擇與匹配問(wèn)題的重要性.例如,在 Jazz 網(wǎng)絡(luò)中,CN,AA,RA 等指標(biāo)的precision都達(dá)到了0.5左右,然而,優(yōu)先鏈接指標(biāo)PA的精確度卻很差,僅為0.133.該結(jié)果說(shuō)明,對(duì)于Jazz網(wǎng)絡(luò)來(lái)說(shuō),基于共同鄰居的算法更能捕獲爵士音樂(lè)家間的合作關(guān)系,且這種關(guān)系不是以優(yōu)先鏈接的形式展開(kāi)的,所以由優(yōu)先鏈接思想演化而來(lái),依靠節(jié)點(diǎn)度乘積來(lái)刻畫相似性的PA指標(biāo)與Jazz 網(wǎng)絡(luò)并不匹配.事實(shí)上,不僅是 Jazz網(wǎng)絡(luò),PA算法在很多真實(shí)網(wǎng)絡(luò)中的precision值都低于其他算法,這說(shuō)明真實(shí)網(wǎng)絡(luò)在演化生長(zhǎng)的過(guò)程中往往表現(xiàn)出集聚性、社團(tuán)性、無(wú)標(biāo)度性、小世界性等多種結(jié)構(gòu)特征,PA算法雖然能夠在無(wú)標(biāo)度網(wǎng)絡(luò)中表現(xiàn)突出,其相對(duì)單一的相似性刻畫思想難以勝任網(wǎng)絡(luò)結(jié)構(gòu)特征比較復(fù)雜的真實(shí)網(wǎng)絡(luò).類似的情況還出現(xiàn)在Router網(wǎng)絡(luò)中,該網(wǎng)絡(luò)中大多數(shù)算法的 precision值都低于 0.05,只有 ACT算法的precision達(dá)到了0.164,這說(shuō)明ACT的算法思想能夠更好地匹配該網(wǎng)絡(luò)更多的結(jié)構(gòu)特征.結(jié)合表3和箱線圖進(jìn)行討論分析,能夠?yàn)榫W(wǎng)絡(luò)與算法間的匹配和選擇問(wèn)題提供幫助.

表2 不同領(lǐng)域真實(shí)網(wǎng)絡(luò)拓?fù)鋵傩訲able 2.Basic statistics of real networks.

表3 鏈路預(yù)測(cè)算法在真實(shí)網(wǎng)絡(luò)中的 precision 值Table 3.The precision of link prediction algorithms in real networks.

圖5 預(yù)測(cè)算法在真實(shí)網(wǎng)絡(luò)上的表現(xiàn)Fig.5.The performance of prediction algorithms in real networks.

5 結(jié)論與展望

在網(wǎng)絡(luò)科學(xué)和信息科學(xué)領(lǐng)域中,我們常常會(huì)遇到信息缺失的情況.鏈路預(yù)測(cè)作為數(shù)據(jù)挖掘領(lǐng)域重要的研究方向之一,是一個(gè)長(zhǎng)期存在的挑戰(zhàn)和難題.近年來(lái)有關(guān)鏈路預(yù)測(cè)理論和實(shí)證的研究發(fā)展迅速,大量研究工作的重心都放在提出算法本身上,各種各樣精確度越來(lái)越高的算法層出不窮.但是,大量實(shí)驗(yàn)結(jié)果表明,在同一網(wǎng)絡(luò)中不同算法的精度有好有壞.因此,到底是不可預(yù)測(cè)的網(wǎng)絡(luò),還是不合適的鏈路預(yù)測(cè)方法,是一個(gè)很有挑戰(zhàn)性問(wèn)題.

本文從統(tǒng)計(jì)物理中圖的可擴(kuò)張性得到啟發(fā),提出了一種基于特征譜的鏈路可預(yù)測(cè)性度量指標(biāo).通過(guò)對(duì)網(wǎng)絡(luò)特征譜的分析,構(gòu)造了一個(gè)指標(biāo)來(lái)評(píng)價(jià)網(wǎng)絡(luò)缺失鏈路的“可被預(yù)測(cè)的程度”.模型網(wǎng)絡(luò)和大量真實(shí)網(wǎng)絡(luò)中的實(shí)驗(yàn)結(jié)果證明,該指標(biāo)能夠有效地刻畫網(wǎng)絡(luò)的鏈路可預(yù)測(cè)性,且能夠就鏈路預(yù)測(cè)算法選擇提供建議.例如,隨機(jī)網(wǎng)絡(luò)的可預(yù)測(cè)性較差,而無(wú)標(biāo)度網(wǎng)絡(luò)的可預(yù)測(cè)性較好.然而,雖然各類算法在無(wú)標(biāo)度網(wǎng)絡(luò)中的精確度明顯優(yōu)于隨機(jī)網(wǎng)絡(luò),LHN-II算法卻不是適用于該網(wǎng)絡(luò)的合適的鏈路預(yù)測(cè)算法;在實(shí)證網(wǎng)絡(luò)中,Jazz網(wǎng)絡(luò)具有較好的可預(yù)測(cè)性,一些基于共同鄰居的相似性指標(biāo)如CN,AA,RA表現(xiàn)較好,然而優(yōu)先鏈接指標(biāo)PA的精確度卻很差.這是因?yàn)榫W(wǎng)絡(luò)中音樂(lè)家之間的合作關(guān)系不是以優(yōu)先鏈接的形式展開(kāi)的,依靠節(jié)點(diǎn)度乘積來(lái)刻畫相似性的PA算法不是適合Jazz網(wǎng)絡(luò)的鏈路預(yù)測(cè)算法.事實(shí)上,我們認(rèn)為網(wǎng)絡(luò)的可被預(yù)測(cè)的程度差并不絕對(duì),可預(yù)測(cè)性差的網(wǎng)絡(luò)也許只是沒(méi)能遇到理解它結(jié)構(gòu)特征的鏈路預(yù)測(cè)算法.一個(gè)好的鏈路預(yù)測(cè)算法背后往往有一套貼近網(wǎng)絡(luò)生長(zhǎng)演化的連邊機(jī)制,同樣道理,一個(gè)重要的機(jī)制往往能夠提取出一種精確的鏈路預(yù)測(cè)算法.鏈路預(yù)測(cè)的研究與網(wǎng)絡(luò)的結(jié)構(gòu)和演化密切相關(guān),即算法與網(wǎng)絡(luò)連邊形成機(jī)制相輔相成,是互通的,網(wǎng)絡(luò)的鏈路可預(yù)測(cè)性即是網(wǎng)絡(luò)連邊演化機(jī)制的另一種表現(xiàn)形式.我們把基于特征譜視角計(jì)算可預(yù)測(cè)性,獲取網(wǎng)絡(luò)能夠被預(yù)測(cè)的難易程度的工作視作基礎(chǔ),在下一步的研究中,擬通過(guò)對(duì)具有典型演化機(jī)制的網(wǎng)絡(luò)進(jìn)行分析,說(shuō)明預(yù)測(cè)背后的主要機(jī)制以及預(yù)測(cè)正確或者錯(cuò)誤的原因,去探索一些因果關(guān)系.同時(shí),考慮基于特征譜挖掘和學(xué)習(xí)不同網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)信息,對(duì)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)進(jìn)行標(biāo)記分類,針對(duì)不同類型網(wǎng)絡(luò)的連邊機(jī)制,提出與之相匹配的鏈路預(yù)測(cè)算法.