復雜網絡鏈路可預測性:基于特征譜視角*

譚索怡 祁明澤 吳俊 呂欣?

1)(國防科技大學系統工程學院,長沙 410073)

2)(國防科技大學文理學院,長沙 410073)

3)(北京師范大學復雜系統國際科學中心,珠海 519087)

近年來鏈路預測的理論和實證研究發展迅速,大部分工作關注于提出更精確的預測算法.事實上,鏈路預測的前提是網絡的結構本身能夠被預測,這種“可被預測的程度”可以看作是網絡自身的基本屬性.本文擬從特征譜的視角去解釋網絡的鏈路可預測性,并刻畫網絡的拓撲結構信息,通過對網絡特征譜進行分析,構造了復雜網絡鏈路可預測性評價指標.通過該指標計算和分析不同網絡的鏈路可預測性,能夠在選擇算法前獲取目標網絡能夠被預測的難易程度,解決到底是網絡本身難以預測還是預測算法不合適的問題,為復雜網絡與鏈路預測算法的選擇和匹配問題提供幫助.

1 引 言

近年來,復雜網絡研究迅速發展,其學科分支在包括數學、統計物理、生物醫學、化學、計算機等領域掀起研究熱潮[1?5].在現代信息科學領域中,鏈路預測作為將復雜網絡與信息科學連接起來的重要橋梁,關心的是信息科學中最基本的問題—缺失信息的預測和還原問題[6,7].即在一個網絡中,如何基于已知連邊信息,刻畫網絡的相似性,進而重現因為數據缺失尚未觀察到的連邊,或者預測未來網絡演化過程中將要出現的連邊.

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

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

顯然,網絡中待預測的連邊集合與網絡中不存在的連邊集合交集為空集,無論預測的準確性和效率如何,理論上我們總可以通過無限加邊命中所有待預測的鏈接.然而這種上界是沒有價值的,不考慮成本的加邊會帶來巨大的成本消耗和結構噪音,這樣的情況顯然偏離了鏈路預測的初衷.如果能夠獲悉一個網絡的鏈路信息能夠多大程度被預測出來,就能夠提供一個導向,確定當前算法是否接近或者已經達到目標網絡的可預測上限.因此,刻畫網絡多大程度上能夠被預測是鏈路預測中首先需要解決的問題,這個問題在相關文獻中被稱為復雜網絡的鏈路可預測性問題.

近年來鏈路預測的理論和實證研究發展迅速,但絕大部分研究的目的都是希望提出更準確的預測算法[25,26],關于復雜網絡鏈路可預測性的研究起步較晚,相關成果少見報道.許小可等[27]最早從理論上比較了各種算法的優劣,分析多個網絡演化過程中形成鏈接的兩個節點之間的拓撲距離分布,闡明了傳統基于共同鄰居相似性指標可有效進行鏈路預測的機理,從理論上分析了9 種基于共同鄰居相似性算法的預測上限.Lü等[28]提出結構一致性的概念,認為網絡“可被預測的程度”,是網絡的一種重要固有屬性.通過對已知網絡進行擾動,刻畫重構的鄰接矩陣和真實鄰接矩陣的差異.如果丟失的連邊沒有顯著改變網絡的結構,那么這個網絡是可預測的,即網絡的結構一致性越強,網絡可預測性越好.熵被廣泛用來測量物理系統中的無序度,Yin等[29]設計了基于證據推理(Dempster-Shafer theory)的鏈路預測算法,從香農信息熵的視角出發,分析了網絡鏈路信息的可預測性.

本文擬從特征譜的視角去理解網絡拓撲信息,并刻畫網絡的鏈路可預測性.首先基于特征譜理論給出復雜網絡鏈路可預測性的數學描述,提出可預測性指標.在此基礎上,通過計算和分析不同實證網絡的鏈路可預測性,驗證該指標的有效性.

2 鏈路預測問題描述

在本文的研究中,主要討論無向無權網絡.令G(V,E)表示無向無權網絡,V 表示節點,E 表示連邊.令 U=N(N-1)/2 表示連邊的全集.對于網絡中未連邊的節點對(vi,vj),可以通過某種預測算法得到其得分矩陣,將所有未連邊列表中節點對的得分降序排列,排在前面的節點對之間產生鏈接的可能性大.

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

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

圖1 鏈路預測問題示意圖Fig.1.Illustration of link prediction problem.

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

3 基于特征譜的復雜網絡鏈路可預測性

3.1 復雜網絡的特征譜

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

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

3.2 基于特征譜視角的網絡鏈路可預測性

近年來,很多統計物理領域的學者基于特征譜研究了圖的溝通性(communicability)[34]和可擴張性(good expansion,GE)[39].圖的溝通性指網絡中不同節點之間進行交流或傳遞信息的能力,而可擴張性指那些既稀疏同時又高度連通的節點間的溝通能力.實際上,統計物理角度的溝通和擴張,在網絡信息的視角中,可以理解為網絡結構某種程度上的演化和發展.鏈路預測,作為網絡信息挖掘的技術手段,一個很重要的功能便是預測缺失連邊和未來可能存在的連邊.可以說,鏈路預測算法與網絡連邊形成機制相輔相成,好的鏈路預測算法本身就給出了很多網絡演化可能機制的暗示;反之網絡的鏈路可預測性也可以理解為網絡連邊演化機制的另一種表現形式.因此,我們可以認為,溝通性和可擴張性這兩個指標所刻畫的拓撲信息從某種程度上來說和網絡的鏈路可預測性是相似的,即具備較好的鏈路可預測性的網絡,一般也具有較好的溝通性和可擴張性.

已有研究表明,可擴張性好的網絡同時也表現出良好的溝通性,且這些網絡特征譜的最大特征根λ1遠大于次大特征根 λ2,即 λ1? λ2.我們在之前的工作中[40]研究了無標度網絡特征譜,同樣發現不同參數的無標度網絡中存在著不同程度的λ1? λ2,即存在譜隙(spectrum gap)現象,如圖2所示.因此,如果能夠定量地刻畫特征譜中λ1和其他特征根之間的差距,就能夠像中醫把脈一樣,定量刻畫網絡的鏈路可預測性.

圖2 無標度網絡特征譜直方圖Fig.2.The histograms of eigenvalues of random sacle-free networks.

3.3 可預測性的數學表達式

在各種各樣衡量網絡結構屬性的指標中,文獻[41]提出的子圖中心性是基于網絡特征譜的指標.其認為閉環回路的路徑長度越小,回路信息交流越便利,節點之間的聯系越緊密,對節點的中心性貢獻越大.節點 i 的子圖中心性可以定義為

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

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

顯然,偶數長度的閉途徑更多的是一些無環的軌跡,更多地出現在二部分圖中;而奇數長度的閉途徑則不包含這部分無效的路徑.本文的研究對象是簡單無權圖,因此,奇數長度的閉途徑更適合于用來描述網絡中節點與其鄰居間的拓撲結構關系.我們可以將SCodd(i)寫成如下形式[39]:

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

則

也就是說,要判斷網絡特征譜中 λ1和λ2之間是否有足夠大的譜隙.需要檢測

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

易知,可預測性 p 的值域為 [ 0 ,1],如果偏差趨近于0,那么 p 趨近于 1,表示網絡的鏈路可預測性很好;反之,若網絡 p 值較小,表示網絡的可預測性差.

4 實驗結果分析

4.1 模型網絡的可預測性分析

相比于隨機網絡,BA無標度網絡具有節點生長和邊的偏好鏈接(preferential attachment)兩種明確的生成機制,即新加入的節點更傾向于與那些具有較大連接度的節點相連.一個新節點與一個已經存在的節點 vi相連接的概率 Πi與 節點的度di成正比:

這意味著,如果我們的指標能夠有效刻畫網絡的可預測性,則 p 值會隨著網絡演化機制的變化而改變.為全面比較網絡演化機制對 p 刻畫可預測性能力的影響,我們基于(11)式,加入參數 α,調控 BA 模型中偏好鏈接機制的強度.構造連接概率

當 α=0 時,網絡生成僅由生長機制決定(在此情況下老的節點仍有更高的概率獲得更多連接);當α=1 時,網絡生成過程具有顯著的偏好鏈接特征.圖3展示了當網絡平均度為4時,不同節點規模下可預測性 p值隨參數 α 的 變化,結果表明,隨著 α 的增加,優先鏈接特性逐漸增強,我們的指標能夠捕捉到網絡逐漸明顯的優先鏈接特性,網絡的可預測性越來越好.并且在連邊機制固定的情況下,可預測性隨網絡規模的變化不大,證明 p 指標具有良好的穩定性.

圖3 不同節點規模下,模型網絡可預測性 p 隨 α 的變化Fig.3.The link predictability of model network versus α with various N .

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

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

圖4 無標度網絡和隨機網絡可預測性示意圖Fig.4.The link predictability of BA scale-free network and random graph.

表1 鏈路預測算法在模型網絡中的表現Table 1.Performance of link prediction algorithms in model networks.

4.2 真實網絡的鏈路可預測性分析

本節進一步考察可預測性指標在真實世界網絡中的表現.我們選取了各個不同領域的15個真實網絡作為實驗網絡.網絡拓撲屬性如表2所列,V和E 表示網絡中的節點和邊,〈 k〉 表示平均度,C 表示集聚系數,r 表示同配系數,〈l〉 表示平均最短路徑長度.

在實驗中,我們采用隨機抽樣的方法,將訓練集和測試集按照9∶1的比例進行劃分,即測試集包含10%的真實連邊.針對預測結果采取precision衡量算法的表現,由于真實網絡規模不同,在實驗時固定預測連邊的比例,令L等于測試集中的連邊數量.

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

表2 不同領域真實網絡拓撲屬性Table 2.Basic statistics of real networks.

表3 鏈路預測算法在真實網絡中的 precision 值Table 3.The precision of link prediction algorithms in real networks.

圖5 預測算法在真實網絡上的表現Fig.5.The performance of prediction algorithms in real networks.

5 結論與展望

在網絡科學和信息科學領域中,我們常常會遇到信息缺失的情況.鏈路預測作為數據挖掘領域重要的研究方向之一,是一個長期存在的挑戰和難題.近年來有關鏈路預測理論和實證的研究發展迅速,大量研究工作的重心都放在提出算法本身上,各種各樣精確度越來越高的算法層出不窮.但是,大量實驗結果表明,在同一網絡中不同算法的精度有好有壞.因此,到底是不可預測的網絡,還是不合適的鏈路預測方法,是一個很有挑戰性問題.

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