一種基于局部與全局結構特征的網絡節點角色發現算法

唐詩琦 懷 念 陳 軍 胡俊勇

(武漢大學計算機學院國家多媒體軟件工程技術研究中心 湖北 武漢 430072)(國網湖北省電力公司江陵縣供電公司 湖北 荊州 434000)

0 引 言

基于節點結構特征的角色發現在復雜網絡研究中成為一個越來越受關注的問題。具有相似的結構特征(例如度中心性、聚類系數和介數中心性等)的節點被劃分為同一角色，例如中心節點、橋梁節點、邊緣節點等。節點的角色發現問題在許多領域都有重要的應用，例如：角色可用于IP-traces等技術網絡的異常檢測[1-2]；可用于在線社交網絡中基于用戶的角色向用戶定制化地投放廣告[3]。此外，角色發現在許多社會網絡研究應用中也成為了一個重要的工具，例如分類[4-5]、主動學習、網絡采樣[6]和匿名化[7]等。

近年來，國內外對于角色發現的研究主要基于節點的結構特征。文獻[8]根據近年來的研究提出了基于節點結構特征的角色發現方法框架，主要分為兩步：(1) 構建角色特征，將圖轉換為一系列的圖的特征。(2) 角色分配，將擁有相似特征向量的節點分配為同一角色。文獻[9]提出了RolX算法[9]，該算法是一個可拓展的，無監督學習方法。文獻[10]根據Henderson提出的算法，將RolX算法擴展到了動態網絡中，提出了動態行為混合成員模型DBMM(Dynamic Behavioral Mixed-membership Model)。文獻[11]將RolX算法通過添加稀疏以及多樣性約束拓展為半監督的學習算法GLRD。文獻[12]則結合了基于圖和基于特征的角色發現算法，同時考慮了在網絡整體中角色間的連接模式與節點局部特征的連接模式，提出了RIDεRs(Role Identification and Discovery using ε-equitable Refinements)算法。

目前，對于角色發現的研究大多數還是基于網絡的拓撲結構，應用節點的局部結構特征[9-11]。本文同時考慮了的節點的全局以及區域特征，遞歸地生成節點結構特征矩陣，使用非負矩陣分解NMF(Non-negative Matrix Factorization)發現角色。將算法應用于Facebook以及Email-Enron社會網絡數據集[13]，并與其他角色發現算法進行評估對比。實驗表明，本文所提出算法在局部以及全局評價指標上，相較其他算法具有更高的準確性。

1 節點結構特征矩陣構建

一個網絡的拓撲結構記為G(V,E)，其中V={v1,v2,…,vn}是網絡中節點的集合，而E={e1,e2,…,em}是網絡中邊的集合，n和m分別為節點數和邊數。一個圖的鄰接矩陣被記為An×n=(aij)，在無向網絡中，若節點vi和節點vj之間存在連邊，則aij=1，否則aij=0。

本文綜合節點的局部以及全局特征作為原始特征，遞歸地計算節點特征的總和以及平均值，得到節點的區域特征。在遞歸過程中若新特征與原特征十分相近時，則認為新產生的特征對網絡結構不再提供新的信息，停止遞歸，由此得到節點的結構特征矩陣。

1.1 節點結構特征

1.1.1 局部指標

在社會網絡中，節點的度作為節點的局部特征之一，是一個簡單但十分重要的概念。節點Vi的度ki被定義為與節點Vi直接相連的節點的數目。本文使用節點的度中心性作局部指標，構建節點的結構特征矩陣。度中心性表示為：

(1)

1.1.2 全局指標

節點的全局屬性具有許多的度量值，為了平衡算法時間復雜度以及準確性，本文選擇了基于特征向量的全局屬性。基于特征向量的屬性，不僅考慮了節點的鄰居節點數量，還考慮了其鄰居節點的質量對該節點重要性的影響，同時與其他全局屬性相比，具有更低的時間復雜度[14]。

(2)

PageRank的時間復雜度為O(n+m)，其中n和m分別為網絡中的節點數和邊數。另外由于PageRank的算法是用于有向圖的，在本文的實驗中，無向圖的計算將自動將兩個節點間的邊轉換為兩個有向邊。

1.2 遞歸特征

本文參考文獻[16]在2011年所提出的ReFeX特征提取方法，將度中心性和PageRank作為原始的特征值，然后遞歸計算當前節點個體網絡的特征值和以及平均值，并對相似特征值進行分箱處理。若遞歸產生的特征值向量與原特征值向量的方差小于相似度閾值，則終止遞歸。為控制生成遞歸特征的數量，減少算法復雜度，經過多次實驗，設置初始相似度閾值為0，并在每一次遞歸結束后增加3。遞歸特征的生成流程見圖1。

圖1 遞歸特征生成流程圖

算法偽代碼如算法1所示。

算法1生成節點遞歸特征矩陣

輸入：網絡G

輸出：包含原始特征和遞歸特征的特征矩陣V

1 計算網絡G中節點的PageRank和度中心性，獲得原始特征矩陣F

2 設置相似度閾值threshold=0

3 while(true){

4 計算每個節點自網絡中的所有節點在F中的特征值之和與平均值得到Fnew

5Fall=F+Fnew

6 設置BinFraction=0.5

7 for eachfiinFall{

8fsorted=fi.sort()

9 設置BinValue=0，NumNodes=網絡G中的節點數，NumAssigned=0

10 NumToAssign= ceil(BinFraction *(NumNodes - NumAssigned ) )

11 for j in NumToAssign do {

12fsorted(j)=BinValue

13 }

14Fbin+=fsorted

15 NumAssigned+=NumToAssign

16 ++BinValue

17 }

18 創建新的網絡Gwcc，以Fbin中每個特征fi作為節點i

19 對于每對節點，如果|fi-fi+1|>threshold，則在點i與點i+1間添加邊

20 得到網絡Gwcc的連通組件，取每個聯通組件中的第一個節點k所對應的特征fk添加到特征矩陣Fretain中

21ifFretain.length==0 {break;}

22 else {

23F+=Fretain

24 threshold+=3

25 }

26 }

2 角色發現

2.1 矩陣分解

通過節點特征矩陣構建步驟，得到了節點-特征矩陣Vn×f，其中n為節點個數，f為對應的特征個數。使用非負矩陣分解NMF，對于給定的矩陣Vn×f，存在正整數r<

(3)

s.t.G≥0F≥0

式中：Gn×r的每一行代表了該節點屬于每個角色概率分布；Fr×f的每一列指定了特定角色的成員關系如何有助于評估特征值。

在執行矩陣分解時，需要確定整數r(即節點被分配的角色)的數目。對于該問題，本文選用了最小描述長度MDL標準來選擇角色分配數量的最佳估計值r。

對于給定的模型，可以通過計算兩個部分來得到所需的描述長度r：(1) 描述模型本身所需要的比特數M；(2) 描述V-GF的重構誤差(實現無損壓縮)的代價ε。最終得到的最優的r值，即最小化描述長度L的值，即L=M+ε。

假定G和F不是稀疏矩陣，則描述該模型的成本被定義為：

M=br(n+f)

(4)

式中：b的值取log2(n)，則彌補V-GF重構誤差的代價為：

(5)

這里使用到了KL散度來進行計算。

為確定算法所發現角色的數量r，首先使用不同r值進行非負矩陣分解，得到不同的矩陣G與矩陣F，再使用最小描述長度方法進行計算。當計算得到的L值最小時，即得到了當前網絡的劃分角色數量r。

2.2 意義建構

由文獻[9]中提出的NodeSense意義建構方法可以很好地應用于大型網絡中。由于大型網絡不易于圖形化，使用相應的度量指標對角色進行評估，可以更加直觀地分析得出該節點角色在網絡中的作用。

對于評價指標，本文選用了全局屬性介數中心性，接近中心性，局部屬性聚類系數以及鄰居屬性節點個體網絡中的各個節點度之和共m個評價指標。

在NodeSense方法中，給定網絡G、n個節點、r個角色以及m個評價指標。對于網絡G中的每個節點，計算其在m個評價指標中的得分，從而得到對應的節點評價矩陣Mn×m。在角色發現算法中，通過矩陣分解步驟，得到了節點角色矩陣Gn×r。NodeSense方法將矩陣Mn×m和矩陣Gn×r作為輸入，計算得到一個非負的角色評價矩陣Er×m，其中M≈GE，對于minE‖M-GE‖2，滿足E≥0。再根據角色評價矩陣E，計算對應的NodeSense矩陣N：

(6)

式中：Ed為1×m維非負矩陣，代表了單個角色在M個評價指標中的得分；N為r×m維矩陣。

3 實驗與結果分析

本文實驗使用斯坦福大學SNAP項目中的Facebook及Email-Enron數據集[13]進行實驗，數據集的具體信息見表1。

表1數據集

數據集節點數邊數平均度網絡直徑FaceBook4 03988 23421.9468Email-Enron36 692183 8315.01011

在以往的工作中，往往將角色發現作為輔助手段應用于如鏈路預測和異常檢測等研究中。因此，目前角色發現領域并未發展出權威的、公認的評價體系。為將本文算法與其他的角色發現算法進行對比，評估各個算法的性能，本文參考文獻[12]中提出的評價方法。該方法引入了復雜網絡中社區劃分評價標準模塊度[17]的思想，對實驗中的每個網絡中的節點隨機分配角色，得到對應的零模型。計算節點所分配角色的NodeSense值與對應零模型的NodeSense值的平均絕對誤差，評估該角色發現算法的性能。平均絕對誤差的數值越高，表明該方法的性能越好。

對于給定的網絡G、n個節點以及相應的角色發現算法所得到的r個角色，對該網絡中的每個節點隨機分配一個角色，由此得到隨機分配的節點角色矩陣Gr。由式(6)計算得到該隨機分配的節點角色矩陣對應的NodeSense矩陣Nr。計算該角色發現算法的NodeSense矩陣N與對應的隨機分配NodeSense矩陣Nr的絕對誤差：

(7)

同時由式(7)可計算得到平均絕對誤差：

(8)

本文將實驗結果與RolX算法和GLRD算法進行對比，其中GLRD算法由其稀疏性和差異性約束分為GLRD-S和GLRD-D(詳情見文獻[11])，對比幾種算法NS值與零模型NS值的平均絕對誤差。實驗對比數據如表2-表3所示。

表2 基于FaceBook數據集的算法性能對比

表3 基于Email-Enron數據集的算法性能對比

由表2和表3可知，本文所提出算法在介數中心性、接近中心性、個體網絡，以及聚類系數四個評價指標上，均比其他算法具有更高的性能。

4 結 語

本文針對復雜網絡中的節點角色發現問題，基于節點的結構特征，在RolX角色發現算法的基礎上，引入節點的局部以及全局特征進行特征提取，構建節點結構特征矩陣，使用非負矩陣分解對節點結構特征矩陣進行降維，獲得對應的節點角色矩陣。并使用幾種不同的節點重要性評價指標對分析所得的角色進行意義建構，同時對比RolX與GLRD角色發現算法。實驗結果表明本文提出算法在局部以及全局屬性上具有更高的性能。下一步工作將本文提出算法應用于更大規模的數據集中，以滿足真實場景中更大規模數據的處理以及分析需求。