馮冰清,胡紹林,郭 棟,鐘曉歌,李佩鈺

1(航天器在軌故障診斷與維修重點(diǎn)實(shí)驗(yàn)室,陜西 西安 710043)2(四川大學(xué) 計(jì)算機(jī)學(xué)院,四川 成都 610065)

隨著信息技術(shù)的迅猛發(fā)展,網(wǎng)絡(luò)數(shù)據(jù)的種類和數(shù)量巨幅增長(zhǎng),從社交網(wǎng)絡(luò)到科研合作者網(wǎng)絡(luò),從電力網(wǎng)絡(luò)到城市交通網(wǎng)絡(luò),從生物體中的大腦到各種新陳代謝網(wǎng)絡(luò),人們已經(jīng)生活在一個(gè)充滿著各種各樣的復(fù)雜網(wǎng)絡(luò)世界中[1].對(duì)復(fù)雜網(wǎng)絡(luò)的研究通常需要對(duì)其進(jìn)行建模和簡(jiǎn)化,傳統(tǒng)復(fù)雜網(wǎng)絡(luò)研究多將復(fù)雜系統(tǒng)建模為靜態(tài)網(wǎng)絡(luò),而現(xiàn)實(shí)中幾乎所有的復(fù)雜系統(tǒng)都是隨時(shí)間不斷變化的.以社交網(wǎng)站Facebook[2]為例,從2004年上線到現(xiàn)在,網(wǎng)站每月的活躍用戶數(shù)超過20億,已經(jīng)發(fā)展成為全球最大的社交網(wǎng)站之一,類似的還有g(shù)oogle+[3],Twitter[4].事實(shí)上,不僅僅是社交網(wǎng)站,還有科學(xué)家合作網(wǎng)絡(luò)、城市交通網(wǎng)絡(luò)、公司郵件網(wǎng)絡(luò)、通信網(wǎng)絡(luò)等,這些復(fù)雜網(wǎng)絡(luò)的顯著特征是網(wǎng)絡(luò)的結(jié)構(gòu)隨時(shí)間不斷地變化,而這些時(shí)序動(dòng)態(tài)特征對(duì)理解系統(tǒng)或網(wǎng)絡(luò)中的行為至關(guān)重要.這些不斷變化的網(wǎng)絡(luò)就是動(dòng)態(tài)復(fù)雜網(wǎng)絡(luò),簡(jiǎn)稱動(dòng)態(tài)網(wǎng)絡(luò)[5].對(duì)動(dòng)態(tài)網(wǎng)絡(luò)時(shí)序模式的深入理解,有助于分析網(wǎng)絡(luò)結(jié)構(gòu)、理解網(wǎng)絡(luò)特性、發(fā)現(xiàn)網(wǎng)絡(luò)中潛在的信息及演化規(guī)律,因此,對(duì)動(dòng)態(tài)網(wǎng)絡(luò)建模及分析得到了廣泛關(guān)注.

信息網(wǎng)絡(luò)(information network)[6]是對(duì)現(xiàn)實(shí)空間中海量、多維、復(fù)雜結(jié)構(gòu)和問題更具一般性的抽象[7],可以有效抽象出復(fù)雜系統(tǒng)中有價(jià)值的特征與潛在規(guī)律,從而為系統(tǒng)化地分析現(xiàn)實(shí)中的復(fù)雜網(wǎng)絡(luò)提供高效的研究和探索的方法.信息網(wǎng)絡(luò)一般都有動(dòng)態(tài)的演化過程,新節(jié)點(diǎn)會(huì)持續(xù)地加入網(wǎng)絡(luò),一些節(jié)點(diǎn)也會(huì)在中途消失,節(jié)點(diǎn)間連接的強(qiáng)度也在不斷變化,信息網(wǎng)絡(luò)中網(wǎng)絡(luò)結(jié)構(gòu)隨之處于不斷演化的過程中[8],這里統(tǒng)稱為動(dòng)態(tài)信息網(wǎng)絡(luò).動(dòng)態(tài)信息網(wǎng)絡(luò)的演化過程具有時(shí)序、復(fù)雜、多變的特點(diǎn),蘊(yùn)含著豐富的潛在信息和商業(yè)價(jià)值.動(dòng)態(tài)網(wǎng)絡(luò)的結(jié)構(gòu)預(yù)測(cè)是網(wǎng)絡(luò)演化中十分重要的問題,它旨在利用歷史網(wǎng)絡(luò)信息預(yù)測(cè)未來時(shí)刻節(jié)點(diǎn)的拓?fù)浣Y(jié)構(gòu),幫助人們提前進(jìn)行預(yù)警和決策.

動(dòng)態(tài)信息網(wǎng)絡(luò)是當(dāng)前復(fù)雜網(wǎng)絡(luò)研究領(lǐng)域中極具挑戰(zhàn)的新方向,由于網(wǎng)絡(luò)結(jié)構(gòu)本身比較復(fù)雜,難以表示和量化,動(dòng)態(tài)網(wǎng)絡(luò)時(shí)序、多變的演化過程更增加了分析的難度.基于動(dòng)態(tài)信息網(wǎng)絡(luò)的廣泛應(yīng)用前景及角色(role)發(fā)現(xiàn)在動(dòng)態(tài)網(wǎng)絡(luò)中有限的研究現(xiàn)狀,本文致力于研究動(dòng)態(tài)信息網(wǎng)絡(luò)中基于角色發(fā)現(xiàn)的結(jié)構(gòu)預(yù)測(cè)問題,主要包括針對(duì)網(wǎng)絡(luò)結(jié)構(gòu)表示的復(fù)雜性以及網(wǎng)絡(luò)演化時(shí)序多變的挑戰(zhàn),將靜態(tài)網(wǎng)絡(luò)中用角色來量化網(wǎng)絡(luò)結(jié)構(gòu)的方法擴(kuò)展至動(dòng)態(tài)網(wǎng)絡(luò),以角色發(fā)現(xiàn)為基礎(chǔ),對(duì)動(dòng)態(tài)網(wǎng)絡(luò)結(jié)構(gòu)預(yù)測(cè)進(jìn)行探索性研究.主要貢獻(xiàn)如下.

(1) 提出動(dòng)態(tài)網(wǎng)絡(luò)角色發(fā)現(xiàn)模型

使用角色來表示動(dòng)態(tài)網(wǎng)絡(luò)的結(jié)構(gòu),將靜態(tài)網(wǎng)絡(luò)中基于遞歸地提取特征的角色發(fā)現(xiàn)方法擴(kuò)展至動(dòng)態(tài)網(wǎng)絡(luò),按照時(shí)間序列對(duì)每個(gè)網(wǎng)絡(luò)快照進(jìn)行特征提取,然后為每個(gè)快照學(xué)習(xí)節(jié)點(diǎn)的行為角色,提出動(dòng)態(tài)網(wǎng)絡(luò)的角色發(fā)現(xiàn)模型.同時(shí)給出兩種角色解釋的方法,并在不同規(guī)模的真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn),驗(yàn)證本文模型的有效性和可解釋性.

(2) 提出基于潛在角色的動(dòng)態(tài)網(wǎng)絡(luò)結(jié)構(gòu)預(yù)測(cè)方法LR-DNSP

網(wǎng)絡(luò)結(jié)構(gòu)的動(dòng)態(tài)預(yù)測(cè)是動(dòng)態(tài)網(wǎng)絡(luò)演化分析的一個(gè)重要任務(wù).將動(dòng)態(tài)網(wǎng)絡(luò)結(jié)構(gòu)預(yù)測(cè)轉(zhuǎn)換為可以表示結(jié)構(gòu)特征的角色預(yù)測(cè)問題,以歷史網(wǎng)絡(luò)角色分布矩陣作為訓(xùn)練數(shù)據(jù)構(gòu)建模型,通過向量自回歸的方法預(yù)測(cè)未來時(shí)刻網(wǎng)絡(luò)可能的角色分布情況,提出了基于潛在角色的動(dòng)態(tài)網(wǎng)絡(luò)結(jié)構(gòu)預(yù)測(cè)方法 LR-DNSP(latent role based dynamic network structure prediction).該方法克服了已有基于轉(zhuǎn)移矩陣方法未能充分利用歷史信息的不足,并且考慮了多個(gè)預(yù)測(cè)目標(biāo)之間可能存在的相互關(guān)系.實(shí)驗(yàn)結(jié)果表明,本文提出的LR-DNSP方法具有更準(zhǔn)確的預(yù)測(cè)效果.

1 相關(guān)工作

在動(dòng)態(tài)網(wǎng)絡(luò)的相關(guān)研究工作中,節(jié)點(diǎn)中心性分析、節(jié)點(diǎn)影響力分析、鏈接預(yù)測(cè)、異常發(fā)現(xiàn)以及社團(tuán)發(fā)現(xiàn)、社團(tuán)演化等近年來得到了較多的關(guān)注,而相對(duì)而言對(duì)節(jié)點(diǎn)結(jié)構(gòu)行為分析關(guān)注較少.相比之下,本文更關(guān)注如何發(fā)現(xiàn)網(wǎng)絡(luò)中節(jié)點(diǎn)的行為模式,通過網(wǎng)絡(luò)隨時(shí)間的變化來捕獲節(jié)點(diǎn)行為的模型,并建模這些模式隨時(shí)間的變化.針對(duì)網(wǎng)絡(luò)結(jié)構(gòu)的表示問題,Henderson等人[9]在 KDD2012上首次提出用潛在的角色來刻畫節(jié)點(diǎn)的結(jié)構(gòu)行為.角色代表網(wǎng)絡(luò)結(jié)構(gòu)的某種類型,結(jié)構(gòu)類型相似的節(jié)點(diǎn)屬于同一種角色,如中心節(jié)點(diǎn)、橋梁節(jié)點(diǎn)、邊緣節(jié)點(diǎn)等.角色發(fā)現(xiàn)是靜態(tài)網(wǎng)絡(luò)結(jié)構(gòu)的一種有效量化方法,可以將復(fù)雜的網(wǎng)絡(luò)結(jié)構(gòu)表示為相對(duì)簡(jiǎn)單的角色.節(jié)點(diǎn)角色分析試圖將在網(wǎng)絡(luò)中有著相同地位或發(fā)揮相同角色作用或有著相同功能的節(jié)點(diǎn)歸為一類.它與社團(tuán)發(fā)現(xiàn)有著本質(zhì)的區(qū)別:社團(tuán)發(fā)現(xiàn)是根據(jù)節(jié)點(diǎn)連接的緊密程度進(jìn)行聚類,而角色發(fā)現(xiàn)主要依賴于網(wǎng)絡(luò)中節(jié)點(diǎn)的拓?fù)浣Y(jié)構(gòu)特征.

Henderson等人在角色概念的基礎(chǔ)上提出了基于特征的角色發(fā)現(xiàn)方法RolX(role extraction),通過無監(jiān)督學(xué)習(xí),從網(wǎng)絡(luò)中自動(dòng)提取結(jié)構(gòu)角色,進(jìn)一步實(shí)現(xiàn)網(wǎng)絡(luò)挖掘任務(wù)[9].在已有的無監(jiān)督角色發(fā)現(xiàn)的研究基礎(chǔ)上,Sean Gilpin等人[10]提出了基于交替最小二乘的有監(jiān)督角色發(fā)現(xiàn)方法,主要解決了數(shù)據(jù)集稀疏性、多樣性和角色交替性問題等.Rossi等人以角色為基礎(chǔ)進(jìn)行了一系列動(dòng)態(tài)網(wǎng)絡(luò)演化分析相關(guān)的研究[11-13],也是本文研究工作的基礎(chǔ).文獻(xiàn)[11]提出一種基于自學(xué)習(xí)方法挖掘動(dòng)態(tài)網(wǎng)絡(luò)角色的混合模型,該模型以基于特征的角色發(fā)現(xiàn)方法為基礎(chǔ),將動(dòng)態(tài)網(wǎng)絡(luò)視為多個(gè)靜態(tài)網(wǎng)絡(luò)的序列,在離散的時(shí)間點(diǎn)上進(jìn)行角色發(fā)現(xiàn),比較不同時(shí)刻的角色分布情況來分析網(wǎng)絡(luò)角色的動(dòng)態(tài)變化趨勢(shì);文獻(xiàn)[13]進(jìn)一步將上述模型進(jìn)行擴(kuò)展,應(yīng)用模型進(jìn)行未來時(shí)刻網(wǎng)絡(luò)角色的預(yù)測(cè),其思想是將動(dòng)態(tài)網(wǎng)絡(luò)的多種角色視為網(wǎng)絡(luò)的多個(gè)狀態(tài),通過計(jì)算網(wǎng)絡(luò)在相鄰時(shí)刻的狀態(tài)轉(zhuǎn)移矩陣來進(jìn)行角色演化的分析與預(yù)測(cè),但是由于該轉(zhuǎn)移矩陣模型只通過相鄰兩個(gè)時(shí)刻的網(wǎng)絡(luò)數(shù)據(jù)得到,未能充分利用歷史時(shí)刻的網(wǎng)絡(luò)數(shù)據(jù),因此預(yù)測(cè)效果有待改進(jìn),該方法將作為本文角色預(yù)測(cè)問題的對(duì)比方法之一.

近年來,角色發(fā)現(xiàn)正在被其他領(lǐng)域廣泛探索,如在線社交網(wǎng)絡(luò)[14]、科技網(wǎng)絡(luò)[15]、生物網(wǎng)絡(luò)[16,17]、網(wǎng)絡(luò)圖[18]等.角色發(fā)現(xiàn)在網(wǎng)絡(luò)挖掘的探索分析中,從傳統(tǒng)的節(jié)點(diǎn)分類、異常檢測(cè)、預(yù)測(cè)問題到結(jié)構(gòu)相似性度量、圖相似性研究、網(wǎng)絡(luò)可視化、遷移學(xué)習(xí)等,逐步發(fā)揮著重要作用.McDowell等人[19]使用角色作為特征進(jìn)行分類;Rossi等人[15]對(duì)給定的兩個(gè)圖,通過提取各自的特征和角色進(jìn)行圖相似研究;Henderson等人[9]通過對(duì)給定網(wǎng)絡(luò)的角色學(xué)習(xí),使用已有的知識(shí)在另一網(wǎng)絡(luò)學(xué)習(xí)同樣的角色集合,以提高分類的準(zhǔn)確性.角色發(fā)現(xiàn)也可以被推廣到更多實(shí)際的應(yīng)用中,例如,角色可用于檢測(cè) IP網(wǎng)絡(luò)中的異常,可以基于用戶在網(wǎng)絡(luò)中的角色來定制廣告推送.在網(wǎng)絡(luò)挖掘和實(shí)際應(yīng)用中,角色正在成為一種重要的潛在分析視角.但相比于社團(tuán)發(fā)現(xiàn)、社團(tuán)演化等,角色發(fā)現(xiàn)僅受到了有限的關(guān)注.

2 動(dòng)態(tài)網(wǎng)絡(luò)的角色發(fā)現(xiàn)與角色解釋

拓?fù)浣Y(jié)構(gòu)是復(fù)雜網(wǎng)絡(luò)的研究基礎(chǔ),靜態(tài)網(wǎng)絡(luò)中已有的拓?fù)渲笜?biāo)包括度、距離、直徑、密度、聚集系數(shù)、介數(shù)中心性、參與三角形數(shù)量、模塊性等,涉及網(wǎng)絡(luò)不同層面的度量,為進(jìn)一步分析動(dòng)態(tài)網(wǎng)絡(luò)的結(jié)構(gòu)特征提供了理論依據(jù),也是捕獲角色的基礎(chǔ)[20].靜態(tài)網(wǎng)絡(luò)中的角色發(fā)現(xiàn)是一種對(duì)網(wǎng)絡(luò)結(jié)構(gòu)的有效量化方法,本文旨在從節(jié)點(diǎn)角色的角度描述其在網(wǎng)絡(luò)中的結(jié)構(gòu)特征,圖1中用不同顏色區(qū)分了網(wǎng)絡(luò)中的不同角色.使用角色來量化節(jié)點(diǎn)的結(jié)構(gòu),可以有效化簡(jiǎn)網(wǎng)絡(luò)結(jié)構(gòu)分析的難度.

Fig.1 Role discovery[9]圖1 角色發(fā)現(xiàn)[9]

網(wǎng)絡(luò)中的角色目前還沒有統(tǒng)一的定義,可以概括地認(rèn)為角色是節(jié)點(diǎn)在網(wǎng)絡(luò)中所表現(xiàn)出的結(jié)構(gòu)行為,來刻畫節(jié)點(diǎn)的某種重要程度[21].而角色發(fā)現(xiàn)則是通過量化節(jié)點(diǎn)結(jié)構(gòu),判定節(jié)點(diǎn)的結(jié)構(gòu)角色.為解決動(dòng)態(tài)網(wǎng)絡(luò)結(jié)構(gòu)演化分析的問題,本文首先對(duì)動(dòng)態(tài)網(wǎng)絡(luò)進(jìn)行角色發(fā)現(xiàn).

2.1 動(dòng)態(tài)網(wǎng)絡(luò)的角色發(fā)現(xiàn)

進(jìn)行動(dòng)態(tài)網(wǎng)絡(luò)的角色發(fā)現(xiàn)之前,首先要構(gòu)建動(dòng)態(tài)網(wǎng)絡(luò).動(dòng)態(tài)網(wǎng)絡(luò)的定義如下.

定義1(動(dòng)態(tài)網(wǎng)絡(luò)).D=〈N,E〉表示一個(gè)動(dòng)態(tài)網(wǎng)絡(luò),N=〈N1,N2,…,NT〉為節(jié)點(diǎn)集合,E=〈E1,E2,…,ET〉為邊集合.將D看做一個(gè)時(shí)間有序的子圖序列D=〈S1,S2,…,ST〉,其中,ST=〈NT,ET〉是動(dòng)態(tài)網(wǎng)絡(luò)D在t時(shí)刻的子圖快照,Nt為St的節(jié)點(diǎn)集合,Et為St的邊集合,T為動(dòng)態(tài)網(wǎng)絡(luò)長(zhǎng)度.本文研究網(wǎng)絡(luò)的結(jié)構(gòu)演化,故只考慮無向網(wǎng)絡(luò).

研究動(dòng)態(tài)網(wǎng)絡(luò)的角色發(fā)現(xiàn),首先要對(duì)網(wǎng)絡(luò)進(jìn)行特征提取,得到高維特征矩陣,然后對(duì)特征矩陣通過非負(fù)矩陣分解進(jìn)行角色發(fā)現(xiàn),在角色發(fā)現(xiàn)的過程中要確定分解的最優(yōu)r值,最后對(duì)得到的角色模型進(jìn)行解釋.將動(dòng)態(tài)網(wǎng)絡(luò)表示為有序的子圖序列后,對(duì)每個(gè)時(shí)刻的網(wǎng)絡(luò)快照分別進(jìn)行角色發(fā)現(xiàn),即將每個(gè)子網(wǎng)絡(luò)都轉(zhuǎn)化為節(jié)點(diǎn)的角色信息.本文使用 KDD2012的RloX方法[9]進(jìn)行角色發(fā)現(xiàn).相比其他傳統(tǒng)方法,RolX更適合大規(guī)模網(wǎng)絡(luò)的角色發(fā)現(xiàn),它不僅能發(fā)現(xiàn)網(wǎng)絡(luò)中的角色,還可以得到節(jié)點(diǎn)在各角色上的概率取值.該方法通過以下兩步過程完成.

(1) 特征提取

特征提取過程采用 ReFex[22]的迭代特征產(chǎn)生方法,為每個(gè)節(jié)點(diǎn)提取基本特征和遞歸特征,基本特征指節(jié)點(diǎn)局部結(jié)構(gòu)的特征,即在與一階鄰居所形成的自網(wǎng)絡(luò)中所表現(xiàn)出的特征,如節(jié)點(diǎn)的度、加權(quán)度、自網(wǎng)絡(luò)包含的邊數(shù)等.得到節(jié)點(diǎn)的基本特征后,使用聚集函數(shù)遞歸地對(duì)其鄰居節(jié)點(diǎn)的基本特征進(jìn)行聚集計(jì)算得到遞歸特征[22].以圖2所示網(wǎng)絡(luò)為例,虛線內(nèi)表示n1的自網(wǎng)絡(luò),選取 3個(gè)基本特征:度、自網(wǎng)絡(luò)包含的邊數(shù)、參與三角形的個(gè)數(shù),使用求和以及求平均兩種聚集函數(shù)來產(chǎn)生遞歸特征.得到n1的基本特征的向量為〈f1,f2,f3〉=〈6,11,5〉.接著計(jì)算遞歸特征,直到?jīng)]有新特征產(chǎn)生終止,便可將節(jié)點(diǎn)n1表示為一個(gè)特征取值向量f=〈f1,f2,f3,…〉.

Fig.2 An example of role discovery圖2 角色發(fā)現(xiàn)的示例網(wǎng)絡(luò)

對(duì)每個(gè)節(jié)點(diǎn)分別進(jìn)行特征提取,可以得到一個(gè)節(jié)點(diǎn)的特征取值向量.因此,可以將網(wǎng)絡(luò)快照St轉(zhuǎn)化為一個(gè)特征空間,記為節(jié)點(diǎn)的特征Vt∈?N×ft.

定義2(節(jié)點(diǎn)-特征矩陣序列V=〈V1,V2,…,VT〉. 給定動(dòng)態(tài)網(wǎng)絡(luò)子圖序列D=〈S1,S2,…,ST〉,對(duì)St進(jìn)行特征提取,得到節(jié)點(diǎn)的特征矩陣Vt∈?N×ft,其中,N為網(wǎng)絡(luò)的節(jié)點(diǎn)個(gè)數(shù),ft表示t時(shí)刻得到的特征個(gè)數(shù).對(duì)每個(gè)網(wǎng)絡(luò)快照D=〈S1,S2,…,ST〉分別進(jìn)行特征提取,得到節(jié)點(diǎn)-特征矩陣序列V=〈V1,V2,…,VT〉.

(2) 角色發(fā)現(xiàn)

通過對(duì)節(jié)點(diǎn)的特征矩陣降維分解,進(jìn)一步進(jìn)行角色發(fā)現(xiàn),降維后得到對(duì)節(jié)點(diǎn)特征的概括就是潛在的角色.基于非負(fù)矩陣分解實(shí)現(xiàn)上的簡(jiǎn)便性、分解形式和分解結(jié)果上的可解釋性,本文使用非負(fù)矩陣分解方法對(duì)提取到的特征矩陣進(jìn)行降維.對(duì)特征矩陣,給定一個(gè)正整數(shù)r

角色-特征矩陣F∈?r×ft表示了每個(gè)角色在提取到的特征值上的貢獻(xiàn),學(xué)習(xí)到F之后,進(jìn)一步對(duì)整個(gè)動(dòng)態(tài)網(wǎng)絡(luò)進(jìn)行角色發(fā)現(xiàn),對(duì)每個(gè)子圖快照D=〈S1,S2,…,ST〉在特征提取后,根據(jù)得到節(jié)點(diǎn)的特征序列V=〈V1,V2,…,VT〉和F,分別進(jìn)行NMF過程得到全部節(jié)點(diǎn)的角色序列G=〈G1,G2,…,GT〉.

根據(jù)上面非負(fù)矩陣分解得到的結(jié)果,Gt是一個(gè)N行r列的矩陣,每列對(duì)應(yīng)一種角色,Gt的每個(gè)元素gt(i,j)表示節(jié)點(diǎn)i屬于角色j的概率.進(jìn)行角色發(fā)現(xiàn)涉及到需要確定角色的個(gè)數(shù),本文使用最小描述長(zhǎng)度(minimum description length)準(zhǔn)則[23]選定角色個(gè)數(shù)r,使得節(jié)點(diǎn)特征矩陣可以得到最佳的壓縮.

算法1.角色個(gè)數(shù)選取算法.

輸入:原始節(jié)點(diǎn)-特征矩陣V∈?n×f;

輸出:角色個(gè)數(shù):r.

用上述方法對(duì)動(dòng)態(tài)網(wǎng)絡(luò)進(jìn)行角色建模,得到角色序列G=〈G1,G2,…,GT〉,Gt的每一行表示t時(shí)刻該節(jié)點(diǎn)在r個(gè)角色上的取值分布.但與此同時(shí),也暴露出對(duì)得到的結(jié)果難以直觀理解的問題,由矩陣分解方法得到的是特征空間中r個(gè)潛在的角色,雖然能得到網(wǎng)絡(luò)中角色的個(gè)數(shù),但這些角色并不直觀,無法獲知每種角色具體表示何種結(jié)構(gòu).

2.2 角色解釋

為了對(duì)得到的角色有直觀的認(rèn)識(shí),下面介紹如何對(duì)模型得到的角色進(jìn)行解釋.在得到角色序列G=〈G1,G2,…,GT〉后,節(jié)點(diǎn)結(jié)構(gòu)被表示為在角色上的概率取值,可否利用傳統(tǒng)的度量(如度、介數(shù)、離心率等)和鄰接節(jié)點(diǎn)的角色分布對(duì)角色進(jìn)行量化和解釋?為了得到對(duì)角色的感官認(rèn)識(shí),本文給出兩種角色解釋方法:一種是基于節(jié)點(diǎn)自身度量屬性的方法NodeSense,另一種是基于鄰居節(jié)點(diǎn)分布的方法NeighborSense.

基于以上思路,對(duì)給定動(dòng)態(tài)網(wǎng)絡(luò)的子圖快照St與角色矩陣Gt,為每個(gè)節(jié)點(diǎn)計(jì)算一系列度量屬性,本文選取了8種傳統(tǒng)的度量屬性:度、加權(quán)度、介數(shù)、特征向量中心度、緊密中心度、聚集系數(shù)、PageRank、離心率,計(jì)算可得到t時(shí)刻節(jié)點(diǎn)的度量矩陣Mt∈?N×m,其中,m=8.為得到角色與度量之間的量化關(guān)系,NodeSense計(jì)算一個(gè)新的非負(fù)矩陣Pt,使得GtPt≈Mt,其中,Pt∈?r×m.Pt的行對(duì)應(yīng)r個(gè)角色,列對(duì)應(yīng)m個(gè)度量,Pt的每一行則表示該角色在各個(gè)度量上的概率取值,即角色在各個(gè)度量屬性的貢獻(xiàn).

NeighborSense方法的思路類似于NodeSense:首先,對(duì)t時(shí)刻子圖快照St計(jì)算每個(gè)節(jié)點(diǎn)鄰居的角色分布矩陣Nt∈?n×r,Nt的行表示節(jié)點(diǎn),列表示角色,Nt(i,j)表示t時(shí)刻節(jié)點(diǎn)i的所有鄰居節(jié)點(diǎn)在角色j上的分布統(tǒng)計(jì);接著,NeighborSense計(jì)算一個(gè)非負(fù)矩陣Qt,使得GtQt≈Nt,其中,Qt∈?r×r表示角色與角色之間的關(guān)系.比如,有些節(jié)點(diǎn)更傾向與自己相同角色的節(jié)點(diǎn)相連,則可以認(rèn)為這類角色是同質(zhì)性的;而另一部分節(jié)點(diǎn)可能與自己相異的角色相連,這類角色可認(rèn)為是異質(zhì)性的.具體分析結(jié)果將在實(shí)驗(yàn)部分呈現(xiàn).

3 動(dòng)態(tài)網(wǎng)絡(luò)角色預(yù)測(cè)

動(dòng)態(tài)網(wǎng)絡(luò)的結(jié)構(gòu)預(yù)測(cè)是網(wǎng)絡(luò)演化分析的重要問題,但由于動(dòng)態(tài)網(wǎng)絡(luò)演化過程本身復(fù)雜多變,加上網(wǎng)絡(luò)規(guī)模的急劇增長(zhǎng),該問題還未得到很好的解決.網(wǎng)絡(luò)結(jié)構(gòu)本身難以量化,直接預(yù)測(cè)網(wǎng)絡(luò)結(jié)構(gòu)比較困難.本文的動(dòng)態(tài)網(wǎng)絡(luò)角色模型為網(wǎng)絡(luò)結(jié)構(gòu)預(yù)測(cè)問題提供了一個(gè)新的思路,即用角色來建模動(dòng)態(tài)網(wǎng)絡(luò)結(jié)構(gòu),動(dòng)態(tài)網(wǎng)絡(luò)結(jié)構(gòu)表示為節(jié)點(diǎn)的角色分布序列,將網(wǎng)絡(luò)結(jié)構(gòu)預(yù)測(cè)問題轉(zhuǎn)化為角色分布的預(yù)測(cè).這樣,很大程度上降低了問題的求解難度(如圖3所示).

Fig.3 Role prediction of dynamic networks圖3 動(dòng)態(tài)網(wǎng)絡(luò)角色預(yù)測(cè)

3.1 問題定義

本文將動(dòng)態(tài)網(wǎng)絡(luò)結(jié)構(gòu)預(yù)測(cè)轉(zhuǎn)換為可以表示結(jié)構(gòu)特征的角色預(yù)測(cè)問題,即:根據(jù)歷史時(shí)刻網(wǎng)絡(luò)的角色分布,預(yù)測(cè)未來時(shí)刻網(wǎng)絡(luò)可能的角色分布情況.形式化表示為:給定動(dòng)態(tài)網(wǎng)絡(luò)D=〈S1,S2,…,ST〉,得到動(dòng)態(tài)網(wǎng)絡(luò)角色模型G=〈G1,G2,…,GT〉,Gi為i時(shí)刻節(jié)點(diǎn)角色矩陣,角色預(yù)測(cè)就是要得到t+1時(shí)刻網(wǎng)絡(luò)的節(jié)點(diǎn)角色矩陣.

對(duì)整個(gè)網(wǎng)絡(luò),角色預(yù)測(cè)就是要得到t+1時(shí)刻網(wǎng)絡(luò)的節(jié)點(diǎn)角色矩陣,對(duì)每個(gè)節(jié)點(diǎn),就是要預(yù)測(cè)節(jié)點(diǎn)n在t+1時(shí)刻的角色分布向量gt+1(的第n行).將網(wǎng)絡(luò)結(jié)構(gòu)的預(yù)測(cè)問題劃分成子問題,對(duì)每個(gè)節(jié)點(diǎn)而言,預(yù)測(cè)目標(biāo)是一個(gè)向量,且節(jié)點(diǎn)的在角色向量的分布上并非獨(dú)立不相關(guān)的.

向量自回歸(VAR)[24]基于數(shù)據(jù)的統(tǒng)計(jì)性質(zhì)建立模型,適合處理多個(gè)變量分析與預(yù)測(cè).本文借鑒 VAR方法的思路,提出了基于潛在角色的動(dòng)態(tài)網(wǎng)絡(luò)結(jié)構(gòu)預(yù)測(cè)方法 LR-DNSP(latent role based dynamic network structure prediction).LR-DNSP模型可以充分考慮前后向量序列之間的關(guān)系和角色之間的相互影響,通過向量自回歸的方法,由歷史時(shí)刻網(wǎng)絡(luò)數(shù)據(jù)得到訓(xùn)練數(shù)據(jù)構(gòu)建潛在角色預(yù)測(cè)模型,以下一時(shí)刻網(wǎng)絡(luò)角色的分布情況作為預(yù)測(cè)目標(biāo).LR-DNSP不僅利用多個(gè)歷史時(shí)刻的屬性信息還考慮了預(yù)測(cè)目標(biāo)之間的相關(guān)性.

3.2 預(yù)測(cè)模型

本文預(yù)測(cè)模型的框架如圖4所示.

Fig.4 Model framework of LR-DNSP圖4 LR-DNSP模型框架

對(duì)所有的網(wǎng)絡(luò)快照計(jì)算其特征矩陣,并進(jìn)行分解得到角色矩陣,用一部分歷史數(shù)據(jù)來訓(xùn)練模型,剩下的一部分?jǐn)?shù)據(jù)用來預(yù)測(cè).

本文預(yù)測(cè)目標(biāo)為節(jié)點(diǎn)在下一時(shí)刻的角色分布向量,記為y=[y1,…,ym].在本文后續(xù)實(shí)驗(yàn)部分的 3個(gè)數(shù)據(jù)集通過計(jì)算驗(yàn)證,當(dāng)角色個(gè)數(shù)r取4時(shí)模型代價(jià)最小,因此此處m=4.為了后續(xù)實(shí)驗(yàn)比對(duì),本文先將預(yù)測(cè)變量視為多個(gè)獨(dú)立的單變量,為每個(gè)yi通過自回歸方法分別建立一個(gè)LR-DNSP(AR)模型,如圖5虛線所選每列所示.對(duì)網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的角色分布進(jìn)行預(yù)測(cè),將所有預(yù)測(cè)結(jié)果合并起來作為最終角色矩陣.

Fig.5 Prediction model of LR-DNSP (AR)圖5 LR-DNSP(AR)預(yù)測(cè)模型

為了實(shí)驗(yàn)對(duì)比中的公正性,以上LR-DNSP(AR)模型分別選取預(yù)測(cè)結(jié)果最佳的階數(shù)p.

考慮到多個(gè)預(yù)測(cè)目標(biāo)之間存在的相互影響,在上述采用自回歸方法模型的基礎(chǔ)上,本文將預(yù)測(cè)目標(biāo)視為向量,提出解決動(dòng)態(tài)網(wǎng)絡(luò)角色預(yù)測(cè)問題的向量自回歸模型,對(duì)每個(gè)節(jié)點(diǎn)直接預(yù)測(cè)t+1時(shí)刻的角色分布向量(如圖6所示).

Fig.6 Prediction model of LR-DNSP圖6 LR-DNSP預(yù)測(cè)模型

對(duì)節(jié)點(diǎn)n用最近的p個(gè)歷史時(shí)刻的角色向量預(yù)測(cè)模型如下:

其中,p是向量自回歸模型的階數(shù);為角色矩陣第n行在t+1時(shí)刻的預(yù)測(cè)值;α為(m×1)常數(shù)項(xiàng)向量,本文模型中,m=4;Φj是自回歸系數(shù)的一個(gè)矩陣,j=1,2,…,p;εt為角色在時(shí)間t+1的分布誤差,服從均值為零的高斯分布.

模型參數(shù)可以采用最小二乘估計(jì),也可采用最大似然估計(jì).本文模型中的參數(shù)學(xué)習(xí)通過解決以下問題的最優(yōu)解:

LR-DNSP模型的訓(xùn)練過程算法可抽象如下.

算法2.LR-DNSP模型訓(xùn)練過程.

輸入:網(wǎng)絡(luò)快照D=〈S1,S2,…,ST〉和對(duì)應(yīng)的節(jié)點(diǎn)角色序列G=〈G1,G2,…,GT〉;

輸出:向量自回歸模型的參數(shù){φ1,φ2,…,φp}和α;向量自回歸模型的介數(shù):p.

算法的第1行～第3行是從各個(gè)時(shí)刻的角色矩陣中提取節(jié)點(diǎn)的角色序列,第4行根據(jù)最小化最終預(yù)測(cè)誤差來確定模型回歸的階數(shù)p,算法的第5行使用梯度下降的方法通過求解公式(4).

算法3.角色分布預(yù)測(cè)算法.

輸入:最近p個(gè)時(shí)刻節(jié)點(diǎn)角色序列:{Gt-p+1,…,Gt-1,Gt};

輸出:t+1時(shí)刻節(jié)點(diǎn)的角色分布矩陣:.

4 實(shí)驗(yàn)及分析

4.1 數(shù)據(jù)集

本文選取 3個(gè)具有代表意義的動(dòng)態(tài)網(wǎng)絡(luò)數(shù)據(jù)集:Enron(http://konect.uni-koblenz.de/networks/enron)、Facebook(http://konect.uni-koblenz.de/networks/facebook-wosn-wall)、DBLP(http://dblp.uni-trier.de/xml/),每個(gè)數(shù)據(jù)集的規(guī)模各不相同,均來自公開網(wǎng)站.表1列出了3個(gè)數(shù)據(jù)集的詳細(xì)信息,“*”表示平均值.

Table 1 Datasets details表1 數(shù)據(jù)集詳細(xì)信息

為簡(jiǎn)化起見,本文假設(shè)網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)目保持不變,因而只考慮在研究時(shí)間段內(nèi)一直出現(xiàn)的節(jié)點(diǎn).對(duì)以上 3個(gè)網(wǎng)絡(luò)均建模為無向加權(quán)網(wǎng)絡(luò),采用權(quán)值衰減的方法計(jì)算邊的權(quán)重.節(jié)點(diǎn)a和節(jié)點(diǎn)b之間的邊在t時(shí)刻的權(quán)值為

其中:wi是ti時(shí)刻節(jié)點(diǎn)a和節(jié)點(diǎn)b之間事件的權(quán)重(如節(jié)點(diǎn)間發(fā)送電子郵件數(shù)、合作發(fā)表論文數(shù)等),相應(yīng)的鄰接矩陣序列為A=〈A1,A2,…,Ar〉;本文實(shí)驗(yàn)中,取λ=1.

4.2 對(duì)比方法

本文使用4種方法作為對(duì)比.

(1) PRE(baseline):使用前一時(shí)刻網(wǎng)絡(luò)的角色分布作為要預(yù)測(cè)的下一時(shí)刻的網(wǎng)絡(luò)角色矩陣,即用時(shí)刻t的網(wǎng)絡(luò)角色分布矩陣作為時(shí)刻t+1時(shí)所求得表示網(wǎng)絡(luò)結(jié)構(gòu)的角色矩陣,即:;

(2) TM(transition model):此模型是相關(guān)工作中所介紹WSDM2014的轉(zhuǎn)移矩陣方法[13],主旨思想是計(jì)算t-1和t時(shí)刻的角色矩陣Gt-1和Gt,使用非負(fù)矩陣分解得到角色轉(zhuǎn)移矩陣T:Gs(t-1)T≈Gs(t),由Gt和T相乘得到t+1時(shí)刻的目標(biāo)角色矩陣;

(3) AR:將角色分布向量(y=[y1,…,ym])視為多個(gè)獨(dú)立的單變量,為每個(gè)yi分別建立一個(gè)自回歸(AR)模型,將每個(gè)模型最后得到的預(yù)測(cè)結(jié)果合并起來作為最終的預(yù)測(cè)目標(biāo)矩陣;

(4) MTR(multiple target regression):將多目標(biāo)回歸問題轉(zhuǎn)化為多個(gè)單目標(biāo)回歸,假設(shè)預(yù)測(cè)目標(biāo)之間相互獨(dú)立.利用歷史時(shí)刻的網(wǎng)絡(luò)快照計(jì)算節(jié)點(diǎn)的一部分度量屬性(包括度、加權(quán)度、介數(shù)、PageRank值、離心率、聚集系數(shù)),用來建立一般的廣義線性回歸模型來預(yù)測(cè)角色的分布.

4.3 評(píng)估方法

本文采用兩種策略對(duì)預(yù)測(cè)模型進(jìn)行評(píng)價(jià).

其中,Gt+1為t+1時(shí)刻網(wǎng)絡(luò)的真實(shí)角色矩陣,為預(yù)測(cè)得到的t+1時(shí)刻網(wǎng)絡(luò)角色矩陣,分別為Gt+1和的第i行向量,||·||F表示矩陣的F范,||·||1表示1-范數(shù),N為網(wǎng)絡(luò)中節(jié)點(diǎn)的數(shù)目.以上兩個(gè)指標(biāo)可以從不同方面評(píng)估預(yù)測(cè)值與實(shí)際值之間的差異度.誤差指標(biāo)值越小,表示預(yù)測(cè)越精確.

4.4 實(shí)驗(yàn)效果

4.4.1 角色解釋

根據(jù)第 3.2節(jié)所介紹的角色解釋方法,用傳統(tǒng)的度量和鄰居節(jié)點(diǎn)的分布來刻畫角色是一種有效的解釋方法.本文以Facebook數(shù)據(jù)集為例對(duì)角色做出解釋(Enron與DBLP數(shù)據(jù)集類似),首先選取前面介紹的8種常見的度量屬性(包括度、加權(quán)度、介數(shù)、特征向量中心性、接近中心度、聚集系數(shù)、PageRank值以及離心率等)計(jì)算節(jié)點(diǎn)的度量矩陣,結(jié)果如圖7所示.圖8為根據(jù)鄰居節(jié)點(diǎn)的角色分布統(tǒng)計(jì),得到角色之間的關(guān)系.

圖7中由Facebook網(wǎng)絡(luò)得到的4種角色都具有明顯的特征:角色R3在度、加權(quán)度、介數(shù)(表示網(wǎng)絡(luò)中包含節(jié)點(diǎn)i的所有最短路的條數(shù)占所有最短路條數(shù)的百分比,反映節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)資源控制的程度,類似于 gatekeeping的角色)特征向量中心性、PageRank等度量上都有表現(xiàn),且取值都較大,但在離心率的取值上最小;角色R4在聚集系數(shù)和離心率兩種度量上取值較大,尤其是在離心率的取值明顯高于其他角色,而在其他度量上取值均較小;R1在度和特征向量中心性取值均比較明顯;而R2在各度量的取值均不突出.從圖8可看出:R3更傾向與其他角色的節(jié)點(diǎn)相連;而R4僅在自己角色的上的分布比較顯著,所表現(xiàn)出的同質(zhì)性比較強(qiáng);角色R3的節(jié)點(diǎn)與角色為R1的節(jié)點(diǎn)相連更緊密,并且這種緊密性是雙向的.通過以上度量屬性和鄰居節(jié)點(diǎn)角色分布的解釋,可推斷R3表示位于重要位置的節(jié)點(diǎn)(例如中心節(jié)點(diǎn));R1為具有重要鄰居的節(jié)點(diǎn);而R2代表網(wǎng)絡(luò)中普遍存在的較一般的節(jié)點(diǎn);R4可能是邊緣節(jié)點(diǎn)甚至是非激活的節(jié)點(diǎn).

Fig.7 Role explaination—NodeSense圖7 角色解釋——NodeSense

Fig.8 Role explaination—NeighborSense圖8 角色解釋——NeighborSense

4.4.2 角色預(yù)測(cè)

首先驗(yàn)證角色序列的平穩(wěn)性,在Enron,Facebook以及DBLP這3個(gè)數(shù)據(jù)集中隨機(jī)選取300個(gè)節(jié)點(diǎn),計(jì)算每個(gè)節(jié)點(diǎn)的前12個(gè)快照序列的自相關(guān)函數(shù).對(duì)一個(gè)序列{s1,s2,…,st},自相關(guān)函數(shù)(autocorrelation)計(jì)算如下:

其中,q為滯后階數(shù),為序列的均值.圖9為3個(gè)數(shù)據(jù)值中節(jié)點(diǎn)的平均自相關(guān)曲線圖.從圖中可以看出,相關(guān)函數(shù)隨滯后階數(shù)q的增加而快速下降并趨向于0,表明角色序列是平穩(wěn)的[24].

Fig.9 Autocorrelation function varies with the lag orderq圖9 自相關(guān)函數(shù)隨滯后階數(shù)q的變化

在本文角色預(yù)測(cè)模型中,向量自回歸的階數(shù)直接會(huì)影響模型預(yù)測(cè)的準(zhǔn)確性,因此接下來驗(yàn)證階數(shù)p對(duì)預(yù)測(cè)結(jié)果的影響.

圖10是在 3個(gè)數(shù)據(jù)集上,p的取值為 1～5,分別計(jì)算預(yù)測(cè)矩陣和真實(shí)矩陣Gt+1的均方根誤差(RMAE∝FPE)的結(jié)果.

Fig.10 Influence ofpto the prediction result圖10 階數(shù)p對(duì)預(yù)測(cè)結(jié)果的影響

從圖10的結(jié)果可以看出:Enron數(shù)據(jù)集在p=3時(shí)均方根誤差最小,Facebok和DBLP數(shù)據(jù)集在p=2時(shí)均方根誤差最小.由圖10可以看出:p的值從1變化到5,預(yù)測(cè)效果并沒有隨著階數(shù)的增大而更準(zhǔn)確,這說明預(yù)測(cè)時(shí)模型里包含的歷史時(shí)刻屬性個(gè)數(shù)并不是越多結(jié)果的準(zhǔn)確性越高.事實(shí)上這也是合理的,p的取值決定有多少歷史快照將影響當(dāng)前時(shí)刻網(wǎng)絡(luò)的角色分布:當(dāng)p的設(shè)定值過大時(shí),模型需要預(yù)測(cè)的參數(shù)增多,較早時(shí)刻歷史快照也會(huì)對(duì)預(yù)測(cè)結(jié)果帶來干擾;另一方面,當(dāng)p的設(shè)定值太小時(shí),模型將會(huì)欠擬合,導(dǎo)致殘差增加.綜合考慮,最優(yōu)的p取決于數(shù)據(jù)集,并通過公式(4)中的最終預(yù)測(cè)誤差來確定,結(jié)果與分析相吻合,表明當(dāng)前時(shí)刻網(wǎng)絡(luò)的結(jié)構(gòu)分布受更近時(shí)刻的歷史數(shù)據(jù)的影響更大.

下面將分別在Enron,Facebook以及DBLP這3個(gè)數(shù)據(jù)集上驗(yàn)證LR-DNSP模型的有效性.首先驗(yàn)證評(píng)估方法(a),此處Enron數(shù)據(jù)集階數(shù)p設(shè)定為3,后兩個(gè)數(shù)據(jù)集階數(shù)p設(shè)定為2.圖11～圖13分別為3個(gè)數(shù)據(jù)集的預(yù)測(cè)效果,Enron,Facebook數(shù)據(jù)集中均選取前19快照用來訓(xùn)練,預(yù)測(cè)Gt+1,19≤t≤23.DBLP數(shù)據(jù)集選取前12快照用來訓(xùn)練,預(yù)測(cè)Gt+1,11≤t≤15.

Fig.11 Predicition in Enron dataset圖11 Enron數(shù)據(jù)集預(yù)測(cè)效果

Fig.12 Predicition in Facebook dataset圖12 Facebook數(shù)據(jù)集預(yù)測(cè)效果

Fig.13 Predicition in DBLP dataset圖13 DBLP數(shù)據(jù)集預(yù)測(cè)效果

從圖11～圖13的預(yù)測(cè)結(jié)果可以看出:本文提出的LR-DNSP模型在3個(gè)規(guī)模不同的真實(shí)數(shù)據(jù)集均取得了很好的預(yù)測(cè)效果,與對(duì)預(yù)測(cè)目標(biāo)分別建立回歸模型的AR方法相比,LR-DNSP能得到更準(zhǔn)確的預(yù)測(cè)值,這說明節(jié)點(diǎn)在4種角色上的取值是有一定聯(lián)系的.再看與TM方法的對(duì)比,LR-DNSP在Enron數(shù)據(jù)集上的回歸階數(shù)為3,在后兩個(gè)數(shù)據(jù)集上的回歸階數(shù)為2,也就是說,Enron使用了3個(gè)最近歷史時(shí)刻的數(shù)據(jù)進(jìn)行預(yù)測(cè),DBLP和Facebook使用了2個(gè)最近歷史時(shí)刻的數(shù)據(jù)預(yù)測(cè),而TM只使用了前一個(gè)時(shí)刻的數(shù)據(jù)來預(yù)測(cè),在3個(gè)數(shù)據(jù)集上的預(yù)測(cè)效果均不如本文模型.MTR模型是根據(jù)歷史時(shí)刻網(wǎng)絡(luò)計(jì)算節(jié)點(diǎn)的一部分度量屬性(包括度、加權(quán)度、介數(shù)、PageRank值、離心率、聚集系數(shù)),用來建立一般的廣義線性回歸模型來預(yù)測(cè)角色的分布,從結(jié)果可以看出,預(yù)測(cè)效果僅優(yōu)于baseline,說明節(jié)點(diǎn)在下一時(shí)刻的角色分布不僅取決于節(jié)點(diǎn)的度量值,而受節(jié)點(diǎn)歷史時(shí)刻的角色分布影響更大一點(diǎn).

接下來驗(yàn)證評(píng)估方法(b),即預(yù)測(cè)節(jié)點(diǎn)角色類標(biāo)分類的準(zhǔn)確性,圖14～圖16分別為3個(gè)數(shù)據(jù)集預(yù)測(cè)的準(zhǔn)確性.

Fig.14 Classification accuracy of rolein Enorn dataset圖14 Enron數(shù)據(jù)集角色分類準(zhǔn)確性

Fig.15 Classification accuracy of rolein Facebook dataset圖15 Facebook數(shù)據(jù)集角色分類準(zhǔn)確性

Fig.16 Classification accuracy of role in DBLP dataset圖16 DBLP數(shù)據(jù)集角色分類準(zhǔn)確性

從3個(gè)數(shù)據(jù)集角色分類準(zhǔn)確性的結(jié)果可以看出,本文提出的LR-DNSP模型和TM方法在準(zhǔn)確性上優(yōu)于其他3種方法;還可以觀察到:相比Enron和Facebook網(wǎng)絡(luò),在DBLP數(shù)據(jù)集角色分類的準(zhǔn)確性上,PRE的預(yù)測(cè)效果與本文模型以及 TM 方法更接近.PRE直接使用當(dāng)前時(shí)刻節(jié)點(diǎn)的角色作為下一時(shí)刻的預(yù)測(cè)值,這是基于相鄰時(shí)刻網(wǎng)絡(luò)結(jié)構(gòu)不會(huì)發(fā)生劇烈變化的假設(shè);繼續(xù)分析可知:在 Enron和 Facebook網(wǎng)絡(luò)中,PRE表現(xiàn)很差.這說明Enron和Facebook網(wǎng)絡(luò)結(jié)構(gòu)并不穩(wěn)定.事實(shí)上,2001年7月～10月間,Enron公司發(fā)生了巨大的人事調(diào)動(dòng),年底公司破產(chǎn),Enron網(wǎng)絡(luò)結(jié)構(gòu)理應(yīng)是不穩(wěn)定的,而2008年的Facebook網(wǎng)絡(luò)正處于超速發(fā)展中,6月正式成為全球最大、增長(zhǎng)最快的社交網(wǎng)絡(luò),Facebook的網(wǎng)絡(luò)結(jié)構(gòu)也不會(huì)是穩(wěn)定的.但在DBLP網(wǎng)絡(luò)中,學(xué)者一般具有穩(wěn)定的研究興趣和合作學(xué)者,網(wǎng)絡(luò)結(jié)構(gòu)自然相對(duì)穩(wěn)定.

以上實(shí)驗(yàn)結(jié)果表明:在角色分類準(zhǔn)確性上,TM方法和本文提出的LR-DNSP模型不相上下;但綜合以上兩種評(píng)價(jià)策略,LR-DNSP模型在預(yù)測(cè)結(jié)果和分類準(zhǔn)確性的整體效果優(yōu)于其他方法.

4.5 時(shí)間開銷

下面分別在 Facebook和 DBLP數(shù)據(jù)集上進(jìn)行時(shí)間開銷的實(shí)驗(yàn)分析,Facebook數(shù)據(jù)集上分別選取 1 000,2 000,3 000,4 000和5 000個(gè)節(jié)點(diǎn),在DBLP數(shù)據(jù)集上分別選取3 000,6 000,9 000,12 000,15 000,18 000和21 000個(gè)節(jié)點(diǎn)進(jìn)行實(shí)驗(yàn).從結(jié)果可以看出:隨著節(jié)點(diǎn)的增加,運(yùn)行時(shí)間呈線性增長(zhǎng).驗(yàn)證了本文預(yù)測(cè)模型的可擴(kuò)展性.

Fig.17 Influence of node’s numbernon time overhead圖17 節(jié)點(diǎn)數(shù)n對(duì)時(shí)間開銷的影響

5 總 結(jié)

基于動(dòng)態(tài)信息網(wǎng)絡(luò)的廣泛應(yīng)用前景及角色發(fā)現(xiàn)在動(dòng)態(tài)網(wǎng)絡(luò)中有限的研究現(xiàn)狀,本文致力于研究動(dòng)態(tài)信息網(wǎng)絡(luò)中基于角色發(fā)現(xiàn)的結(jié)構(gòu)演化與預(yù)測(cè)問題.在網(wǎng)絡(luò)結(jié)構(gòu)難以量化呈現(xiàn)和分析的基礎(chǔ)上,本文提出了簡(jiǎn)化該問題的新思路,將基于遞歸地提取特征的角色發(fā)現(xiàn)方法引入動(dòng)態(tài)信息網(wǎng)絡(luò)的結(jié)構(gòu)演化分析中,同時(shí)給出了兩種角色解釋的方法;進(jìn)一步以角色發(fā)現(xiàn)的結(jié)構(gòu)模型為基礎(chǔ),將網(wǎng)絡(luò)結(jié)構(gòu)的預(yù)測(cè)問題轉(zhuǎn)化為角色預(yù)測(cè)問題,提出了基于潛在角色的動(dòng)態(tài)網(wǎng)絡(luò)結(jié)構(gòu)預(yù)測(cè)方法LR-DNSP.動(dòng)態(tài)網(wǎng)絡(luò)是目前復(fù)雜網(wǎng)絡(luò)研究領(lǐng)域中極具活力的新興研究方向,相比于靜態(tài)網(wǎng)絡(luò)的研究成果,目前動(dòng)態(tài)網(wǎng)絡(luò)的研究還處于起步階段,本文只針對(duì)其中的演化分析和預(yù)測(cè)問題進(jìn)行了研究.傳統(tǒng)靜態(tài)網(wǎng)絡(luò)中的許多問題都需要在動(dòng)態(tài)網(wǎng)絡(luò)中得到進(jìn)一步研究與擴(kuò)展,未來的研究工作將繼續(xù)關(guān)注動(dòng)態(tài)網(wǎng)絡(luò)的演化問題,進(jìn)一步優(yōu)化本文算法,以達(dá)到更好的效果.