一種基于局部與全局結(jié)構(gòu)特征的網(wǎng)絡(luò)節(jié)點(diǎn)角色發(fā)現(xiàn)算法

唐詩琦 懷 念 陳 軍 胡俊勇

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

0 引 言

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

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

目前，對于角色發(fā)現(xiàn)的研究大多數(shù)還是基于網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，應(yīng)用節(jié)點(diǎn)的局部結(jié)構(gòu)特征[9-11]。本文同時考慮了的節(jié)點(diǎn)的全局以及區(qū)域特征，遞歸地生成節(jié)點(diǎn)結(jié)構(gòu)特征矩陣，使用非負(fù)矩陣分解NMF(Non-negative Matrix Factorization)發(fā)現(xiàn)角色。將算法應(yīng)用于Facebook以及Email-Enron社會網(wǎng)絡(luò)數(shù)據(jù)集[13]，并與其他角色發(fā)現(xiàn)算法進(jìn)行評估對比。實(shí)驗(yàn)表明，本文所提出算法在局部以及全局評價指標(biāo)上，相較其他算法具有更高的準(zhǔn)確性。

1 節(jié)點(diǎn)結(jié)構(gòu)特征矩陣構(gòu)建

一個網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)記為G(V,E)，其中V={v1,v2,…,vn}是網(wǎng)絡(luò)中節(jié)點(diǎn)的集合，而E={e1,e2,…,em}是網(wǎng)絡(luò)中邊的集合，n和m分別為節(jié)點(diǎn)數(shù)和邊數(shù)。一個圖的鄰接矩陣被記為An×n=(aij)，在無向網(wǎng)絡(luò)中，若節(jié)點(diǎn)vi和節(jié)點(diǎn)vj之間存在連邊，則aij=1，否則aij=0。

本文綜合節(jié)點(diǎn)的局部以及全局特征作為原始特征，遞歸地計(jì)算節(jié)點(diǎn)特征的總和以及平均值，得到節(jié)點(diǎn)的區(qū)域特征。在遞歸過程中若新特征與原特征十分相近時，則認(rèn)為新產(chǎn)生的特征對網(wǎng)絡(luò)結(jié)構(gòu)不再提供新的信息，停止遞歸，由此得到節(jié)點(diǎn)的結(jié)構(gòu)特征矩陣。

1.1 節(jié)點(diǎn)結(jié)構(gòu)特征

1.1.1 局部指標(biāo)

在社會網(wǎng)絡(luò)中，節(jié)點(diǎn)的度作為節(jié)點(diǎn)的局部特征之一，是一個簡單但十分重要的概念。節(jié)點(diǎn)Vi的度ki被定義為與節(jié)點(diǎn)Vi直接相連的節(jié)點(diǎn)的數(shù)目。本文使用節(jié)點(diǎn)的度中心性作局部指標(biāo)，構(gòu)建節(jié)點(diǎn)的結(jié)構(gòu)特征矩陣。度中心性表示為：

(1)

1.1.2 全局指標(biāo)

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

(2)

PageRank的時間復(fù)雜度為O(n+m)，其中n和m分別為網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)和邊數(shù)。另外由于PageRank的算法是用于有向圖的，在本文的實(shí)驗(yàn)中，無向圖的計(jì)算將自動將兩個節(jié)點(diǎn)間的邊轉(zhuǎn)換為兩個有向邊。

1.2 遞歸特征

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

圖1 遞歸特征生成流程圖

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

算法1生成節(jié)點(diǎn)遞歸特征矩陣

輸入：網(wǎng)絡(luò)G

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

1 計(jì)算網(wǎng)絡(luò)G中節(jié)點(diǎn)的PageRank和度中心性，獲得原始特征矩陣F

2 設(shè)置相似度閾值threshold=0

3 while(true){

4 計(jì)算每個節(jié)點(diǎn)自網(wǎng)絡(luò)中的所有節(jié)點(diǎn)在F中的特征值之和與平均值得到Fnew

5Fall=F+Fnew

6 設(shè)置BinFraction=0.5

7 for eachfiinFall{

8fsorted=fi.sort()

9 設(shè)置BinValue=0，NumNodes=網(wǎng)絡(luò)G中的節(jié)點(diǎn)數(shù)，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 創(chuàng)建新的網(wǎng)絡(luò)Gwcc，以Fbin中每個特征fi作為節(jié)點(diǎn)i

19 對于每對節(jié)點(diǎn)，如果|fi-fi+1|>threshold，則在點(diǎn)i與點(diǎn)i+1間添加邊

20 得到網(wǎng)絡(luò)Gwcc的連通組件，取每個聯(lián)通組件中的第一個節(jié)點(diǎn)k所對應(yīng)的特征fk添加到特征矩陣Fretain中

21ifFretain.length==0 {break;}

22 else {

23F+=Fretain

24 threshold+=3

25 }

26 }

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

2.1 矩陣分解

通過節(jié)點(diǎn)特征矩陣構(gòu)建步驟，得到了節(jié)點(diǎn)-特征矩陣Vn×f，其中n為節(jié)點(diǎn)個數(shù)，f為對應(yīng)的特征個數(shù)。使用非負(fù)矩陣分解NMF，對于給定的矩陣Vn×f，存在正整數(shù)r<

(3)

s.t.G≥0F≥0

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

在執(zhí)行矩陣分解時，需要確定整數(shù)r(即節(jié)點(diǎn)被分配的角色)的數(shù)目。對于該問題，本文選用了最小描述長度MDL標(biāo)準(zhǔn)來選擇角色分配數(shù)量的最佳估計(jì)值r。

對于給定的模型，可以通過計(jì)算兩個部分來得到所需的描述長度r：(1) 描述模型本身所需要的比特?cái)?shù)M；(2) 描述V-GF的重構(gòu)誤差(實(shí)現(xiàn)無損壓縮)的代價ε。最終得到的最優(yōu)的r值，即最小化描述長度L的值，即L=M+ε。

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

M=br(n+f)

(4)

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

(5)

這里使用到了KL散度來進(jìn)行計(jì)算。

為確定算法所發(fā)現(xiàn)角色的數(shù)量r，首先使用不同r值進(jìn)行非負(fù)矩陣分解，得到不同的矩陣G與矩陣F，再使用最小描述長度方法進(jìn)行計(jì)算。當(dāng)計(jì)算得到的L值最小時，即得到了當(dāng)前網(wǎng)絡(luò)的劃分角色數(shù)量r。

2.2 意義建構(gòu)

由文獻(xiàn)[9]中提出的NodeSense意義建構(gòu)方法可以很好地應(yīng)用于大型網(wǎng)絡(luò)中。由于大型網(wǎng)絡(luò)不易于圖形化，使用相應(yīng)的度量指標(biāo)對角色進(jìn)行評估，可以更加直觀地分析得出該節(jié)點(diǎn)角色在網(wǎng)絡(luò)中的作用。

對于評價指標(biāo)，本文選用了全局屬性介數(shù)中心性，接近中心性，局部屬性聚類系數(shù)以及鄰居屬性節(jié)點(diǎn)個體網(wǎng)絡(luò)中的各個節(jié)點(diǎn)度之和共m個評價指標(biāo)。

在NodeSense方法中，給定網(wǎng)絡(luò)G、n個節(jié)點(diǎn)、r個角色以及m個評價指標(biāo)。對于網(wǎng)絡(luò)G中的每個節(jié)點(diǎn)，計(jì)算其在m個評價指標(biāo)中的得分，從而得到對應(yīng)的節(jié)點(diǎn)評價矩陣Mn×m。在角色發(fā)現(xiàn)算法中，通過矩陣分解步驟，得到了節(jié)點(diǎn)角色矩陣Gn×r。NodeSense方法將矩陣Mn×m和矩陣Gn×r作為輸入，計(jì)算得到一個非負(fù)的角色評價矩陣Er×m，其中M≈GE，對于minE‖M-GE‖2，滿足E≥0。再根據(jù)角色評價矩陣E，計(jì)算對應(yīng)的NodeSense矩陣N：

(6)

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

3 實(shí)驗(yàn)與結(jié)果分析

本文實(shí)驗(yàn)使用斯坦福大學(xué)SNAP項(xiàng)目中的Facebook及Email-Enron數(shù)據(jù)集[13]進(jìn)行實(shí)驗(yàn)，數(shù)據(jù)集的具體信息見表1。

表1數(shù)據(jù)集

數(shù)據(jù)集節(jié)點(diǎn)數(shù)邊數(shù)平均度網(wǎng)絡(luò)直徑FaceBook4 03988 23421.9468Email-Enron36 692183 8315.01011

在以往的工作中，往往將角色發(fā)現(xiàn)作為輔助手段應(yīng)用于如鏈路預(yù)測和異常檢測等研究中。因此，目前角色發(fā)現(xiàn)領(lǐng)域并未發(fā)展出權(quán)威的、公認(rèn)的評價體系。為將本文算法與其他的角色發(fā)現(xiàn)算法進(jìn)行對比，評估各個算法的性能，本文參考文獻(xiàn)[12]中提出的評價方法。該方法引入了復(fù)雜網(wǎng)絡(luò)中社區(qū)劃分評價標(biāo)準(zhǔn)模塊度[17]的思想，對實(shí)驗(yàn)中的每個網(wǎng)絡(luò)中的節(jié)點(diǎn)隨機(jī)分配角色，得到對應(yīng)的零模型。計(jì)算節(jié)點(diǎn)所分配角色的NodeSense值與對應(yīng)零模型的NodeSense值的平均絕對誤差，評估該角色發(fā)現(xiàn)算法的性能。平均絕對誤差的數(shù)值越高，表明該方法的性能越好。

對于給定的網(wǎng)絡(luò)G、n個節(jié)點(diǎn)以及相應(yīng)的角色發(fā)現(xiàn)算法所得到的r個角色，對該網(wǎng)絡(luò)中的每個節(jié)點(diǎn)隨機(jī)分配一個角色，由此得到隨機(jī)分配的節(jié)點(diǎn)角色矩陣Gr。由式(6)計(jì)算得到該隨機(jī)分配的節(jié)點(diǎn)角色矩陣對應(yīng)的NodeSense矩陣Nr。計(jì)算該角色發(fā)現(xiàn)算法的NodeSense矩陣N與對應(yīng)的隨機(jī)分配NodeSense矩陣Nr的絕對誤差：

(7)

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

(8)

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

表2 基于FaceBook數(shù)據(jù)集的算法性能對比

表3 基于Email-Enron數(shù)據(jù)集的算法性能對比

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

4 結(jié) 語

本文針對復(fù)雜網(wǎng)絡(luò)中的節(jié)點(diǎn)角色發(fā)現(xiàn)問題，基于節(jié)點(diǎn)的結(jié)構(gòu)特征，在RolX角色發(fā)現(xiàn)算法的基礎(chǔ)上，引入節(jié)點(diǎn)的局部以及全局特征進(jìn)行特征提取，構(gòu)建節(jié)點(diǎn)結(jié)構(gòu)特征矩陣，使用非負(fù)矩陣分解對節(jié)點(diǎn)結(jié)構(gòu)特征矩陣進(jìn)行降維，獲得對應(yīng)的節(jié)點(diǎn)角色矩陣。并使用幾種不同的節(jié)點(diǎn)重要性評價指標(biāo)對分析所得的角色進(jìn)行意義建構(gòu)，同時對比RolX與GLRD角色發(fā)現(xiàn)算法。實(shí)驗(yàn)結(jié)果表明本文提出算法在局部以及全局屬性上具有更高的性能。下一步工作將本文提出算法應(yīng)用于更大規(guī)模的數(shù)據(jù)集中，以滿足真實(shí)場景中更大規(guī)模數(shù)據(jù)的處理以及分析需求。