王 強(qiáng) ,江 昊,羿舒文,楊林濤,奈 何,聶 琦

1(武漢大學(xué) 電子信息學(xué)院,湖北 武漢 430072)

2(華中師范大學(xué) 物理科學(xué)與技術(shù)學(xué)院,湖北 武漢 430079)

近年來,以Internet 為代表的信息技術(shù)的發(fā)展,已使我們處于由無處不在的網(wǎng)絡(luò)構(gòu)成的世界中.此外,網(wǎng)絡(luò)結(jié)構(gòu)數(shù)據(jù)分布在各種相關(guān)領(lǐng)域數(shù)據(jù)中,包括分子結(jié)構(gòu)網(wǎng)絡(luò)、生物蛋白質(zhì)交互網(wǎng)絡(luò)、推薦系統(tǒng)、社交網(wǎng)絡(luò)、引文網(wǎng)絡(luò)等等.這些數(shù)據(jù)結(jié)構(gòu)都可以通過網(wǎng)絡(luò)來描述實(shí)體及實(shí)體之間的交互關(guān)系,網(wǎng)絡(luò)結(jié)構(gòu)數(shù)據(jù)是我們生產(chǎn)、生活中常見的一種數(shù)據(jù)形式.其中,復(fù)雜網(wǎng)絡(luò)是一類具有冪率度分布、強(qiáng)聚類、小世界特性的網(wǎng)絡(luò).對復(fù)雜網(wǎng)絡(luò)的分析有利于網(wǎng)絡(luò)數(shù)據(jù)結(jié)構(gòu)的潛在信息挖掘,這將促進(jìn)一系列應(yīng)用,如節(jié)點(diǎn)分類、社區(qū)發(fā)現(xiàn)、鏈路預(yù)測等[1-6].例如,可以通過“推特、微博”用戶關(guān)注所形成的社交網(wǎng)絡(luò)進(jìn)行“朋友推薦”,通過生物蛋白質(zhì)代謝網(wǎng)絡(luò)發(fā)現(xiàn)潛在的蛋白質(zhì)功能.

復(fù)雜網(wǎng)絡(luò)的分析具有極強(qiáng)的現(xiàn)實(shí)意義,但直接對大規(guī)模、稀疏的鄰接矩陣進(jìn)行分析需要較高的時間復(fù)雜度和空間復(fù)雜度,難以進(jìn)行并行計(jì)算[2].另一方面,在機(jī)器學(xué)習(xí)浪潮下,復(fù)雜網(wǎng)絡(luò)學(xué)科與機(jī)器學(xué)習(xí)的結(jié)合成為當(dāng)下熱點(diǎn)研究問題,很多機(jī)器學(xué)習(xí)算法試圖將網(wǎng)絡(luò)結(jié)構(gòu)數(shù)據(jù)引入作為特征輸入.該輸入數(shù)據(jù)一般可以被表示為包含特征信息的向量形式,傳統(tǒng)方法使用網(wǎng)絡(luò)的統(tǒng)計(jì)參數(shù)、核函數(shù)或通過精心設(shè)計(jì)的特征來描述鄰居結(jié)構(gòu)信息,但這些設(shè)計(jì)代價昂貴且不能自適應(yīng)學(xué)習(xí)過程[6].

為了解決這些困難和挑戰(zhàn),大量研究使用表征學(xué)習(xí)來編碼網(wǎng)絡(luò)結(jié)構(gòu)信息.網(wǎng)絡(luò)表征學(xué)習(xí)通過假設(shè)網(wǎng)絡(luò)節(jié)點(diǎn)位于低維空間,在該空間中學(xué)習(xí)網(wǎng)絡(luò)節(jié)點(diǎn)的低維向量表示,低維向量將進(jìn)一步用于處理后續(xù)任務(wù).表征學(xué)習(xí)的目標(biāo)是通過優(yōu)化網(wǎng)絡(luò)節(jié)點(diǎn)的向量表示來實(shí)現(xiàn)保留網(wǎng)絡(luò)結(jié)構(gòu)信息的降維表達(dá),向量空間中節(jié)點(diǎn)的位置和節(jié)點(diǎn)間距離可以表征網(wǎng)絡(luò)的高階拓?fù)湫畔?如圖1 所示,GCN[7]是一種用于網(wǎng)絡(luò)結(jié)構(gòu)數(shù)據(jù)的神經(jīng)網(wǎng)絡(luò)架構(gòu),隨機(jī)初始化的3 層GCN 也可以生成網(wǎng)絡(luò)中節(jié)點(diǎn)的鄰近特征表征.

Fig.1 Example of embeddings obtained from an untrained 3-layer GCN model with random weights applied to the Zachary’s karate club network[7]圖1 使用未訓(xùn)練的3 層GCN 嵌入Zachary’s Karate Club 網(wǎng)絡(luò)示例[7]

大部分的網(wǎng)絡(luò)表征學(xué)習(xí)針對的是圖數(shù)據(jù),通過圖計(jì)算形式實(shí)現(xiàn)降維表達(dá).而復(fù)雜網(wǎng)絡(luò)的表征學(xué)習(xí)針對具有冪率度分布、強(qiáng)聚類、小世界特性的網(wǎng)絡(luò),其研究有利于降低網(wǎng)絡(luò)數(shù)據(jù)維度,使網(wǎng)絡(luò)數(shù)據(jù)可以與機(jī)器學(xué)習(xí)相結(jié)合,更好地分析網(wǎng)絡(luò)節(jié)點(diǎn)間聯(lián)系,為各種后續(xù)實(shí)際應(yīng)用提供解決方案.近年來,在網(wǎng)絡(luò)表征學(xué)習(xí)領(lǐng)域涌現(xiàn)出大量的研究成果,其中一些研究表明,雙曲空間可以很好地描述具有近似樹狀層次結(jié)構(gòu)的復(fù)雜網(wǎng)絡(luò).雙曲空間具有負(fù)常數(shù)曲率,是樹狀圖的連續(xù)近似空間,無限樹在雙曲空間中也有近乎等距的嵌入[8].復(fù)雜網(wǎng)絡(luò)的雙曲幾何模型嵌入理論將復(fù)雜網(wǎng)絡(luò)幾何化,同時又不損失復(fù)雜網(wǎng)絡(luò)中的無標(biāo)度、小世界等特性,是一種可以解釋復(fù)雜網(wǎng)絡(luò)拓?fù)涮卣骱蜕L機(jī)制的新型模型.為了更好地分析與應(yīng)用該類模型,本文圍繞復(fù)雜網(wǎng)絡(luò)的雙曲空間表征學(xué)習(xí)方法展開系統(tǒng)性介紹和總結(jié),以供后續(xù)研究參考.

本文第1 節(jié)對網(wǎng)絡(luò)表征學(xué)習(xí)及其分類進(jìn)行總結(jié),將網(wǎng)絡(luò)表征學(xué)習(xí)分為矩陣分解、隨機(jī)游走、深度自編碼機(jī)和圖神經(jīng)網(wǎng)絡(luò)的方法.第2 節(jié)在介紹雙曲空間的基礎(chǔ)上,對已有的復(fù)雜網(wǎng)絡(luò)雙曲空間生成模型和嵌入方法進(jìn)行總結(jié).第3 節(jié)從復(fù)雜網(wǎng)絡(luò)雙曲空間表征學(xué)習(xí)的應(yīng)用出發(fā),結(jié)合雙曲空間特征,概括了其主要應(yīng)用場景.第4 節(jié)給出不同的雙曲空間表征學(xué)習(xí)方法性能評估結(jié)果.第5 節(jié)總結(jié)全文,指出復(fù)雜網(wǎng)絡(luò)的雙曲空間表征學(xué)習(xí)的特征優(yōu)勢,并對未來研究方向做出展望.

1 網(wǎng)絡(luò)表征學(xué)習(xí)

1.1 網(wǎng)絡(luò)表征學(xué)習(xí)定義

網(wǎng)絡(luò)表征學(xué)習(xí)是一個降維表達(dá)的過程,將高維的網(wǎng)絡(luò)結(jié)構(gòu)數(shù)據(jù)轉(zhuǎn)換為低維的節(jié)點(diǎn)向量表示,向量可作為節(jié)點(diǎn)特征用于后續(xù)網(wǎng)絡(luò)應(yīng)用.表1 給出了本文所用符號的含義,網(wǎng)絡(luò)表征學(xué)習(xí)的目標(biāo)是:對網(wǎng)絡(luò)G中每個節(jié)點(diǎn)vi,學(xué)習(xí)一個實(shí)值向量表示zi∈?d(d<<|V|).部分方法會用到節(jié)點(diǎn)屬性或連邊屬性,如m維節(jié)點(diǎn)屬性可通過X∈?|V|×m的實(shí)值矩陣來表示.通過網(wǎng)絡(luò)表征學(xué)習(xí)形成保留網(wǎng)絡(luò)結(jié)構(gòu)信息的低維實(shí)值向量,可以用于重構(gòu)出原網(wǎng)絡(luò)、有效支撐網(wǎng)絡(luò)推斷和提高后續(xù)應(yīng)用算法執(zhí)行效率.

Table 1 Notations used in this paper表1 本文所用符號

1.2 網(wǎng)絡(luò)表征學(xué)習(xí)分類及特征

網(wǎng)絡(luò)表征學(xué)習(xí)方法眾多,按照不同的分類標(biāo)準(zhǔn),可得到不同的結(jié)果.本文根據(jù)不同方法的技術(shù)特點(diǎn),把網(wǎng)絡(luò)表征學(xué)習(xí)分為基于矩陣分解、隨機(jī)游走、深度自編碼機(jī)、圖神經(jīng)網(wǎng)絡(luò)的方法:矩陣分解的方法將網(wǎng)絡(luò)信息使用矩陣表示,然后通過分解該矩陣獲取節(jié)點(diǎn)向量表示[9-11];隨機(jī)游走方法將網(wǎng)絡(luò)信息通過采樣一系列隨機(jī)游走的路徑表示,然后將深度學(xué)習(xí)方法應(yīng)用到采樣路徑中進(jìn)行圖嵌入,以保持路徑所攜帶的圖屬性[1,12];深度自編碼機(jī)將網(wǎng)絡(luò)信息編碼到表征空間,然后譯碼重構(gòu),使得重構(gòu)誤差最小化;圖神經(jīng)網(wǎng)絡(luò)通過在圖上定義近似卷積等操作,將神經(jīng)網(wǎng)絡(luò)應(yīng)用于圖信息處理.表2 對每種方法的特征及適用性進(jìn)行描述[13-28].

基于矩陣分解、隨機(jī)游走、深度自編碼機(jī)和圖神經(jīng)網(wǎng)絡(luò)的網(wǎng)絡(luò)表征學(xué)習(xí)方法的相關(guān)研究層出不窮,它們一般都是通過某種策略將實(shí)體對象嵌入到低維歐氏向量空間中,該策略的目標(biāo)是捕獲語義信息,如節(jié)點(diǎn)近似度或節(jié)點(diǎn)間最短路徑等信息.但是,歐幾里德對稱模型不能很好地反映復(fù)雜的數(shù)據(jù)模式,比如分類數(shù)據(jù)中潛在的層次結(jié)構(gòu)[29].為了解決這一問題,非歐幾里德流形表示學(xué)習(xí)成為新的發(fā)展趨勢.實(shí)際上,許多復(fù)雜網(wǎng)絡(luò)都呈現(xiàn)出冪率度分布和潛在的樹狀結(jié)構(gòu),該結(jié)構(gòu)的存在通常可以追溯到層次結(jié)構(gòu).為了利用這種結(jié)構(gòu)特性來學(xué)習(xí)更有效的表示,許多研究建議不在歐幾里德空間中計(jì)算嵌入,而是在雙曲空間中計(jì)算嵌入[30-32],即曲率為負(fù)常數(shù)的空間.

Table 2 Comparison of network representation learning methods表2 網(wǎng)絡(luò)表征學(xué)習(xí)方法比較

關(guān)于網(wǎng)絡(luò)表征學(xué)習(xí),已有大量綜述文獻(xiàn)[1-6,9,11,12],但描述的方法大多以網(wǎng)絡(luò)特征提取和表示為目標(biāo),將網(wǎng)絡(luò)嵌入到低維歐氏空間中.本文主要聚焦于雙曲空間中的復(fù)雜網(wǎng)絡(luò)表征學(xué)習(xí),亦屬于網(wǎng)絡(luò)表征學(xué)習(xí)中的一類,但該類方法來源于對復(fù)雜網(wǎng)絡(luò)形成過程和規(guī)律的研究,所表征的節(jié)點(diǎn)向量具有獨(dú)特的物理含義.該類方法認(rèn)為:雙曲空間是復(fù)雜網(wǎng)絡(luò)潛在的幾何度量空間,將雙曲空間幾何性質(zhì)與復(fù)雜網(wǎng)絡(luò)的特征相結(jié)合,形成復(fù)雜網(wǎng)絡(luò)的生成模型,而相應(yīng)的表征學(xué)習(xí)則是對原始坐標(biāo)的逆向推斷.下一節(jié)將介紹雙曲空間基本性質(zhì)、雙曲空間適合表達(dá)近似樹狀結(jié)構(gòu)的復(fù)雜網(wǎng)絡(luò)的原因、從雙曲空間到實(shí)際網(wǎng)絡(luò)的生成過程以及從實(shí)際網(wǎng)絡(luò)到雙曲空間的嵌入方法.

2 復(fù)雜網(wǎng)絡(luò)的雙曲空間表征學(xué)習(xí)

2.1 雙曲空間概述

非歐幾何的誕生,源自于對歐幾里德第五公設(shè)的討論與研究.雙曲幾何是非歐幾何的一種特例,在雙曲幾何中,前4 條公設(shè)保留,第5 公設(shè)修改為“過已知直線外一點(diǎn)至少可以作兩條直線與已知直線平行”.雙曲空間由于具有負(fù)常數(shù)的曲率,無法等度量地嵌入到歐氏空間中,難以直觀表達(dá).有研究學(xué)者為此建立了很多等價模型,這里我們介紹常用的3 種模型:雙曲面模型、克萊因模型和龐加萊球模型.圖2(b)和圖2(c)所示為克萊因模型和龐加萊圓盤模型(二維龐加萊球模型)中的過給定點(diǎn)的平行線.

Fig.2 Examples of hyperbolic geometric models圖2 雙曲幾何模型示例

2.1.1 雙曲空間表達(dá)模型

(1)雙曲面模型

雙曲面模型將n維雙曲空間視為n+1 維閔可夫斯基空間中的偽球面,n+1 維閔可夫斯基空間是內(nèi)積為公式(1)的實(shí)值空間:

n維雙曲面模型中的點(diǎn)可由n+1 維閔可夫斯基空間中的點(diǎn)表示,如公式(2)所示:

如圖2(a)所示,雙曲面模型中的每一條測地線都是Ln和過原點(diǎn)的平面的交線,兩點(diǎn)間的測地距離如公式(3)所示:

(2)克萊因模型

如圖2(a)所示,將Ln中的每個點(diǎn)通過原點(diǎn)發(fā)散出的射線映射到xn+1=1 的超平面上,可得克萊因模型:

即:該過原點(diǎn)的平面與Ln相交形成雙曲面模型中的測地線,與xn+1=1 的超平面相交形成克萊因模型中的測地線.克萊因模型和雙曲面模型互為映射:

克萊因模型中的測地線距離為

(3)龐加萊球模型

如圖2(a)所示,將Ln中的每個點(diǎn)通過(0,0,…,0,-1)發(fā)散出的射線映射到xn+1=0 的超平面上,可得到龐加萊球模型:

同樣,雙曲面模型與龐加萊球模型互為映射:

龐加萊球模型中的測地線距離為

龐加萊圓盤模型為龐加萊球模型在二維下的具體體現(xiàn).龐加萊圓盤模型具有保角性,即模型中雙曲線之間的歐幾里德角與其雙曲值相等;龐加萊圓盤模型中的距離與歐氏空間中的不同,從圓盤中心出發(fā)的雙曲距離rh與歐氏距離re之間具有如下關(guān)系:

然而,在擴(kuò)展的龐加萊圓盤中,徑坐標(biāo)r使用雙曲距離表示,即:

在曲率為K=-ζ2<0,ζ>0 的擴(kuò)展龐加萊圓盤中,(ri,θi)和(rj,θj)之間的測地線距離dij通過雙曲余弦定理表示為

其中,Δθij=π-|π-|θi-θj||.若ζri和ζrj足夠大,滿足,則測地線距離可通過下式近似計(jì)算:

復(fù)雜網(wǎng)絡(luò)的雙曲幾何模型多采用擴(kuò)展的龐加萊圓盤模型表征雙曲空間,該模型直觀,可視化效果好,二維表達(dá)下更容易分析幾何空間中潛在的物理含義.若非特別說明,本文所提及的龐加萊圓盤或雙曲圓盤均指擴(kuò)展的龐加萊圓盤模型.

2.1.2 雙曲空間基本屬性

雙曲空間具有負(fù)常數(shù)的曲率,其指數(shù)擴(kuò)張速度遠(yuǎn)大于歐氏空間的多項(xiàng)式擴(kuò)張.

如表3 所示,在曲率為K=-ζ2<0,ζ>0 的龐加萊圓盤中,圓周長L和面積S均隨半徑r以eζr增長.

Table 3 Characteristic properties of Euclidean,spherical,and hyperbolic geometries表3 歐氏空間、球面空間和雙曲空間的固有屬性

除了上述固有屬性外,雙曲空間中還有一系列幾何定理,這些屬性和定理可供復(fù)雜網(wǎng)絡(luò)的雙曲空間模型使用.下面給出幾個常見定理.

定理1.在非歐幾何中,三角形ΔABC的面積S與量π-(∠A+∠B+∠C)成正比:S=M[π-(∠A+∠B+∠C)].特別地,任意三角形的面積是有界的:S

定理2.在雙曲空間的三角形ΔABC中,a,b,c分別為∠A,∠B,∠C所對的邊長,則有:

? 雙曲余弦定理:cosh(c)=cosh(a)?cosh(b)-sinh(a)?sinh(b)?cos(∠C).

定理3.設(shè)a為DR={z||z|

定理4.如圖3 所示:設(shè)l是一條給定的非歐直線,記d(z,l)是點(diǎn)z到l的非歐距離,d>0 是任意給定的正數(shù).集合D={z∈U:d(z,l)

Fig.3 Hypercycle of hyperbolic space圖3 雙曲空間的超圓周

2.1.3 雙曲空間與復(fù)雜網(wǎng)絡(luò)的聯(lián)系

雙曲空間適合嵌入具有冪率度分布的復(fù)雜網(wǎng)絡(luò),與雙曲空間的特性關(guān)系密切.冪率度分布的復(fù)雜網(wǎng)絡(luò)具有近似樹狀的層次結(jié)構(gòu),而雙曲空間是樹網(wǎng)絡(luò)的連續(xù)版本,對于n進(jìn)制的樹,圓盤周長和面積可分別類比于距離根節(jié)點(diǎn)r跳的節(jié)點(diǎn)數(shù)(n+1)nr-1和不超過r跳的所有節(jié)點(diǎn)總數(shù)[(n+1)nr-2]/(n-1).如果令圓盤所表示的雙曲空間曲率滿足,則雙曲空間圓周和圓面積以eζr增長,與n進(jìn)制樹增長速率nr保持一致.故樹狀結(jié)構(gòu)可視為離散的雙曲空間.例如,雙曲空間的任何鑲嵌細(xì)分(如圖4 所示)自然定義了由多邊形邊的某些子集形成的一類樹的等距嵌入[31].已有研究表明:任何有限樹都可以通過任意低失真嵌入到有限雙曲空間中,而歐氏空間以多項(xiàng)式速率擴(kuò)張,無限維的歐氏空間也無法滿足任意低失真嵌入有限樹[33,34].

Fig.4 Examples of hyperbolic space embedding圖4 雙曲空間嵌入示例

由于復(fù)雜網(wǎng)絡(luò)的無標(biāo)度性質(zhì)和近似樹狀結(jié)構(gòu)與雙曲空間的負(fù)曲率和指數(shù)擴(kuò)張高度貼合,基于雙曲空間生成模型的嵌入方法作為一類基于幾何模型的網(wǎng)絡(luò)表征學(xué)習(xí)方法誕生.該模型通過將復(fù)雜網(wǎng)絡(luò)嵌入到雙曲空間的龐加萊圓盤模型中,通過圓盤的徑向坐標(biāo)表示節(jié)點(diǎn)流行性,角坐標(biāo)間距離表示節(jié)點(diǎn)間相似性,將網(wǎng)絡(luò)的生長解釋為流行性和相似性的競爭,可以很好地解釋復(fù)雜網(wǎng)絡(luò)中無標(biāo)度、小世界、強(qiáng)聚類等拓?fù)涮卣鱗32].本文首先描述復(fù)雜網(wǎng)絡(luò)雙曲空間的生成模型,然后介紹基于該模型的嵌入方法及無模型的嵌入方法,最后引入嵌入后的應(yīng)用、性能對比及研究展望.

2.2 復(fù)雜網(wǎng)絡(luò)雙曲空間的生成模型

對復(fù)雜網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)和動態(tài)演化過程的刻畫,是復(fù)雜網(wǎng)絡(luò)研究領(lǐng)域內(nèi)的基礎(chǔ)性問題之一,由此引發(fā)的復(fù)雜網(wǎng)絡(luò)生成模型的研究具有很長一段歷史.起初,關(guān)于復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)的假設(shè)形成規(guī)則網(wǎng)絡(luò)和隨機(jī)網(wǎng)絡(luò)兩個極端,較著名的研究是ER 隨機(jī)圖模型[35],該模型假設(shè)網(wǎng)絡(luò)中每條連邊獨(dú)立且連接概率相同,可以生成稀疏、存在巨片、平均距離較短的網(wǎng)絡(luò),但該模型無法解釋實(shí)際網(wǎng)絡(luò)中出現(xiàn)的聚類特性和度分布非均勻性;規(guī)則的最近鄰網(wǎng)絡(luò)和ER 隨機(jī)圖模型都不能解釋許多實(shí)際網(wǎng)絡(luò)同時具有的強(qiáng)聚類、小世界特征,WS 小世界模型[36]作為一種完全規(guī)則網(wǎng)絡(luò)向完全隨機(jī)網(wǎng)絡(luò)的過渡模型誕生,該模型通過在規(guī)則網(wǎng)絡(luò)中引入少量隨機(jī)性產(chǎn)生具有小世界特征的網(wǎng)絡(luò),包括較短的平均距離和高聚類系數(shù);文獻(xiàn)[37]中指出,ER 隨機(jī)圖模型和WS 小世界模型忽略了實(shí)際網(wǎng)絡(luò)中的增長特性和優(yōu)先連接特性,提出了BA 無標(biāo)度網(wǎng)絡(luò)模型,該模型生成的網(wǎng)絡(luò)具有冪率度分布和較短的平均距離,但無法解釋很多現(xiàn)實(shí)網(wǎng)絡(luò)中的強(qiáng)聚類效應(yīng).在上述這些網(wǎng)絡(luò)模型中,連邊關(guān)系都是獨(dú)立的,而現(xiàn)實(shí)網(wǎng)絡(luò)并非如此.例如社交網(wǎng)絡(luò)中,如果兩個人具有共同好友,則他們將比陌生人更容易產(chǎn)生聯(lián)系.當(dāng)網(wǎng)絡(luò)引入幾何模型時,這些拓?fù)涮卣骶秃苋菀椎玫浇忉?最近,復(fù)雜網(wǎng)絡(luò)的雙曲空間生成模型被提了出來,該模型假設(shè)復(fù)雜網(wǎng)絡(luò)處于雙曲幾何空間中,節(jié)點(diǎn)間連接概率受空間中的距離影響,幾何空間中的三角不等式可以解釋現(xiàn)實(shí)網(wǎng)絡(luò)的強(qiáng)聚類效應(yīng).通過調(diào)整模型參數(shù),可轉(zhuǎn)化為隨機(jī)網(wǎng)絡(luò)、BA 網(wǎng)絡(luò)模型等[32,38].本節(jié)首先介紹復(fù)雜網(wǎng)絡(luò)幾何空間生成模型的基本思想,然后對復(fù)雜網(wǎng)絡(luò)雙曲空間的各類生成模型展開介紹.

2.2.1 復(fù)雜網(wǎng)絡(luò)幾何空間的生成模型基本思想

復(fù)雜網(wǎng)絡(luò)幾何空間的生成模型一般認(rèn)為網(wǎng)絡(luò)存在潛在的幾何空間,網(wǎng)絡(luò)由節(jié)點(diǎn)和連邊組成,在幾何空間中布點(diǎn),然后根據(jù)一定的概率進(jìn)行連邊即可生成不同拓?fù)浣Y(jié)構(gòu)的網(wǎng)絡(luò).不同的生成模型在幾何空間的選擇、節(jié)點(diǎn)間連接概率的設(shè)計(jì)和網(wǎng)絡(luò)生成過程這3 方面有所不同.一般認(rèn)為,連接概率受到幾何空間中的距離和節(jié)點(diǎn)的內(nèi)在固有屬性兩方面的影響,節(jié)點(diǎn)固有屬性通過設(shè)計(jì)節(jié)點(diǎn)來隱藏變量表現(xiàn).根據(jù)網(wǎng)絡(luò)生成過程,可以將生成模型分為靜態(tài)模型和動態(tài)模型:靜態(tài)模型中,節(jié)點(diǎn)和連邊一次性生成,不隨時間變化;動態(tài)模型中,網(wǎng)絡(luò)中的節(jié)點(diǎn)會增加或刪減,連邊在節(jié)點(diǎn)加入或移除時發(fā)生變化.

2.2.2 多種雙曲空間生成模型

(1)S1生成模型

S1生成模型是一種簡單的復(fù)雜網(wǎng)絡(luò)幾何生成模型[39],由Krioukov 等人在文獻(xiàn)[40]中提出.該文認(rèn)為,復(fù)雜網(wǎng)絡(luò)存在隱藏的幾何度量空間.提出了S1生成模型,通過模型參數(shù)控制生成網(wǎng)絡(luò)的度分布、聚類系數(shù),并且生成的網(wǎng)絡(luò)可具有無標(biāo)度、強(qiáng)聚類、自相似、小世界特性.

S1生成模型中,假設(shè)節(jié)點(diǎn)均勻分布在半徑為|V|/2π的圓環(huán)上,每個節(jié)點(diǎn)對(vi,vj)之間的連接概率受到幾何空間中的距離dij和節(jié)點(diǎn)拓?fù)湎嚓P(guān)固有屬性dc(i,j)的影響,表現(xiàn)為p(dij/dc(i,j)).令κ為與節(jié)點(diǎn)度相關(guān)的隱藏變量,則dc(i,j)∝κiκj.該式保證節(jié)點(diǎn)平均度,連接概率的具體形式可見后文表5.為了生成符合冪率度分布的網(wǎng)絡(luò),可令κ滿足概率分布.

(2)H2生成模型

由于雙曲空間是指數(shù)擴(kuò)張的,空間本身就是一個連續(xù)版本的“樹”,這與復(fù)雜網(wǎng)絡(luò)的樹狀結(jié)構(gòu)高度吻合.Krioukov 等人在文獻(xiàn)[30]中提出了H2生成模型,該模型是S1生成模型的等價模型.該文認(rèn)為,無標(biāo)度復(fù)雜網(wǎng)絡(luò)的節(jié)點(diǎn)分布在二維有界的雙曲圓盤上.將節(jié)點(diǎn)連邊表示能量為隱藏雙曲距離的非相互作用費(fèi)米子,使用費(fèi)米狄拉克統(tǒng)計(jì)解釋雙曲距離與連接概率的關(guān)系,如公式(13)所示:

其中,β=1/T,T為溫度系數(shù),影響生成網(wǎng)絡(luò)的聚類系數(shù).T→0 時,公式(13)轉(zhuǎn)化為,此時聚類系數(shù)最大化;隨著T的增大聚類系數(shù)降低,T→1 時,聚類系數(shù)趨近于0;T→∞時,圖為經(jīng)典隨機(jī)圖.該模型生成網(wǎng)絡(luò)的度分布滿足公式(14),由此可生成具有任意冪率指數(shù)度分布、聚類系數(shù)的復(fù)雜網(wǎng)絡(luò):

(3)雙曲空間的隨機(jī)幾何圖生成模型

基于S1和H2生成模型,文獻(xiàn)[31]進(jìn)一步提出研究復(fù)雜網(wǎng)絡(luò)的幾何框架,該文假設(shè)復(fù)雜網(wǎng)絡(luò)是一種嵌入在雙曲空間中的隨機(jī)幾何圖,從而非常容易解釋網(wǎng)絡(luò)異質(zhì)性(無標(biāo)度分布現(xiàn)象)和高聚集性.

如圖5 所示,與經(jīng)典的隨機(jī)幾何圖類似,雙曲空間中的隨機(jī)幾何圖首先需要在半徑為R的雙曲圓盤上撒N個點(diǎn),然后以每個點(diǎn)P為圓心、以r=R為半徑作雙曲圓,落在圓內(nèi)的點(diǎn)均與P點(diǎn)相連接形成網(wǎng)絡(luò),連接概率可表示為公式(15),通過該模型生成的網(wǎng)絡(luò)則同時可具備無標(biāo)度和高聚集性:

Fig.5 Example of a random geometric graph in hyperbolic space[31]圖5 雙曲空間的隨機(jī)幾何圖生成模型示例[31]

在該模型中,只有距離小于R的節(jié)點(diǎn)對才產(chǎn)生連接,距離較遠(yuǎn)則無連接.Krioukov 等人進(jìn)一步提出軟化連接模型,任意兩點(diǎn)的連接概率與H2模型相同,當(dāng)β趨近于無窮大時,該模型退化為標(biāo)準(zhǔn)的雙曲空間隨機(jī)幾何圖模型.一般情形下,節(jié)點(diǎn)間連接概率隨著彼此雙曲距離的增大而減小,R為閾值;當(dāng)雙曲距離超過R時,連接概率減小速率加快.文獻(xiàn)[38]對雙曲空間的隨機(jī)幾何圖模型進(jìn)行了詳細(xì)分析,證明該模型可擴(kuò)展為6 種不同的模型,見表4.

Table 4 Expansion of random geometric graph model in hyperbolic space表4 雙曲空間隨機(jī)幾何圖模型擴(kuò)展

(4)PSO 動態(tài)生長模型

前面提到的模型都是靜態(tài)模型,網(wǎng)絡(luò)中的節(jié)點(diǎn)和連接都是一次建立,不隨時間變化的.文獻(xiàn)[32]提出了一個在雙曲空間下的動態(tài)生長模型(popularity-similarity-optimization model,簡稱PSO).

如圖6 所示,PSO 生長模型建立在擴(kuò)展的龐加萊圓盤上,生成網(wǎng)絡(luò)過程如下:(1)t=0 時刻,網(wǎng)絡(luò)為空;(2)t≥0時刻,坐標(biāo)為(rt,θt)的新節(jié)點(diǎn)t加入,其中,rt=ln(t),θt為[0,2π]的隨機(jī)值;(3)t≤m時,新節(jié)點(diǎn)t連接到所有已存在的節(jié)點(diǎn);(4)t>m時,新節(jié)點(diǎn)連接到m個雙曲距離最近的節(jié)點(diǎn),可轉(zhuǎn)化為求解m個sΔθst最小的節(jié)點(diǎn),其中,是控制網(wǎng)絡(luò)平均節(jié)點(diǎn)度的參數(shù),s

Fig.6 Example of PSO model[32]圖6 PSO 模型示例[32]

該模型中,網(wǎng)絡(luò)的生長過程表現(xiàn)為流行性和相似性的競爭,每個節(jié)點(diǎn)徑坐標(biāo)為ln(s),s為誕生時間,代表流行性特征,s越小,節(jié)點(diǎn)誕生越早,新節(jié)點(diǎn)連接它的概率越大;Δθ為相似性特征,Δθ越小,節(jié)點(diǎn)越相似,連接概率越大.在上述模型中,流行性與相似性對節(jié)點(diǎn)連接具有同樣的影響力,可引入流行性與相似性的權(quán)重調(diào)節(jié)參數(shù)λ∈[0,1],使得新節(jié)點(diǎn)連接時最小化sλΔθst.改進(jìn)后的模型即為流行性的衰減模型,在t時刻,新節(jié)點(diǎn)加入時,對于已存在的節(jié)點(diǎn)s

其中,Rt是t時刻雙曲圓盤半徑.

相比于靜態(tài)的雙曲空間隨機(jī)幾何圖模型,該動態(tài)模型具有一些優(yōu)點(diǎn).

(a)動態(tài)模型中節(jié)點(diǎn)根據(jù)時間逐個加入網(wǎng)絡(luò),可以模擬實(shí)際網(wǎng)絡(luò)動態(tài)生長情況;

(b)動態(tài)模型將雙曲坐標(biāo)賦予了實(shí)際含義,徑坐標(biāo)表示的是節(jié)點(diǎn)的流行性,角坐標(biāo)相對差值表示節(jié)點(diǎn)間的相似性,節(jié)點(diǎn)間的連接產(chǎn)生則表現(xiàn)為實(shí)際網(wǎng)絡(luò)中流行性與相似性的競爭;

(c)該模型可以擴(kuò)展為偏好依附網(wǎng)絡(luò)模型、適應(yīng)度網(wǎng)絡(luò)模型等.

PSO 模型存在進(jìn)一步變體GPA(geometric preferential attachment)模型和nPSO(nonuniform PSO)模型,以便產(chǎn)生具有軟社區(qū)[41]或所需社區(qū)結(jié)構(gòu)[42]的雙曲合成網(wǎng)絡(luò).

(5)GPA 模型

由于PSO 模型及前述雙曲空間中的靜態(tài)模型均假設(shè)節(jié)點(diǎn)角坐標(biāo)均勻分布在0～2π范圍內(nèi),節(jié)點(diǎn)間連接概率隨雙曲距離的增大而減小,故沒有角區(qū)域包含空間上緊密相連的節(jié)點(diǎn)集群以形成明確的社區(qū)結(jié)構(gòu).文獻(xiàn)[41]提出了GPA 生成模型,通過使雙曲圓盤中不同角域具有不同的吸引力來形成社區(qū).該模型僅修改了PSO 模型中的角坐標(biāo)生成機(jī)制,在每個節(jié)點(diǎn)加入網(wǎng)絡(luò)中時,先根據(jù)均勻分布選取角坐標(biāo)的候選位置φ1,φ2,…,φi,對每個候選點(diǎn)計(jì)算其引力大小,然后根據(jù)公式(17)的概率選取角坐標(biāo):

其中,引力Ai(φj)為離候選點(diǎn)(ri,φj)距離小于ri的已存在節(jié)點(diǎn)個數(shù);Λ≥0 為模型參數(shù),代表初始引力,節(jié)點(diǎn)角度分布的異質(zhì)性是其減函數(shù).

(6)nPSO 模型

GPA 模型通過調(diào)整PSO 模型中角坐標(biāo)的分布來形成社區(qū)結(jié)構(gòu),但該模型不能明確控制社區(qū)的個數(shù)和規(guī)模.文獻(xiàn)[42]提出了nPSO 模型,通過高斯混合分布生成角坐標(biāo),可調(diào)整社區(qū)數(shù)量和規(guī)模,高效地生成高聚類網(wǎng)絡(luò).

表5 總結(jié)了上述幾種幾何生成模型的設(shè)計(jì)特點(diǎn).

Table 5 Comparison of geometric space generation models for complex networks表5 復(fù)雜網(wǎng)絡(luò)幾何空間的生成模型比較

Table 5 Comparison of geometric space generation models for complex networks (Continued 1)表5 復(fù)雜網(wǎng)絡(luò)幾何空間的生成模型比較(續(xù)1)

Table 5 Comparison of geometric space generation models for complex networks (Continued 2)表5 復(fù)雜網(wǎng)絡(luò)幾何空間的生成模型比較(續(xù)2)

2.3 復(fù)雜網(wǎng)絡(luò)雙曲空間的嵌入方法

2.3.1 基于生成模型的嵌入方法

復(fù)雜網(wǎng)絡(luò)的雙曲空間生成模型能夠構(gòu)建跨越多種拓?fù)浣Y(jié)構(gòu)和動態(tài)特性的類似于真實(shí)網(wǎng)絡(luò)的合成網(wǎng)絡(luò),我們是否可以逆轉(zhuǎn)這種合成,并給定一個真實(shí)網(wǎng)絡(luò),將網(wǎng)絡(luò)映射(嵌入)到雙曲空間中,在某種程度上與生成模型保持一致?這種嵌入是否存在高效的后續(xù)應(yīng)用?這些問題成為當(dāng)下的研究熱點(diǎn),引出了大量研究成果.其中,基于生成模型的嵌入方法假設(shè)網(wǎng)絡(luò)由給定的生成模型產(chǎn)生,逆向推斷最可能生成該網(wǎng)絡(luò)的生成模型參數(shù),主要可分為基于最大似然估計(jì)的嵌入方法、基于流形學(xué)習(xí)的嵌入方法和兩者結(jié)合的嵌入方法.

一般來說,復(fù)雜網(wǎng)絡(luò)雙曲空間的嵌入方法要求輸入為連通圖G=(V,E),因?yàn)榕c網(wǎng)絡(luò)中巨片不連通的部分沒有相應(yīng)的鄰接信息,可以被嵌入到雙曲空間中的任意位置.由于生成模型中徑坐標(biāo)與節(jié)點(diǎn)度高度相關(guān),不同的嵌入方法對于徑坐標(biāo)一般均根據(jù)模型采用直接推斷方法來估計(jì).

對于靜態(tài)隨機(jī)幾何圖模型,一般采用公式(18)來估計(jì)雙曲圓盤最大半徑,用公式(19)來估計(jì)每個節(jié)點(diǎn)的徑坐標(biāo):

對于動態(tài)PSO 模型,一般重現(xiàn)其生長過程,根據(jù)ri=2λln(i)+2(1-λ)ln(N)指定徑坐標(biāo),其中,i={1,2,…,N}為按節(jié)點(diǎn)度降序排列的節(jié)點(diǎn)編號,λ=1/(γ-1),γ為度分布冪指數(shù).

上述基于生成模型的嵌入方法由此轉(zhuǎn)變?yōu)橐粋€角坐標(biāo)參數(shù)估計(jì)問題.基于最大似然估計(jì)的嵌入方法根據(jù)似然函數(shù)推斷每個節(jié)點(diǎn)在隱藏的幾何空間中的坐標(biāo),該問題為NP-Hard 問題[39],只能通過啟發(fā)式方法獲取可能的近似解,該類方法的計(jì)算復(fù)雜度和嵌入精確度依賴于選擇的啟發(fā)式方法和生成模型.基于流形學(xué)習(xí)的嵌入方法具有一些快速算法,但其中使用矩陣分解的一類方法在應(yīng)用于大規(guī)模網(wǎng)絡(luò)嵌入時仍然具有O(N2)的復(fù)雜度.另外,基于流行學(xué)習(xí)的嵌入方法一般在歐氏空間中計(jì)算,只能通過龐加萊圓盤的保角性完成角坐標(biāo)的近似推斷,徑坐標(biāo)推斷則需要使用上述方法來計(jì)算得出.將流行學(xué)習(xí)與最大似然估計(jì)結(jié)合所形成的嵌入方法一般先通過流行學(xué)習(xí)方法近似估計(jì)嵌入坐標(biāo)初值,然后通過最大似然估計(jì)法提高嵌入精度.本節(jié)將對不同的嵌入方法展開介紹.

(1)基于最大似然估計(jì)的嵌入方法

最大似然估計(jì)的目標(biāo)是找到生成模型與觀測網(wǎng)絡(luò)的最佳匹配,實(shí)際是在根據(jù)觀測網(wǎng)絡(luò)解析參數(shù)估計(jì)問題.在貝葉斯準(zhǔn)則下,該估計(jì)問題的后驗(yàn)概率為

其中,Prob(A,{ri,θi};Model)表示Model生成坐標(biāo){ri,θi}和觀測網(wǎng)絡(luò)鄰接矩陣A的聯(lián)合概率,Prob(A;Model)表示Model生成觀測網(wǎng)絡(luò)鄰接矩陣A的先驗(yàn)概率.公式(21)表示Model生成坐標(biāo){ri,θi}的先驗(yàn)概率,公式(22)表示Model在坐標(biāo){ri,θi}下生成鄰接矩陣A的條件概率:

如果公式(21)的先驗(yàn)概率已知,則可使用貝葉斯估計(jì)最大化公式(20)來獲得最佳估計(jì).然而,在大部分情況下先驗(yàn)信息未知,一般通過最大化似然函數(shù)公式(22),或其對數(shù)形式公式(23)來推斷嵌入坐標(biāo):

基于最大似然估計(jì)的嵌入方法通過不同的策略最大化該似然函數(shù)來推斷角坐標(biāo).

? HyperMap

HyperMap[43]是一種基于最大似然估計(jì)的雙曲空間無權(quán)網(wǎng)絡(luò)嵌入方法,通過重現(xiàn)PSO 模型生長過程完成角坐標(biāo)的推斷.具體過程如下.

1)節(jié)點(diǎn)按照度從大到小重整為i=1,2,…,N;

2)節(jié)點(diǎn)i=1 誕生,隨機(jī)角坐標(biāo)θ1∈[0,2π];

3)節(jié)點(diǎn)i=2,3,…,N的角坐標(biāo)通過最大化來獲取.

? HyperMap-CN

在HyperMap 中,度大的節(jié)點(diǎn)先生成,且在生成時僅考慮與度更大的節(jié)點(diǎn)是否存在連接對其在雙曲空間中坐標(biāo)的影響,導(dǎo)致度大的節(jié)點(diǎn)嵌入的角坐標(biāo)并不精確.HyperMap-CN[44]通過修改HyperMap 中的似然函數(shù),引入共同鄰居信息來推斷節(jié)點(diǎn)嵌入坐標(biāo).經(jīng)過調(diào)整后,節(jié)點(diǎn)坐標(biāo)推斷更加精確,但計(jì)算復(fù)雜度由HyperMap 的O(N3)增大到O(N4).為了減小計(jì)算量,Papadopoulos 等人進(jìn)一步提出混合模型,僅對度大的節(jié)點(diǎn)i(ki≤kspeedup)使用修改后的似然優(yōu)化,并且可采用加速的啟發(fā)式方法估計(jì)角坐標(biāo).對于度大的節(jié)點(diǎn)i,先僅考慮i的鄰居節(jié)點(diǎn)j(j

? EE

在HyperMap 和HyperMap-CN 的基礎(chǔ)上,文獻(xiàn)[45]提出一種可應(yīng)用于大規(guī)模網(wǎng)絡(luò)的雙曲空間靜態(tài)隨機(jī)幾何圖模型高效嵌入方法,該方法具有擬線性的時間復(fù)雜度.與HyperMap 相似,該方法采用貪婪策略完成嵌入.與對網(wǎng)絡(luò)全局的嵌入結(jié)果同時優(yōu)化相比,采用貪婪策略,每次最優(yōu)化一個節(jié)點(diǎn)的嵌入坐標(biāo)相對容易.在得到模型的全局參數(shù)估計(jì)后,該方法先嵌入網(wǎng)絡(luò)的核心部分,即度較大的節(jié)點(diǎn).通過引入共同鄰居信息,優(yōu)化隨機(jī)幾何圖階躍模型的似然來獲取節(jié)點(diǎn)對的角度差,然后借助彈性嵌入方法完成網(wǎng)絡(luò)核心部分嵌入.對于其他度較小的節(jié)點(diǎn),先根據(jù)已嵌入的鄰居節(jié)點(diǎn)估計(jì)角坐標(biāo)初值,然后在初值附近隨機(jī)采樣多個坐標(biāo)點(diǎn),選取似然最優(yōu)值作為最終結(jié)果.

(2)基于流行學(xué)習(xí)的嵌入方法

基于流行學(xué)習(xí)的嵌入方法以Laplace 特征映射為代表,原始用于高維數(shù)據(jù)的降維.該類方法一般針對高維情形下的數(shù)據(jù)稀疏、難以計(jì)算等“維數(shù)災(zāi)難”問題,通過某種策略將原始高維空間轉(zhuǎn)換為低維子空間,在子空間中,數(shù)據(jù)密度提高,結(jié)構(gòu)簡化,便于后續(xù)應(yīng)用計(jì)算.但這類方法降維的子空間一般為歐氏空間,雙曲嵌入只能通過該相似子空間推斷角坐標(biāo),而徑坐標(biāo)及其他參數(shù)的推斷則根據(jù)具體模型計(jì)算得出.

? LaBNE

基于網(wǎng)絡(luò)中互相連接的節(jié)點(diǎn)在雙曲空間中彼此靠近的基本思想,針對無向、無權(quán)、單一組成成分的網(wǎng)絡(luò),Alanis-Lobato 等人提出了基于Laplace 譜分解的龐加萊圓盤嵌入方法LaBNE(Laplacian-based network embedding)[46].定義由節(jié)點(diǎn)度組成的對角陣D,網(wǎng)絡(luò)的鄰接矩陣A,則網(wǎng)絡(luò)的Laplace 矩陣為L=D-A;Y=[y1,y2]為N×2 矩陣,該矩陣的第i行為節(jié)點(diǎn)嵌入歐氏圓盤坐標(biāo).最小化,使彼此連接的節(jié)點(diǎn)坐標(biāo)靠近,同時加入約束條件YTDY=I來避免節(jié)點(diǎn)聚集(I為單位陣).最終,Y的求解可以轉(zhuǎn)換為求解廣義特征值問題.基于龐加萊圓盤模型的保角性,角坐標(biāo)可以通過θ=arctan(y2/y1)計(jì)算得到.

? Coalescent embedding

基于LaBNE,文獻(xiàn)[47]衍生出一類基于流行學(xué)習(xí)的雙曲空間嵌入方法.該類方法通過節(jié)點(diǎn)度、共同鄰居和節(jié)點(diǎn)間最短路徑等局部拓?fù)湫畔⒍x了RA(repulsion-attraction)規(guī)則和EBC(edge betweenness centrality)規(guī)則.首先,基于該規(guī)則對無權(quán)網(wǎng)絡(luò)加權(quán);然后,使用流行學(xué)習(xí)方法,如Isomap、拉普拉斯特征映射獲取近似角坐標(biāo);最后,引入角度均勻化調(diào)整,使角坐標(biāo)滿足生成模型關(guān)于節(jié)點(diǎn)分布的基本假設(shè).通過此流程,提高了LaBNE 嵌入的精確性,并提供了一系列嵌入方法.

(3)流行學(xué)習(xí)與最大似然估計(jì)結(jié)合的嵌入方法

? LaBNE+HM

HyperMap 方法基于搜索求解最大似然估計(jì)來完成雙曲空間嵌入,該方法嵌入精度高,但是計(jì)算量大,對于大規(guī)模的網(wǎng)絡(luò)則只能通過啟發(fā)式方法求解;LaBNE 方法基于Laplace 譜分解,計(jì)算速度相對較快,但卻高度依賴于拓?fù)湫畔?僅考慮使有連接的節(jié)點(diǎn)彼此靠近,無法保證無連接的節(jié)點(diǎn)彼此遠(yuǎn)離,在網(wǎng)絡(luò)平均度高、聚類系數(shù)高時才能獲得較為精確的嵌入結(jié)果.LaBNE+HM[48]將兩者的優(yōu)勢相結(jié)合,先使用LaBNE 近似估計(jì)嵌入初值,再根據(jù)網(wǎng)絡(luò)特征調(diào)整搜索范圍,采用HyperMap 精確求解,在保證嵌入精度的前提下,縮短了HyperMap 求解時間.

? Mercator

Mercator[39]將流行學(xué)習(xí)與最大似然相結(jié)合,在觀測網(wǎng)絡(luò)和S1模型間求解最佳匹配.該方法不僅推斷節(jié)點(diǎn)角坐標(biāo)次序及具體值,還推斷節(jié)點(diǎn)隱藏期望度和模型全局參數(shù),并且可以將任意度分布網(wǎng)絡(luò)嵌入到S1模型中.Mercator 提供兩種模式:在快速模式下,首先根據(jù)S1模型統(tǒng)計(jì)分析推斷得到全局參數(shù)β、μ和每個節(jié)點(diǎn)i的隱藏期望度變量κi,然后使用拉普拉斯特征映射估計(jì)角坐標(biāo)θi,基于推斷的β、μ、κi以及節(jié)點(diǎn)間有無連邊進(jìn)一步調(diào)整角坐標(biāo);精確模式將快速模式嵌入結(jié)果作為初值,基于最大似然估計(jì)理論,使用洋蔥分解[49]從中心節(jié)點(diǎn)開始,在節(jié)點(diǎn)鄰居角坐標(biāo)均值處局部搜索優(yōu)化角坐標(biāo),最后根據(jù)優(yōu)化后的角坐標(biāo)更新隱藏期望度.

(4)其他嵌入方法

? LPCS

與前述流行學(xué)習(xí)或最大似然估計(jì)的嵌入方法有所不同,LPCS[50]是一種基于社區(qū)結(jié)構(gòu)的雙曲空間嵌入方法,通過將社區(qū)結(jié)構(gòu)信息引入,使不同社區(qū)的節(jié)點(diǎn)具有一定的相對角度,相同社區(qū)的節(jié)點(diǎn)彼此靠近以完成嵌入.該方法基于EPSO[43]生成模型,具有線性時間復(fù)雜度,適用于具有一定社區(qū)結(jié)構(gòu)的冪率度分布網(wǎng)絡(luò),具體按照如下步驟完成嵌入.

1)檢測層次性社區(qū);

2)從節(jié)點(diǎn)數(shù)量最多的社區(qū)開始,利用社區(qū)親密度指數(shù)對頂層社區(qū)進(jìn)行排序,該指數(shù)考慮了社區(qū)內(nèi)部和社區(qū)之間的連邊比例;

3)根據(jù)高層社區(qū)的順序,遞歸地對低層社區(qū)進(jìn)行排序,直至到達(dá)層次結(jié)構(gòu)的底層;

4)為每一個底層社區(qū)分配一個與社區(qū)節(jié)點(diǎn)大小成比例的角度范圍,以不重疊的角度范圍覆蓋整個社區(qū).在相關(guān)底層社區(qū)的角度范圍內(nèi),隨機(jī)均勻采樣節(jié)點(diǎn)的角坐標(biāo).

CHM[51]采用與LPCS 類似的方法得到雙曲空間嵌入初值,然后使用最大似然估計(jì)優(yōu)化初值,提高精確度.

? MCA

具有稀疏、強(qiáng)聚類、小世界、異質(zhì)性的復(fù)雜網(wǎng)絡(luò)通?？梢酝ㄟ^最小生成樹實(shí)現(xiàn)高效導(dǎo)航.MCA[52]方法定義相似性依附機(jī)制,通過不斷生長的最小生成樹滿足最低彎曲度策略,有效地近似雙曲圓盤中節(jié)點(diǎn)角坐標(biāo),完成雙曲空間嵌入.該方法具有近似線性復(fù)雜度,同時,嵌入精度超過HyperMap-CN,低于Coalescent Embedding.具體過程如下.

3)基于Prim 最小生成樹構(gòu)造方法依次排列最低排斥度節(jié)點(diǎn),將節(jié)點(diǎn)序列通過角度等距調(diào)整或斥力-引力等距調(diào)整使角坐標(biāo)分布在[0,2π].

表6 對上述幾種復(fù)雜網(wǎng)絡(luò)雙曲空間嵌入方法的時間復(fù)雜度進(jìn)行了簡單總結(jié).

Table 6 Comparison of embedding of complex networks to hyperbolic space表6 復(fù)雜網(wǎng)絡(luò)雙曲空間的嵌入方法比較

2.3.2 無生成模型的嵌入方法

由于表達(dá)信息的能力是學(xué)習(xí)和泛化的先決條件,因此提高嵌入方法的表示能力非常重要,這樣它就可以用于各種實(shí)際數(shù)據(jù)的復(fù)雜模式之中.盡管歐氏空間嵌入取得了成功,但最近的研究結(jié)果表明,來自多個領(lǐng)域(如生物學(xué)、網(wǎng)絡(luò)科學(xué)、計(jì)算機(jī)圖形學(xué)或計(jì)算機(jī)視覺)的許多類型的復(fù)雜數(shù)據(jù)(例如圖數(shù)據(jù))都顯示出高度非歐幾里德潛在結(jié)構(gòu)[53].在這種情況下,歐幾里德空間沒有提供最強(qiáng)大或最有意義的幾何表示.為了更好地學(xué)習(xí)數(shù)據(jù)的層次結(jié)構(gòu)和復(fù)雜模式,近期涌現(xiàn)了許多無生成模型的雙曲空間嵌入方法[8,29,34,54-59].這些方法一般通過雙曲距離刻畫數(shù)據(jù)間相似度來將其嵌入到雙曲空間中,利用雙曲空間對數(shù)據(jù)的表達(dá)能力,在貪婪路由、層級表示學(xué)習(xí)、知識問答、鏈路預(yù)測、最短路徑長度預(yù)測、機(jī)器翻譯等應(yīng)用上取得性能上的提升.

3 復(fù)雜網(wǎng)絡(luò)雙曲空間模型的應(yīng)用

通過將復(fù)雜網(wǎng)絡(luò)嵌入到雙曲空間中,高維稀疏的網(wǎng)絡(luò)結(jié)構(gòu)信息轉(zhuǎn)化為低維稠密的實(shí)值向量,具有一般嵌入方法降低計(jì)算復(fù)雜度的特點(diǎn).另外,每個節(jié)點(diǎn)被表示為潛在幾何空間中確定位置的坐標(biāo),幾何空間中的距離度量決定節(jié)點(diǎn)間存在連接的可能性,因此可將幾何工具和方法論應(yīng)用到網(wǎng)絡(luò)研究中,以有效解釋現(xiàn)實(shí)網(wǎng)絡(luò)中的物理現(xiàn)象.例如,幾何空間中的三角不等式給出了現(xiàn)實(shí)網(wǎng)絡(luò)中聚類效應(yīng)的合理解釋[60].

由于復(fù)雜網(wǎng)絡(luò)雙曲空間模型的物理含義和低維向量表示便于進(jìn)行高效計(jì)算,基于該模型的嵌入將有益于很多圖分析的應(yīng)用.本節(jié)將圍繞基于復(fù)雜網(wǎng)絡(luò)雙曲空間模型嵌入后的各類應(yīng)用展開介紹.

3.1 基于雙曲徑坐標(biāo)的層次結(jié)構(gòu)發(fā)現(xiàn)

近年來,因雙曲空間嵌入對潛在層次結(jié)構(gòu)的有效捕獲,將數(shù)據(jù)嵌入雙曲空間表示受到越來越多的關(guān)注[8,34,56-58].這種層次結(jié)構(gòu)捕獲的能力可能與雙曲空間的關(guān)鍵特性密切相關(guān),即:空間容量隨徑向呈指數(shù)增長,而在非歐氏空間中呈緩慢的多項(xiàng)式增長.樹狀結(jié)構(gòu)數(shù)據(jù)幾何形狀的增長方式與雙曲空間保持一致,因此可以通過雙曲空間精確捕捉樹狀的層次結(jié)構(gòu).如圖7 所示:文獻(xiàn)[56,57]將WordNet 等網(wǎng)絡(luò)嵌入到低維雙曲空間中,學(xué)習(xí)其層次結(jié)構(gòu),與高維歐氏空間相比具有更優(yōu)的重構(gòu)誤差和鏈路預(yù)測能力;文獻(xiàn)[58]將問答系統(tǒng)嵌入到雙曲空間中,發(fā)現(xiàn)其潛在的層次結(jié)構(gòu),對問答系統(tǒng)進(jìn)行快速而高效的排序檢索;文獻(xiàn)[61]將單詞和句子嵌入到雙曲空間中,保留了單詞的共現(xiàn)頻率信息和句子短語選區(qū)信息.

Fig.7 Example of embedding for learning hierarchical representation in hyperbolic space[56]圖7 雙曲空間中層次結(jié)構(gòu)發(fā)現(xiàn)示例[56]

3.2 基于雙曲角坐標(biāo)劃分的社區(qū)發(fā)現(xiàn)

在復(fù)雜網(wǎng)絡(luò)的龐加萊圓盤嵌入結(jié)果中,雙曲距離較近的節(jié)點(diǎn)存在較大的連接概率.雙曲空間隨圓盤半徑呈指數(shù)增長,位于龐加萊圓盤中心附近的節(jié)點(diǎn)有大量的連接,而外圍的節(jié)點(diǎn)只靠近角坐標(biāo)相近的節(jié)點(diǎn).文獻(xiàn)[62-64]研究表明:真實(shí)網(wǎng)絡(luò)在龐加萊圓盤中嵌入的節(jié)點(diǎn)角坐標(biāo)不是均勻分布的;相反,它們以一種異構(gòu)的方式分布,節(jié)點(diǎn)在某些角坐標(biāo)附近的集群化揭示了節(jié)點(diǎn)之間存在大量連接的區(qū)域,該區(qū)域組成一個社區(qū)[32,41,42,65-68].另外,文獻(xiàn)[69]的研究也說明,具有強(qiáng)模塊化的網(wǎng)絡(luò)嵌入到雙曲圓盤中表現(xiàn)出同一社區(qū)內(nèi)節(jié)點(diǎn)角度的高度一致性.基于這種思想,根據(jù)雙曲模型嵌入結(jié)果的聚類[70]或角坐標(biāo)劃分[64]可以設(shè)計(jì)快速而高效的社區(qū)發(fā)現(xiàn)算法,如圖8 所示,相同顏色的節(jié)點(diǎn)組成一個社區(qū).基于復(fù)雜網(wǎng)絡(luò)雙曲圓盤嵌入的社區(qū)劃分操作簡單、高效,劃分結(jié)果直觀、明確.

Fig.8 Example of community detection in hyperbolic space[64]圖8 雙曲空間中社區(qū)發(fā)現(xiàn)示例[64]

3.3 基于雙曲距離度量的路徑搜索

從腦神經(jīng)網(wǎng)絡(luò)到社交網(wǎng)絡(luò)、互聯(lián)網(wǎng)和交通網(wǎng)絡(luò),信息或能量的傳遞是許多復(fù)雜系統(tǒng)的關(guān)鍵功能.已有研究結(jié)果表明:即使不具備系統(tǒng)的全局知識,網(wǎng)絡(luò)中的節(jié)點(diǎn)仍能執(zhí)行有效的信息路由.雙曲嵌入為網(wǎng)絡(luò)中每個節(jié)點(diǎn)提供了幾何空間坐標(biāo),故可以借助坐標(biāo)進(jìn)行高效的貪婪路由.在信息轉(zhuǎn)發(fā)時,不需要提前計(jì)算路由,每個節(jié)點(diǎn)只需知道目的節(jié)點(diǎn)坐標(biāo)和鄰居節(jié)點(diǎn)坐標(biāo),通過計(jì)算雙曲距離,每次選取最接近目的節(jié)點(diǎn)的鄰居節(jié)點(diǎn)作為下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn),該應(yīng)用說明,雙曲模型具有可導(dǎo)航性[54,62,71,72].如圖9 所示:由于雙曲空間龐加萊圓盤模型中的測地線(紅色虛線)為弧形,故貪婪路由的中繼轉(zhuǎn)發(fā)節(jié)點(diǎn)更偏向于靠近圓盤中心的樞紐節(jié)點(diǎn)(藍(lán)色實(shí)線為轉(zhuǎn)發(fā)路徑).大規(guī)模圖中,計(jì)算最短路徑較為困難[73],貪婪路由僅需要嵌入后的少量局部信息計(jì)算雙曲距離,就可以獲取接近最短的轉(zhuǎn)發(fā)路徑,是一種高效的路由方法.

Fig.9 Example of greedy routing in hyperbolic space[62]圖9 雙曲空間中貪婪路由示例[62]

由于復(fù)雜網(wǎng)絡(luò)具有路徑多樣性,結(jié)合雙曲嵌入,大量不相交路徑分布于雙曲空間通過源目的節(jié)點(diǎn)的測地線附近[62],類似于貪婪路由的單路徑搜索亦可擴(kuò)展到多路徑搜索.

3.4 基于雙曲距離度量的關(guān)鍵節(jié)點(diǎn)發(fā)現(xiàn)

復(fù)雜網(wǎng)絡(luò)的異構(gòu)性導(dǎo)致每個節(jié)點(diǎn)的結(jié)構(gòu)和功能有所不同,精確估計(jì)網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)在網(wǎng)絡(luò)優(yōu)化、藥物研發(fā)、輿情控制等方面具有廣泛的應(yīng)用前景.網(wǎng)絡(luò)的介數(shù)中心性這一經(jīng)典的關(guān)鍵節(jié)點(diǎn)排序指標(biāo)需要計(jì)算所有節(jié)點(diǎn)對的最短路徑,在無權(quán)網(wǎng)絡(luò)中,用布蘭德斯的算法計(jì)算介數(shù)中心性具有O(|V||E|)的時間復(fù)雜度.而在雙曲空間中,通過貪婪路由近似最短路徑,只需要計(jì)算所有節(jié)點(diǎn)對的雙曲距離即可估算出介數(shù)中心性,具有O(|V|2)的時間復(fù)雜度[73].類似的研究工作包括文獻(xiàn)[74]提出的雙曲空間中快速計(jì)算接近度中心性方法和文獻(xiàn)[75]提出的雙曲流量負(fù)載中心性(hyperbolic traffic load centrality)方法.

3.5 基于雙曲距離度量的鏈路預(yù)測

鏈路預(yù)測是指通過已知的各種信息,預(yù)測給定網(wǎng)絡(luò)中尚不存在連邊的兩個節(jié)點(diǎn)之間產(chǎn)生連接的可能性.鏈路預(yù)測模型可以幫助我們理解網(wǎng)絡(luò)結(jié)構(gòu),并且具有很多實(shí)際的應(yīng)用價值,比如指導(dǎo)蛋白質(zhì)交互實(shí)驗(yàn)、建立推薦系統(tǒng)等[50].很多鏈路預(yù)測方法基于節(jié)點(diǎn)相似性,其基本假設(shè)是:相似性越大的節(jié)點(diǎn)之間,存在鏈接的可能性越大.復(fù)雜網(wǎng)絡(luò)的雙曲空間模型中明確定義了與雙曲距離密切相關(guān)的連接概率,僅僅只需要根據(jù)嵌入坐標(biāo)計(jì)算節(jié)點(diǎn)對的雙曲距離,就可以進(jìn)行鏈路預(yù)測.該思想操作簡單,并且可以獲得高精度預(yù)測結(jié)果,在部分網(wǎng)絡(luò)上性能甚至優(yōu)于Common-neighbors(CN)和Katz index(Katz)等經(jīng)典鏈路預(yù)測方法[32,43,44,50,67,76].

3.6 基于雙曲坐標(biāo)的網(wǎng)絡(luò)演化分析

本文所述研究大多都是靜態(tài)網(wǎng)絡(luò)的雙曲空間嵌入,但是現(xiàn)實(shí)網(wǎng)絡(luò)一般都具有復(fù)雜的動態(tài)演變過程,比如社交網(wǎng)絡(luò)中不斷有新用戶加入和用戶交友行為產(chǎn)生.隨著網(wǎng)絡(luò)的演化,網(wǎng)絡(luò)的表征也需要隨之更新.已有的雙曲空間中網(wǎng)絡(luò)演化的分析方法將動態(tài)網(wǎng)絡(luò)視為由多個靜態(tài)網(wǎng)絡(luò)快照組成,分時段對靜態(tài)快照嵌入雙曲空間來研究網(wǎng)絡(luò)演化規(guī)律[64].但這類方法將靜態(tài)網(wǎng)絡(luò)嵌入算法直接應(yīng)用到動態(tài)演化網(wǎng)絡(luò)上會遇到一系列問題,比如:由于缺乏增量嵌入方法,即使網(wǎng)絡(luò)變化很小也必須重新嵌入;由于一些隨機(jī)噪聲的存在,不同時段的嵌入結(jié)果可能不夠穩(wěn)定、前后差異較大等.因此,雙曲空間中的網(wǎng)絡(luò)演化分析仍然是未來研究的重要課題之一.

3.7 基于雙曲坐標(biāo)的多層網(wǎng)絡(luò)關(guān)聯(lián)性及魯棒性分析

關(guān)系的多重性是現(xiàn)實(shí)網(wǎng)絡(luò)的共同特征,比如社交網(wǎng)絡(luò)中,人與人之間的關(guān)系多種多樣.現(xiàn)實(shí)的多層網(wǎng)絡(luò)往往不是單層網(wǎng)絡(luò)的隨機(jī)組合,分析不同網(wǎng)絡(luò)層次之間的關(guān)聯(lián)性,對于理解現(xiàn)實(shí)網(wǎng)絡(luò)具有重大意義.通過將每一層網(wǎng)絡(luò)嵌入到雙曲空間中,節(jié)點(diǎn)層與層之間的坐標(biāo)會表現(xiàn)出顯著的相關(guān)性,這些相關(guān)性揭示了多層網(wǎng)絡(luò)隱藏的幾何關(guān)聯(lián),可以應(yīng)用于層間鏈路預(yù)測、貪婪路由、社區(qū)發(fā)現(xiàn)[67].另外,在相互作用的多層網(wǎng)絡(luò)中,部分節(jié)點(diǎn)的失效會導(dǎo)致與之依賴的節(jié)點(diǎn)失效,從而產(chǎn)生級聯(lián)失效現(xiàn)象,這種級聯(lián)失效往往會導(dǎo)致整個相互依賴系統(tǒng)的崩潰.在網(wǎng)絡(luò)科學(xué)研究中,滲流理論是研究復(fù)雜網(wǎng)絡(luò)魯棒性與網(wǎng)絡(luò)團(tuán)簇演變的一個重要手段.已有研究結(jié)果表明:當(dāng)層間角坐標(biāo)的相關(guān)性較高時,滲流變換平滑,網(wǎng)絡(luò)魯棒性較強(qiáng);當(dāng)相關(guān)性較低時,滲流變換易發(fā)生突變,網(wǎng)絡(luò)魯棒性較弱[69,77].多層網(wǎng)絡(luò)的雙曲空間嵌入,可以對層間關(guān)聯(lián)性及魯棒性進(jìn)行分析,有助于設(shè)計(jì)網(wǎng)絡(luò)保護(hù)策略和更健壯、更可控的相互依賴系統(tǒng).

3.8 基于雙曲坐標(biāo)的復(fù)雜網(wǎng)絡(luò)幾何重整化

許多復(fù)雜的網(wǎng)絡(luò),如Internet、社交和生物網(wǎng)絡(luò),往往具有節(jié)點(diǎn)的異構(gòu)度分布.這些分布可以用冪律衰減來描述:它們在度變量重新標(biāo)度的情況下保持不變.這表明可能存在對網(wǎng)絡(luò)結(jié)構(gòu)的某種變換,使其統(tǒng)計(jì)特性保持不變[78].重整化變換按照一定的規(guī)則將網(wǎng)絡(luò)中的數(shù)個節(jié)點(diǎn)合并為超級節(jié)點(diǎn),抓取網(wǎng)絡(luò)中的部分屬性.通過重整化變換,可將復(fù)雜結(jié)構(gòu)簡單化,便于分析網(wǎng)絡(luò)結(jié)構(gòu)特征.例如,該變換揭示了某些網(wǎng)絡(luò)具有自相似嵌套的層次結(jié)構(gòu)[79].已有研究結(jié)果表明:通過對復(fù)雜網(wǎng)絡(luò)雙曲空間嵌入的結(jié)果進(jìn)行重整化,使相同徑坐標(biāo)下角坐標(biāo)彼此靠近的節(jié)點(diǎn)合并,可實(shí)現(xiàn)網(wǎng)絡(luò)規(guī)?？s小和多尺度貪婪路由[80].

3.9 基于雙曲空間表達(dá)模型的可視化

圖的二維可視化問題研究遍布網(wǎng)絡(luò)科學(xué)、數(shù)據(jù)挖掘、生物科學(xué)等各個領(lǐng)域.復(fù)雜網(wǎng)絡(luò)雙曲空間的表征學(xué)習(xí)為可視化提供了極大的便利,將每個節(jié)點(diǎn)通過二維實(shí)值向量表示,研究者們可以很容易地獲得高維數(shù)據(jù)的可視化表達(dá).并且,利用復(fù)雜網(wǎng)絡(luò)雙曲空間模型的物理含義,該可視化表達(dá)對社區(qū)發(fā)現(xiàn)、層次結(jié)構(gòu)提取、流行性相似性分析以及其他潛在網(wǎng)絡(luò)結(jié)構(gòu)發(fā)現(xiàn)都具有重大意義.

3.10 雙曲空間結(jié)合機(jī)器學(xué)習(xí)

基于雙曲空間對樹狀結(jié)構(gòu)數(shù)據(jù)的精確表示和高效捕獲層次結(jié)構(gòu)的能力,雙曲空間的嵌入已經(jīng)應(yīng)用到各類領(lǐng)域中,包括自然語言處理[34,56,61]和網(wǎng)絡(luò)科學(xué)[43,44,46]等.相比于高維的歐氏空間,這些方法僅只需要低維的雙曲空間,便能夠在各自的后續(xù)任務(wù)中取得更佳性能[81,82].例如,文獻(xiàn)[81]將支持向量機(jī)(support vector machine,簡稱SVM)與雙曲空間相結(jié)合,提出了雙曲支持向量機(jī),通過雙曲面模型進(jìn)行超平面劃分,在合成網(wǎng)絡(luò)與現(xiàn)實(shí)網(wǎng)絡(luò)的節(jié)點(diǎn)多分類任務(wù)上取得性能上的提升.文獻(xiàn)[29,59,82]將雙曲空間與神經(jīng)網(wǎng)絡(luò)相結(jié)合,分別引入雙曲神經(jīng)網(wǎng)絡(luò)、雙曲注意力網(wǎng)絡(luò)、雙曲圖卷積網(wǎng)絡(luò),在機(jī)器翻譯、圖分析、可視化問答等任務(wù)上取得性能上的提升.

4 復(fù)雜網(wǎng)絡(luò)雙曲空間表征學(xué)習(xí)方法的性能評估

本文介紹了多種復(fù)雜網(wǎng)絡(luò)雙曲空間的表征學(xué)習(xí)方法,不同方法在坐標(biāo)推斷精確度、后續(xù)任務(wù)性能以及算法執(zhí)行時間上存在一定的差異.通過將各種方法應(yīng)用于合成網(wǎng)絡(luò)和真實(shí)網(wǎng)絡(luò),來給出其性能對比結(jié)果.其中,合成網(wǎng)絡(luò)通過PSO 模型生成,節(jié)點(diǎn)數(shù)均為1 000,冪律度分布冪指數(shù)γ=2.5,平均度,溫度系數(shù)T=0.1,0.3,0.5,0.7,0.9,每組參數(shù)合成5 個網(wǎng)絡(luò).圖10 給出了實(shí)驗(yàn)結(jié)果,a、b、c組分別對應(yīng)平均度為4、8、12 的合成網(wǎng)絡(luò).C-score衡量角坐標(biāo)正確排序的節(jié)點(diǎn)對比例;HD-correlation 為所有節(jié)點(diǎn)對真實(shí)和推斷的雙曲距離之間的皮爾遜相關(guān)系數(shù);GR-score 衡量嵌入后貪婪路由的性能,當(dāng)GR-score 為1 時,所有節(jié)點(diǎn)對貪婪路由均可成功且為最短路徑;Time為嵌入算法執(zhí)行時間.各指標(biāo)的詳細(xì)定義參見文獻(xiàn)[47].

Fig.10 Performance evaluation of hyperbolic embedding in synthetic networks圖10 合成網(wǎng)絡(luò)雙曲嵌入的性能評估

除了合成網(wǎng)絡(luò),本文還將不同的表征學(xué)習(xí)方法應(yīng)用于真實(shí)網(wǎng)絡(luò),表7 給出了不同真實(shí)網(wǎng)絡(luò)數(shù)據(jù)的相關(guān)特征和來源,所有的真實(shí)網(wǎng)絡(luò)均經(jīng)過去除自環(huán)、重邊、取最大連通片的處理過程.

Table 7 Overview of the considered real-world network data表7 真實(shí)網(wǎng)絡(luò)數(shù)據(jù)概覽

由于真實(shí)網(wǎng)絡(luò)數(shù)據(jù)無法獲知雙曲空間原始坐標(biāo),只能根據(jù)推斷坐標(biāo)分析其性能差異,故無法計(jì)算C-score 和HD-correlation 指標(biāo),這里使用連接概率和對數(shù)似然替代分析.圖11 給出了真實(shí)網(wǎng)絡(luò)雙曲嵌入的性能對比結(jié)果.

Fig.11 Performance evaluation of hyperbolic embedding in real-world networks圖11 真實(shí)網(wǎng)絡(luò)雙曲嵌入的性能評估

5 結(jié)論及展望

本文介紹了現(xiàn)有的復(fù)雜網(wǎng)絡(luò)的雙曲幾何模型、嵌入方法以及應(yīng)用任務(wù).相對于其他網(wǎng)絡(luò)模型,雙曲幾何模型具有以下優(yōu)勢:(1)雙曲空間的指數(shù)擴(kuò)張使得空間容量大、易于表達(dá)樹狀層次結(jié)構(gòu)數(shù)據(jù);(2)雙曲幾何模型能夠近似網(wǎng)絡(luò)的樹狀分支,產(chǎn)生具有冪率度分布和自相似性的網(wǎng)絡(luò);(3)雙曲幾何空間中的三角不等式說明與某節(jié)點(diǎn)A相連的兩個節(jié)點(diǎn)B和C之間容易產(chǎn)生連接,可以解釋現(xiàn)實(shí)網(wǎng)絡(luò)中出現(xiàn)的強(qiáng)聚類效應(yīng);(4)復(fù)雜網(wǎng)絡(luò)的雙曲空間模型將網(wǎng)絡(luò)映射到雙曲幾何空間中,通過雙曲距離編碼節(jié)點(diǎn)間連接概率,使得模型參數(shù)可以反映節(jié)點(diǎn)的流行性和相似性;(5)復(fù)雜網(wǎng)絡(luò)的雙曲空間嵌入是一個網(wǎng)絡(luò)降維過程,便于后續(xù)應(yīng)用的高效計(jì)算,其嵌入坐標(biāo)可以作為機(jī)器學(xué)習(xí)算法輸入;(6)該模型提供了一種新的強(qiáng)有力的網(wǎng)絡(luò)可視化方法,社區(qū)結(jié)構(gòu)可以通過角區(qū)域集聚性來加以表征.

相對于歐氏空間的多項(xiàng)式擴(kuò)張,指數(shù)擴(kuò)張的雙曲空間具有更大的容量,更適合表達(dá)樹狀結(jié)構(gòu)、層次結(jié)構(gòu)的數(shù)據(jù).通過將數(shù)據(jù)嵌入到雙曲空間,可以近似捕獲其潛在的層次結(jié)構(gòu).徑坐標(biāo)與節(jié)點(diǎn)度高度相關(guān),可用于發(fā)現(xiàn)度相關(guān)結(jié)構(gòu)、網(wǎng)絡(luò)自相似結(jié)構(gòu)、快速比較和分析節(jié)點(diǎn)流行性、快速層級劃分等任務(wù);角坐標(biāo)間距離與節(jié)點(diǎn)相似性相關(guān),可用于快速社區(qū)劃分、相似節(jié)點(diǎn)融合、多層網(wǎng)絡(luò)關(guān)聯(lián)性及魯棒性分析、鏈路預(yù)測等任務(wù).雙曲幾何模型在具有較強(qiáng)可解釋性的同時,還能通過幾何工具和方法研究數(shù)據(jù)結(jié)構(gòu).其強(qiáng)大的層次結(jié)構(gòu)表達(dá)能力使得雙曲幾何的嵌入不僅能夠應(yīng)用于傳統(tǒng)的復(fù)雜網(wǎng)絡(luò)圖分析任務(wù),還為表征學(xué)習(xí)及其后續(xù)應(yīng)用開辟了新的方向.如圖12(a)所示:可以將雙曲空間嵌入應(yīng)用于監(jiān)督學(xué)習(xí),對象可以是具有層次結(jié)構(gòu)的文本符號數(shù)據(jù)或圖像數(shù)據(jù),研究其分類、層次表達(dá)等相關(guān)問題;類似地,對于無監(jiān)督學(xué)習(xí),可以構(gòu)建相似矩陣完成雙曲嵌入,如圖12(b)所示.

Fig.12 Example of machine learning combined with hyperbolic space圖12 雙曲空間與機(jī)器學(xué)習(xí)結(jié)合應(yīng)用示例

雖然復(fù)雜網(wǎng)絡(luò)的雙曲幾何模型已經(jīng)取得了豐富的研究成果,但是仍在以下幾個方面面臨著巨大挑戰(zhàn).

(1)動態(tài)變化網(wǎng)絡(luò)的生成.現(xiàn)實(shí)生活中,大量網(wǎng)絡(luò)的結(jié)構(gòu)具有動態(tài)性,現(xiàn)有的雙曲幾何模型主要是靜態(tài)的,雖然PSO 模型能夠刻畫一類網(wǎng)絡(luò)的動態(tài)生成過程,但仍存在許多現(xiàn)實(shí)網(wǎng)絡(luò)無法通過PSO 模型動態(tài)重現(xiàn).因此,如何在雙曲幾何模型的框架下模擬現(xiàn)實(shí)網(wǎng)絡(luò)的動態(tài)變化過程,是亟待解決的問題;

(2)多層次、多關(guān)系網(wǎng)絡(luò)的生成.在已有的研究中,復(fù)雜網(wǎng)絡(luò)的雙曲幾何模型成功地描述了從生物系統(tǒng)到信息系統(tǒng)和社會系統(tǒng)等各種復(fù)雜系統(tǒng)的形成過程,然而目前的研究對象大多是單一層次的網(wǎng)絡(luò),僅有少數(shù)多層網(wǎng)絡(luò)雙曲空間的生成模型[67],許多現(xiàn)實(shí)網(wǎng)絡(luò)具有多層次、多關(guān)系的網(wǎng)絡(luò)結(jié)構(gòu).這些網(wǎng)絡(luò)的不同層之間一般不是隨機(jī)連接的,如何挖掘?qū)娱g關(guān)聯(lián)關(guān)系,形成多層次、多關(guān)系網(wǎng)絡(luò)的雙曲幾何模型,是復(fù)雜網(wǎng)絡(luò)雙曲空間表征學(xué)習(xí)面臨的重要挑戰(zhàn);

(3)高維雙曲空間的嵌入.目前,基于生成模型的雙曲空間嵌入方法大多將復(fù)雜網(wǎng)絡(luò)嵌入到二維的雙曲空間中,現(xiàn)實(shí)數(shù)據(jù)中,實(shí)體之間的關(guān)系往往更加復(fù)雜,難以在二維雙曲空間中精確表示.提升雙曲空間的嵌入維度,可以增強(qiáng)模型的表達(dá)能力和適應(yīng)性,高維雙曲空間嵌入方法的研究,是未來的一個重要方向;

(4)更大規(guī)模、更高速率的嵌入方法.已有的雙曲空間嵌入方法僅僅能夠應(yīng)用于小規(guī)模網(wǎng)絡(luò),而實(shí)際場景中的網(wǎng)絡(luò)動輒上億節(jié)點(diǎn),因此,克服大規(guī)模網(wǎng)絡(luò)嵌入面臨的存儲、計(jì)算復(fù)雜度等困難,推廣雙曲空間嵌入方法到大規(guī)模網(wǎng)絡(luò)中,將開辟更加廣泛的應(yīng)用領(lǐng)域;

(5)與神經(jīng)網(wǎng)絡(luò)、機(jī)器學(xué)習(xí)相結(jié)合,將適合使用雙曲空間表示的數(shù)據(jù)、距離,轉(zhuǎn)移到雙曲空間中.雙曲空間相較于歐氏空間具有更強(qiáng)的樹狀結(jié)構(gòu)表達(dá)能力,如何調(diào)整神經(jīng)網(wǎng)絡(luò)、機(jī)器學(xué)習(xí)的模型,充分發(fā)掘雙曲空間的表達(dá)能力,是未來的一個開放性研究問題.