基于角色發現的動態信息網絡結構演化分析?

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

1(航天器在軌故障診斷與維修重點實驗室,陜西 西安 710043)2(四川大學 計算機學院,四川 成都 610065)

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

信息網絡(information network)[6]是對現實空間中海量、多維、復雜結構和問題更具一般性的抽象[7],可以有效抽象出復雜系統中有價值的特征與潛在規律,從而為系統化地分析現實中的復雜網絡提供高效的研究和探索的方法.信息網絡一般都有動態的演化過程,新節點會持續地加入網絡,一些節點也會在中途消失,節點間連接的強度也在不斷變化,信息網絡中網絡結構隨之處于不斷演化的過程中[8],這里統稱為動態信息網絡.動態信息網絡的演化過程具有時序、復雜、多變的特點,蘊含著豐富的潛在信息和商業價值.動態網絡的結構預測是網絡演化中十分重要的問題,它旨在利用歷史網絡信息預測未來時刻節點的拓撲結構,幫助人們提前進行預警和決策.

動態信息網絡是當前復雜網絡研究領域中極具挑戰的新方向,由于網絡結構本身比較復雜,難以表示和量化,動態網絡時序、多變的演化過程更增加了分析的難度.基于動態信息網絡的廣泛應用前景及角色(role)發現在動態網絡中有限的研究現狀,本文致力于研究動態信息網絡中基于角色發現的結構預測問題,主要包括針對網絡結構表示的復雜性以及網絡演化時序多變的挑戰,將靜態網絡中用角色來量化網絡結構的方法擴展至動態網絡,以角色發現為基礎,對動態網絡結構預測進行探索性研究.主要貢獻如下.

(1) 提出動態網絡角色發現模型

使用角色來表示動態網絡的結構,將靜態網絡中基于遞歸地提取特征的角色發現方法擴展至動態網絡,按照時間序列對每個網絡快照進行特征提取,然后為每個快照學習節點的行為角色,提出動態網絡的角色發現模型.同時給出兩種角色解釋的方法,并在不同規模的真實網絡數據集上進行實驗,驗證本文模型的有效性和可解釋性.

(2) 提出基于潛在角色的動態網絡結構預測方法LR-DNSP

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

1 相關工作

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

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

近年來,角色發現正在被其他領域廣泛探索,如在線社交網絡[14]、科技網絡[15]、生物網絡[16,17]、網絡圖[18]等.角色發現在網絡挖掘的探索分析中,從傳統的節點分類、異常檢測、預測問題到結構相似性度量、圖相似性研究、網絡可視化、遷移學習等,逐步發揮著重要作用.McDowell等人[19]使用角色作為特征進行分類;Rossi等人[15]對給定的兩個圖,通過提取各自的特征和角色進行圖相似研究;Henderson等人[9]通過對給定網絡的角色學習,使用已有的知識在另一網絡學習同樣的角色集合,以提高分類的準確性.角色發現也可以被推廣到更多實際的應用中,例如,角色可用于檢測 IP網絡中的異常,可以基于用戶在網絡中的角色來定制廣告推送.在網絡挖掘和實際應用中,角色正在成為一種重要的潛在分析視角.但相比于社團發現、社團演化等,角色發現僅受到了有限的關注.

2 動態網絡的角色發現與角色解釋

拓撲結構是復雜網絡的研究基礎,靜態網絡中已有的拓撲指標包括度、距離、直徑、密度、聚集系數、介數中心性、參與三角形數量、模塊性等,涉及網絡不同層面的度量,為進一步分析動態網絡的結構特征提供了理論依據,也是捕獲角色的基礎[20].靜態網絡中的角色發現是一種對網絡結構的有效量化方法,本文旨在從節點角色的角度描述其在網絡中的結構特征,圖1中用不同顏色區分了網絡中的不同角色.使用角色來量化節點的結構,可以有效化簡網絡結構分析的難度.

Fig.1 Role discovery[9]圖1 角色發現[9]

網絡中的角色目前還沒有統一的定義,可以概括地認為角色是節點在網絡中所表現出的結構行為,來刻畫節點的某種重要程度[21].而角色發現則是通過量化節點結構,判定節點的結構角色.為解決動態網絡結構演化分析的問題,本文首先對動態網絡進行角色發現.

2.1 動態網絡的角色發現

進行動態網絡的角色發現之前,首先要構建動態網絡.動態網絡的定義如下.

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

研究動態網絡的角色發現,首先要對網絡進行特征提取,得到高維特征矩陣,然后對特征矩陣通過非負矩陣分解進行角色發現,在角色發現的過程中要確定分解的最優r值,最后對得到的角色模型進行解釋.將動態網絡表示為有序的子圖序列后,對每個時刻的網絡快照分別進行角色發現,即將每個子網絡都轉化為節點的角色信息.本文使用 KDD2012的RloX方法[9]進行角色發現.相比其他傳統方法,RolX更適合大規模網絡的角色發現,它不僅能發現網絡中的角色,還可以得到節點在各角色上的概率取值.該方法通過以下兩步過程完成.

(1) 特征提取

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

Fig.2 An example of role discovery圖2 角色發現的示例網絡

對每個節點分別進行特征提取,可以得到一個節點的特征取值向量.因此,可以將網絡快照St轉化為一個特征空間,記為節點的特征Vt∈?N×ft.

定義2(節點-特征矩陣序列V=〈V1,V2,…,VT〉. 給定動態網絡子圖序列D=〈S1,S2,…,ST〉,對St進行特征提取,得到節點的特征矩陣Vt∈?N×ft,其中,N為網絡的節點個數,ft表示t時刻得到的特征個數.對每個網絡快照D=〈S1,S2,…,ST〉分別進行特征提取,得到節點-特征矩陣序列V=〈V1,V2,…,VT〉.

(2) 角色發現

通過對節點的特征矩陣降維分解,進一步進行角色發現,降維后得到對節點特征的概括就是潛在的角色.基于非負矩陣分解實現上的簡便性、分解形式和分解結果上的可解釋性,本文使用非負矩陣分解方法對提取到的特征矩陣進行降維.對特征矩陣,給定一個正整數r

角色-特征矩陣F∈?r×ft表示了每個角色在提取到的特征值上的貢獻,學習到F之后,進一步對整個動態網絡進行角色發現,對每個子圖快照D=〈S1,S2,…,ST〉在特征提取后,根據得到節點的特征序列V=〈V1,V2,…,VT〉和F,分別進行NMF過程得到全部節點的角色序列G=〈G1,G2,…,GT〉.

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

算法1.角色個數選取算法.

輸入:原始節點-特征矩陣V∈?n×f;

輸出:角色個數:r.

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

2.2 角色解釋

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

基于以上思路,對給定動態網絡的子圖快照St與角色矩陣Gt,為每個節點計算一系列度量屬性,本文選取了8種傳統的度量屬性:度、加權度、介數、特征向量中心度、緊密中心度、聚集系數、PageRank、離心率,計算可得到t時刻節點的度量矩陣Mt∈?N×m,其中,m=8.為得到角色與度量之間的量化關系,NodeSense計算一個新的非負矩陣Pt,使得GtPt≈Mt,其中,Pt∈?r×m.Pt的行對應r個角色,列對應m個度量,Pt的每一行則表示該角色在各個度量上的概率取值,即角色在各個度量屬性的貢獻.

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

3 動態網絡角色預測

動態網絡的結構預測是網絡演化分析的重要問題,但由于動態網絡演化過程本身復雜多變,加上網絡規模的急劇增長,該問題還未得到很好的解決.網絡結構本身難以量化,直接預測網絡結構比較困難.本文的動態網絡角色模型為網絡結構預測問題提供了一個新的思路,即用角色來建模動態網絡結構,動態網絡結構表示為節點的角色分布序列,將網絡結構預測問題轉化為角色分布的預測.這樣,很大程度上降低了問題的求解難度(如圖3所示).

Fig.3 Role prediction of dynamic networks圖3 動態網絡角色預測

3.1 問題定義

本文將動態網絡結構預測轉換為可以表示結構特征的角色預測問題,即:根據歷史時刻網絡的角色分布,預測未來時刻網絡可能的角色分布情況.形式化表示為:給定動態網絡D=〈S1,S2,…,ST〉,得到動態網絡角色模型G=〈G1,G2,…,GT〉,Gi為i時刻節點角色矩陣,角色預測就是要得到t+1時刻網絡的節點角色矩陣.

對整個網絡,角色預測就是要得到t+1時刻網絡的節點角色矩陣,對每個節點,就是要預測節點n在t+1時刻的角色分布向量gt+1(的第n行).將網絡結構的預測問題劃分成子問題,對每個節點而言,預測目標是一個向量,且節點的在角色向量的分布上并非獨立不相關的.

向量自回歸(VAR)[24]基于數據的統計性質建立模型,適合處理多個變量分析與預測.本文借鑒 VAR方法的思路,提出了基于潛在角色的動態網絡結構預測方法 LR-DNSP(latent role based dynamic network structure prediction).LR-DNSP模型可以充分考慮前后向量序列之間的關系和角色之間的相互影響,通過向量自回歸的方法,由歷史時刻網絡數據得到訓練數據構建潛在角色預測模型,以下一時刻網絡角色的分布情況作為預測目標.LR-DNSP不僅利用多個歷史時刻的屬性信息還考慮了預測目標之間的相關性.

3.2 預測模型

本文預測模型的框架如圖4所示.

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

對所有的網絡快照計算其特征矩陣,并進行分解得到角色矩陣,用一部分歷史數據來訓練模型,剩下的一部分數據用來預測.

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

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

為了實驗對比中的公正性,以上LR-DNSP(AR)模型分別選取預測結果最佳的階數p.

考慮到多個預測目標之間存在的相互影響,在上述采用自回歸方法模型的基礎上,本文將預測目標視為向量,提出解決動態網絡角色預測問題的向量自回歸模型,對每個節點直接預測t+1時刻的角色分布向量(如圖6所示).

Fig.6 Prediction model of LR-DNSP圖6 LR-DNSP預測模型

對節點n用最近的p個歷史時刻的角色向量預測模型如下:

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

模型參數可以采用最小二乘估計,也可采用最大似然估計.本文模型中的參數學習通過解決以下問題的最優解:

LR-DNSP模型的訓練過程算法可抽象如下.

算法2.LR-DNSP模型訓練過程.

輸入:網絡快照D=〈S1,S2,…,ST〉和對應的節點角色序列G=〈G1,G2,…,GT〉;

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

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

算法3.角色分布預測算法.

輸入:最近p個時刻節點角色序列:{Gt-p+1,…,Gt-1,Gt};

輸出:t+1時刻節點的角色分布矩陣:.

4 實驗及分析

4.1 數據集

本文選取 3個具有代表意義的動態網絡數據集: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/),每個數據集的規模各不相同,均來自公開網站.表1列出了3個數據集的詳細信息,“*”表示平均值.

Table 1 Datasets details表1 數據集詳細信息

為簡化起見,本文假設網絡的節點數目保持不變,因而只考慮在研究時間段內一直出現的節點.對以上 3個網絡均建模為無向加權網絡,采用權值衰減的方法計算邊的權重.節點a和節點b之間的邊在t時刻的權值為

其中:wi是ti時刻節點a和節點b之間事件的權重(如節點間發送電子郵件數、合作發表論文數等),相應的鄰接矩陣序列為A=〈A1,A2,…,Ar〉;本文實驗中,取λ=1.

4.2 對比方法

本文使用4種方法作為對比.

(1) PRE(baseline):使用前一時刻網絡的角色分布作為要預測的下一時刻的網絡角色矩陣,即用時刻t的網絡角色分布矩陣作為時刻t+1時所求得表示網絡結構的角色矩陣,即:;

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

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

(4) MTR(multiple target regression):將多目標回歸問題轉化為多個單目標回歸,假設預測目標之間相互獨立.利用歷史時刻的網絡快照計算節點的一部分度量屬性(包括度、加權度、介數、PageRank值、離心率、聚集系數),用來建立一般的廣義線性回歸模型來預測角色的分布.

4.3 評估方法

本文采用兩種策略對預測模型進行評價.

其中,Gt+1為t+1時刻網絡的真實角色矩陣,為預測得到的t+1時刻網絡角色矩陣,分別為Gt+1和的第i行向量,||·||F表示矩陣的F范,||·||1表示1-范數,N為網絡中節點的數目.以上兩個指標可以從不同方面評估預測值與實際值之間的差異度.誤差指標值越小,表示預測越精確.

4.4 實驗效果

4.4.1 角色解釋

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

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

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

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

4.4.2 角色預測

首先驗證角色序列的平穩性,在Enron,Facebook以及DBLP這3個數據集中隨機選取300個節點,計算每個節點的前12個快照序列的自相關函數.對一個序列{s1,s2,…,st},自相關函數(autocorrelation)計算如下:

其中,q為滯后階數,為序列的均值.圖9為3個數據值中節點的平均自相關曲線圖.從圖中可以看出,相關函數隨滯后階數q的增加而快速下降并趨向于0,表明角色序列是平穩的[24].

Fig.9 Autocorrelation function varies with the lag orderq圖9 自相關函數隨滯后階數q的變化

在本文角色預測模型中,向量自回歸的階數直接會影響模型預測的準確性,因此接下來驗證階數p對預測結果的影響.

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

Fig.10 Influence ofpto the prediction result圖10 階數p對預測結果的影響

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

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

Fig.11 Predicition in Enron dataset圖11 Enron數據集預測效果

Fig.12 Predicition in Facebook dataset圖12 Facebook數據集預測效果

Fig.13 Predicition in DBLP dataset圖13 DBLP數據集預測效果

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

接下來驗證評估方法(b),即預測節點角色類標分類的準確性,圖14～圖16分別為3個數據集預測的準確性.

Fig.14 Classification accuracy of rolein Enorn dataset圖14 Enron數據集角色分類準確性

Fig.15 Classification accuracy of rolein Facebook dataset圖15 Facebook數據集角色分類準確性

Fig.16 Classification accuracy of role in DBLP dataset圖16 DBLP數據集角色分類準確性

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

以上實驗結果表明:在角色分類準確性上,TM方法和本文提出的LR-DNSP模型不相上下;但綜合以上兩種評價策略,LR-DNSP模型在預測結果和分類準確性的整體效果優于其他方法.

4.5 時間開銷

下面分別在 Facebook和 DBLP數據集上進行時間開銷的實驗分析,Facebook數據集上分別選取 1 000,2 000,3 000,4 000和5 000個節點,在DBLP數據集上分別選取3 000,6 000,9 000,12 000,15 000,18 000和21 000個節點進行實驗.從結果可以看出:隨著節點的增加,運行時間呈線性增長.驗證了本文預測模型的可擴展性.

Fig.17 Influence of node’s numbernon time overhead圖17 節點數n對時間開銷的影響

5 總 結

基于動態信息網絡的廣泛應用前景及角色發現在動態網絡中有限的研究現狀,本文致力于研究動態信息網絡中基于角色發現的結構演化與預測問題.在網絡結構難以量化呈現和分析的基礎上,本文提出了簡化該問題的新思路,將基于遞歸地提取特征的角色發現方法引入動態信息網絡的結構演化分析中,同時給出了兩種角色解釋的方法;進一步以角色發現的結構模型為基礎,將網絡結構的預測問題轉化為角色預測問題,提出了基于潛在角色的動態網絡結構預測方法LR-DNSP.動態網絡是目前復雜網絡研究領域中極具活力的新興研究方向,相比于靜態網絡的研究成果,目前動態網絡的研究還處于起步階段,本文只針對其中的演化分析和預測問題進行了研究.傳統靜態網絡中的許多問題都需要在動態網絡中得到進一步研究與擴展,未來的研究工作將繼續關注動態網絡的演化問題,進一步優化本文算法,以達到更好的效果.