劉宇廷,畢海濱,郭 強,倪穎杰

(江南計算技術(shù)研究所,江蘇 無錫 214000)

0 概述

不同領(lǐng)域多樣化的系統(tǒng)可以表示為復雜網(wǎng)絡(luò),例如科技系統(tǒng)、生物系統(tǒng)和社會系統(tǒng)[1]。針對復雜網(wǎng)絡(luò)研究的一個熱門方向是社團檢測,社團結(jié)構(gòu)在復雜網(wǎng)絡(luò)中普遍存在[2]。通過挖掘網(wǎng)絡(luò)中的社團,可以幫助理解網(wǎng)絡(luò)拓撲結(jié)構(gòu)特點,揭示復雜系統(tǒng)內(nèi)在功能特性,理解社團內(nèi)個體關(guān)系及行為的演化趨勢[3]。

傳統(tǒng)社團檢測方法基于網(wǎng)絡(luò)拓撲結(jié)構(gòu)的統(tǒng)計特性建模進行分析與挖掘,研究人員通常假設(shè)得到的社團能夠表示具有相似特性或功能的節(jié)點集合。當前,一些研究已經(jīng)證實了這個假設(shè)下得到的社團與網(wǎng)絡(luò)中元數(shù)據(jù)代表的團組是有區(qū)別的[4]。所以,許多研究人員期望能夠結(jié)合其他信息進行社團檢測,以發(fā)現(xiàn)網(wǎng)絡(luò)中的真實社團結(jié)構(gòu)。

在真實復雜網(wǎng)絡(luò)中,網(wǎng)絡(luò)除了拓撲信息之外,還有節(jié)點上的元數(shù)據(jù)與邊上的元數(shù)據(jù)。例如,社交網(wǎng)絡(luò)[5]如新浪微博包含用戶的個人信息(姓名、年齡、愛好等),引用網(wǎng)絡(luò)包括用戶的姓名、關(guān)鍵詞和文章的摘要信息、郵件網(wǎng)絡(luò)中發(fā)送郵件的內(nèi)容等。通常屬于一個社團中的節(jié)點一定共享了某些相似的屬性,反之可以認為節(jié)點的屬性影響了社團的結(jié)構(gòu),結(jié)合這些元數(shù)據(jù)將會提高社團檢測的準確性。近年來,研究者提出許多社團檢測算法,以期能夠通過元數(shù)據(jù)提高社團檢測的準確程度。文獻[6]利用2個節(jié)點之間共同好友的個數(shù)衡量節(jié)點之間的相似度,但是這個方法需要遍歷整個網(wǎng)絡(luò),復雜度高;文獻[7]利用譜聚類算法找到初始劃分,利用節(jié)點的度、內(nèi)度、外度建立條件概率表,選擇一部分最有可能的點作為根節(jié)點,構(gòu)建貝葉斯網(wǎng)絡(luò)來找到最優(yōu)社團結(jié)構(gòu);文獻[8]通過定義節(jié)點與節(jié)點、節(jié)點與社團之間的互動力作為社團檢測的指標;文獻[9]提出一種基于自然最近鄰居概念的社團檢測算法CD3N算法,以結(jié)構(gòu)相似度為基準,構(gòu)造網(wǎng)絡(luò)中節(jié)點的自然鄰居從而發(fā)現(xiàn)社團結(jié)構(gòu);文獻[10]指出當前很多方法只是基于網(wǎng)絡(luò)中邊的連接信息而忽視了節(jié)點上的信息,將邊與節(jié)點信息同時存在的網(wǎng)絡(luò)建模為NSBM,并研究基于似然推理的算法;文獻[11]提出通過改進基準網(wǎng)絡(luò)建模,將節(jié)點上的元數(shù)據(jù)(metadata)社團編號融合到模型中,以自動判斷這種元數(shù)據(jù)能否幫助網(wǎng)絡(luò)劃分,使得到的網(wǎng)絡(luò)劃分評價分數(shù)更高。但是算法中使用的元數(shù)據(jù)是社團歸屬標簽與年齡、性別等單一屬性,在刻畫節(jié)點特征上并不完整,例如社交網(wǎng)絡(luò)中一個節(jié)點的描述通常是一段文字、圖片等信息。

針對文獻[11]算法存在的問題,本文提出基于網(wǎng)絡(luò)拓撲與節(jié)點元數(shù)據(jù)的社團檢測算法CDNTNM。首先假設(shè)網(wǎng)絡(luò)中節(jié)點具有混合高斯分布,構(gòu)建節(jié)點元數(shù)據(jù)復雜分布的基準網(wǎng)絡(luò);然后建立融合網(wǎng)絡(luò)結(jié)構(gòu)與節(jié)點元數(shù)據(jù)的網(wǎng)絡(luò)模型,研究混合高斯模型與基準網(wǎng)絡(luò)模型的融合方法;最后分析真實網(wǎng)絡(luò)數(shù)據(jù)樣本分布,提出特征選擇方法。

1 基于隨機塊模型的網(wǎng)絡(luò)建模

1.1 隨機塊模型

隨機塊模型[12]通常建模為包含社團結(jié)構(gòu)的網(wǎng)絡(luò),用于輔助社團發(fā)現(xiàn)。隨機塊模型通常假設(shè)網(wǎng)絡(luò)中社團數(shù)量是固定的,網(wǎng)絡(luò)中的節(jié)點一定歸屬于其中某個社團,處于不同社團中的節(jié)點以概率prs建立連邊。調(diào)整同一個社團內(nèi)節(jié)點之間邊連接的概率,可以生成符合社團結(jié)構(gòu)定義的網(wǎng)絡(luò)結(jié)構(gòu),即社團內(nèi)部連邊密集而社團之間連邊稀疏,隨機塊模型的似然函數(shù)為:

(1)

其中,Aij代表網(wǎng)絡(luò)的鄰接矩陣中第i行第j列的元素,取值為1表示節(jié)點i和節(jié)點j之間存在連邊,取值為0表示不存在連邊,si表示節(jié)點i所屬的社團編號,i

1.2 隨機塊模型的改進

真實復雜網(wǎng)絡(luò)具有“無標度”特性[14],而隨機塊模型不滿足這個特征,所以,在擬合現(xiàn)實世界網(wǎng)絡(luò)數(shù)據(jù)時效果很差。文獻[15]通過在塊模型中添加度數(shù)相關(guān)的變量,使得節(jié)點之間邊的概率prs能夠與節(jié)點度數(shù)匹配(如節(jié)點具有邊的總量),從而滿足“無標度”這個特性。改進后的模型中定義節(jié)點之間邊的概率為:

puv=dudvθsu,sv

(2)

其中,du為節(jié)點u的度數(shù),θst是指定的參數(shù),θsu,sv能夠讓模型適合任意度數(shù)序列,即度數(shù)分布。

真實復雜網(wǎng)絡(luò)中節(jié)點上的元數(shù)據(jù)通常呈現(xiàn)信息多、形式雜的特點,例如:一個校園社交網(wǎng)絡(luò)中學生具有性別、年齡、種族等信息;一個食品網(wǎng)絡(luò)顧客信息包含體重、愛好等信息。節(jié)點上的信息不僅具有標量信息和連續(xù)變量信息,甚至還有文本信息,無疑對社團分布影響非常大。通常具有相似信息的節(jié)點元數(shù)據(jù)構(gòu)成的特征符合一定的分布,比如高斯分布。所以,在本文的實驗中,將這類具有多維度特征的向量建模為多維高斯模型。為方便觀察,實驗中使用二維高斯分布數(shù)據(jù)作為節(jié)點元數(shù)據(jù),數(shù)據(jù)來自2個具有相同方差、不同均值的高斯分布,參數(shù)如表1所示,通過參數(shù)可以將2個分布的邊界控制為清晰與混雜。

表1 節(jié)點元數(shù)據(jù)分布參數(shù)設(shè)置

2 基于網(wǎng)絡(luò)拓撲與節(jié)點元數(shù)據(jù)的社團檢測

2.1 基準網(wǎng)絡(luò)似然概率模型建模

(3)

由隨機塊模型可知基于網(wǎng)絡(luò)拓撲結(jié)構(gòu)的先驗概率模型為:

(4)

基于這兩個模型生成網(wǎng)絡(luò)的似然概率為:

(5)

其中,A為網(wǎng)絡(luò)的鄰接矩陣,Γ為參數(shù)γsx的矩陣,Θ為參數(shù)θst的矩陣。針對復雜網(wǎng)絡(luò)節(jié)點具有高維元數(shù)據(jù)的情況,可以定義:對于所有節(jié)點元數(shù)據(jù)X={x1,x2,…,xn},假設(shè)每個節(jié)點u分配到社團s的概率基于節(jié)點u的元數(shù)據(jù)xu,xu∈n,n≥1,定義概率為γsx,使用高斯混合模型對社團歸屬建模。高斯混合模型的概率模型為:

(6)

對于每個節(jié)點的元數(shù)據(jù)xi,其由第k個高斯模型生成的概率為:

(7)

其中,N(xi|μk,δk)為xi屬于分布k的后驗概率,如式(8)所示。

(8)

因此,基準網(wǎng)絡(luò)中每個節(jié)點社團分配的先驗概率模型為:

(9)

最終得到基于這兩個模型生成網(wǎng)絡(luò)的似然概率為:

P(A|Θ,π,μ,σ,x)=

(10)

在上述式中,π為高斯混合模型的權(quán)值向量,μ、δ為高斯混合模型的均值矩陣與方差矩陣。通?？梢允褂肊M算法求解式(9),通過估計模型中的參數(shù),得到模型的最優(yōu)解,從而得到社團分布。

2.2 基于EM算法的推導

設(shè)有函數(shù)f(x),x∈,如果?x有f″(x)≥0成立,則f(x)是凸函數(shù)。如果x是一個向量,而且其hessian矩陣H是半正定的(H≥0),那么f(x)是凸函數(shù)。如果f″(x)>0或者H>0,那么稱f(x)是嚴格凸函數(shù)。

Jensen不等式表述為:如果f是凸函數(shù),X是隨機變量,那么E[f(x)]≥f(EX),特別地,如果f是嚴格凸函數(shù),那么E[f(x)]=f(EX),當且僅當p(x=E[X])=1,即X是常量。這里f(EX)是f(E[X])的簡寫[15],其幾何表示如圖1所示。

圖1 Jensen不等式的幾何表示

給定的訓練樣本是X={x1,x2,…,xn},樣本之間相互獨立,對于每個樣本xi,存在隱含類別z使得p(x,z)最大。p(x,z)的最大似然估計公式如下:

(11)

求解第1步是對極大似然取對數(shù),第2步是對每個樣例的每個可能類別z求聯(lián)合分布概率和。但是直接求θ一般比較困難,因為有隱藏變量z存在,所以如果能夠確定z,則求解便可以化簡。

EM是一種解決存在隱含變量優(yōu)化問題的有效方法。由于不能直接最大化(θ),因此不斷地建立(θ)的下界(E步),然后優(yōu)化下界(M步)?？梢院唵蚊枋鰹?對于每一個樣本xi,用Qi表示該樣本隱含變量z的某種分布,且Qi滿足的條件是例如:要將動物分類,如果隱藏變量是體重,那么就是連續(xù)的高斯分布;如果按照隱藏變量是食肉或食草,那么就是伯努利分布。

由此可以得到以下公式:

(12)

(13)

(14)

(15)

p(z(i)|x(i);θ)

(16)

由上述推導可以發(fā)現(xiàn),固定θ后,Qi(z(i))的計算公式就是后驗概率,解決了Qi(z(i))如何選擇的問題。這一步就是E步,建立(θ)的下界。接下來的M步,就是在給定Qi(z(i))后,調(diào)整θ,去極大化(θ)的下界(在固定Qi(z(i))后,下界還可以調(diào)整的更大)。(θ)是單調(diào)增加的,所以,算法在(θ)趨于不變時收斂。

2.3 融合混合高斯模型的似然概率模型求解

將2.2節(jié)的推導應(yīng)用到式(10)中,可以得到:

logaP(A|Θ,π,μ,σ,x)=

(17)

(18)

由式(18)可以看出,Qi(z(i))為后驗概率分布,表達式為:

(19)

對式(18)應(yīng)用EM算法,可以得到CDMTMN算法對應(yīng)的最優(yōu)解,算法求解過程與EM算法中對應(yīng)步驟描述如下:

1)CDNTMN算法初始化,輸入數(shù)據(jù)集G,檢測網(wǎng)絡(luò)G中的社團結(jié)構(gòu),得到模型似然概率值并輸出網(wǎng)絡(luò)節(jié)點社團歸屬分布Q。初始化Θ、μ、δ、π的值。

2)E步,固定參數(shù)Θ、μ、δ、π的值,使用它們計算社團后驗概率分布Q。

3)M步,固定Q,更新參數(shù)Θ、μ、δ、π的值。

4)計算似然值與評價函數(shù),查看是否收斂。如果否,從第2個步驟開始執(zhí)行。

5)算法收斂,算法結(jié)束,得到模型似然概率值與社團最優(yōu)分布Q。

3 實驗與結(jié)果分析

仿真硬件平臺為:E4310,8 GB,Win7 x64,對比算法選用Newman的算法[11]、FN算法[17]。

3.1 基準網(wǎng)絡(luò)

3.1.1 基準網(wǎng)絡(luò)生成

在電腦生成的基準網(wǎng)絡(luò)上測試算法性能,基準網(wǎng)絡(luò)基于Newman改進后的隨機塊模型生成?；鶞示W(wǎng)絡(luò)的參數(shù)包括:網(wǎng)絡(luò)中社團數(shù)量K(定義K=2);網(wǎng)絡(luò)節(jié)點數(shù)量N;社團內(nèi)部與社團之間邊連接概率的混合參數(shù)Γ,為K×K矩陣;網(wǎng)絡(luò)中節(jié)點元數(shù)據(jù)維度D;節(jié)點元數(shù)據(jù)邊界清晰參數(shù)C。

通過設(shè)置不同的參數(shù),生成用來對比的基準網(wǎng)絡(luò),實驗中使用的參數(shù)如表2所示。

表2 基準網(wǎng)絡(luò)參數(shù)

具有相同的節(jié)點規(guī)模N、節(jié)點上的元數(shù)據(jù)維度D與社團內(nèi)邊連接概率pin,不同基準網(wǎng)絡(luò)通過社團間邊連接概率區(qū)分,為表征各個基準網(wǎng)絡(luò)的社團結(jié)構(gòu)程度,通過調(diào)整社團間邊的連接概率,將基準網(wǎng)絡(luò)分為3個等級:清晰,混雜,無,分別對應(yīng)具有明顯的社團結(jié)構(gòu)、社團邊界較明顯、無社團結(jié)構(gòu)(達到Newman所說的臨界值)?；鶞示W(wǎng)絡(luò)節(jié)點數(shù)量N=200,元數(shù)據(jù)維度D=2,社團內(nèi)邊連接概率pin=0.1,生成的網(wǎng)絡(luò)指標詳見表3。

表3 基準網(wǎng)絡(luò)

3.1.2 基準網(wǎng)絡(luò)實驗結(jié)果

由于EM算法求解參數(shù)最優(yōu)值時,存在局部極值,因此在本實驗中基于算法多次運行,得到算法平均性能,衡量標準使用準確率和NMI。NMI是用來衡量社團檢測與“真實”情況的方法[18],NMI的值域在0到1之間,如果節(jié)點元數(shù)據(jù)能夠非常準確地預測社團成員,則達到極大值。

1)設(shè)置不同網(wǎng)絡(luò)參數(shù),本文算法性能對比如圖2所示。

圖2 N=200時各參數(shù)下的算法性能

2)本文算法與Newman算法和FN算法的正確率對比如表4所示。

表4 各算法在不同社團質(zhì)量下的正確率對比 %

3.2 真實網(wǎng)絡(luò)

為體現(xiàn)算法在真實網(wǎng)絡(luò)上的表現(xiàn),選擇具有真實社團信息并且廣泛使用的Facebook數(shù)據(jù)集作為算法的驗證網(wǎng)絡(luò)。

Facebook數(shù)據(jù)集來自斯坦福大學(http://snap.stanford.edu/data/),其中包含10個用戶網(wǎng)絡(luò)(ego-network),共包含193個朋友圈和4 038位用戶。由于實驗需要真實社團信息,所以,選擇其中具有人工標注的用戶網(wǎng)絡(luò)。每個網(wǎng)絡(luò)包含一位處于中心的用戶,由用戶標注社團成員(即朋友圈成員),社團數(shù)量平均8個,包含不屬于任何社團的用戶

3.2.1 Facebook網(wǎng)絡(luò)預處理

通過預處理,提取其中兩位用戶的用戶網(wǎng)絡(luò)A和用戶網(wǎng)絡(luò)B,其網(wǎng)絡(luò)關(guān)系如圖3所示,可以看到用戶A的網(wǎng)絡(luò)社團結(jié)構(gòu)明顯,用戶B的網(wǎng)絡(luò)社團結(jié)構(gòu)不明顯。

圖3 用戶網(wǎng)絡(luò)真實社團劃分結(jié)果

3.2.2 特征提取

出于對用戶信息安全的考慮,數(shù)據(jù)集中的用戶特征被映射為對應(yīng)的值,形成了一個特征矩陣,本文對其做一次主成分分析,并約減到合適的維度。通過實驗發(fā)現(xiàn),用戶網(wǎng)絡(luò)A維度為133維、用戶網(wǎng)絡(luò)B維度為40時,可以保留原數(shù)據(jù)的90%的信息。用戶網(wǎng)絡(luò)相關(guān)參數(shù)如表5所示。由模塊度可以看出網(wǎng)絡(luò)A比網(wǎng)絡(luò)B的社團結(jié)構(gòu)明顯。

表5 用戶網(wǎng)絡(luò)參數(shù)

3.2.3 真實網(wǎng)絡(luò)實驗結(jié)果

通常使用BIC準則評價高斯混合模型,

圖4中可以看到,用戶網(wǎng)絡(luò)A社團數(shù)N=7和用戶網(wǎng)絡(luò)B社團數(shù)N=6時,bic值達到最小。

圖4 用戶網(wǎng)絡(luò)社團劃分的bic值對比

與FN算法得到的社團劃分對比,準確率與NMI對比如表6所示,由于傳統(tǒng)社團檢測算法FN無法比較NMI,因此只能對比社團檢測的準確率。

表6 用戶網(wǎng)絡(luò)各算法性能對比 %

3.3 結(jié)果分析

3.3.1 基準網(wǎng)絡(luò)實驗結(jié)果分析

由圖3可以看出,當元數(shù)據(jù)邊界明顯時,CDNTMN算法性能基本不會受到拓撲結(jié)構(gòu)的影響,準確率穩(wěn)定在90%以上,隨著社團質(zhì)量下降,出現(xiàn)了少量的無法收斂的情況。當元數(shù)據(jù)邊界不明顯時,算法性能隨著社團質(zhì)量下降而迅速下降,當社團之間邊連接概率大于等于0.06時,算法多次運行的結(jié)果中,多次出現(xiàn)無法收斂的情況,同時,社團準確率非常不穩(wěn)定。

由表4可以看出,本文算法能夠結(jié)合節(jié)點元數(shù)據(jù)與拓撲結(jié)構(gòu)檢測社團結(jié)構(gòu),在復雜網(wǎng)絡(luò)中社團結(jié)構(gòu)不明顯時,基于網(wǎng)絡(luò)拓撲結(jié)構(gòu)的算法正確率僅有52.5%,而本文算法可以穩(wěn)定在90%以上。但是當節(jié)點元數(shù)據(jù)分布邊界不明顯,同時社團之間邊連接概率達到Newman定義的條件時,算法性能也會急劇下降。

3.3.2 Facebook網(wǎng)絡(luò)實驗結(jié)果分析

在Facebook用戶網(wǎng)絡(luò)上的實驗可以發(fā)現(xiàn),用戶網(wǎng)絡(luò)A的模塊度在0.3左右,節(jié)點元數(shù)據(jù)與社團結(jié)構(gòu)相關(guān)程度高,實驗結(jié)果較好。用戶網(wǎng)絡(luò)B社團結(jié)構(gòu)不明顯,同時節(jié)點元數(shù)據(jù)所標注的社團與算法發(fā)現(xiàn)的社團之間存在差異,影響因素是人工采集的特征不完整。

本文算法檢測到的社團與真實社團對比具有如下特點:

1)如果現(xiàn)實世界網(wǎng)絡(luò)中社團結(jié)構(gòu)明顯,則任何算法都能夠準確地發(fā)現(xiàn)社團結(jié)構(gòu)。

2)如果現(xiàn)實世界網(wǎng)絡(luò)中社團結(jié)構(gòu)并不明顯且元數(shù)據(jù)不能夠反映社團劃分,如用戶網(wǎng)絡(luò)B,則本文算法準確率較傳統(tǒng)社團檢測算法有較大的提升。

實驗中發(fā)現(xiàn)用戶特征維度各不相同,且用戶特征矩陣為稀疏矩陣,這在一定程度上給用戶特征建模造成一定的困擾。如何確定一個用戶的主要特征,例如,文獻[19]發(fā)現(xiàn)雖然在Facebook網(wǎng)絡(luò)中。用戶來自世界各個地方的大學,但是一個用戶的朋友網(wǎng)絡(luò)中,不同大學數(shù)量卻不多,所以,這種具有強烈社團歸屬特性的特征在實驗中沒有重點利用。

4 結(jié)束語

本文結(jié)合社團檢測算法的現(xiàn)有研究,提出一種基于網(wǎng)絡(luò)拓撲結(jié)構(gòu)與節(jié)點元數(shù)據(jù)的社團檢測算法。相比傳統(tǒng)社團檢測算法,該算法在基準網(wǎng)絡(luò)中的正確率有顯著提高,結(jié)合網(wǎng)絡(luò)節(jié)點元數(shù)據(jù),即使在網(wǎng)絡(luò)中社團結(jié)構(gòu)不明顯的情況下,也可以生成較為準確的估計;由于真實網(wǎng)絡(luò)的節(jié)點元數(shù)據(jù)維度較高,因此其使用主成分分析約減特征維度,降低了計算復雜度,但是這種特征提取方法仍然比較粗糙,最后的社團檢測結(jié)果與人工標注社團有一定相似,不可避免地存在誤差。

本文算法使用的基準網(wǎng)絡(luò)具有固定的社團數(shù)量且沒有考慮網(wǎng)絡(luò)元數(shù)據(jù)重疊的情況。此外,真實網(wǎng)絡(luò)中節(jié)點元數(shù)據(jù)是脫敏映射后的稀疏矩陣,與真正的元數(shù)據(jù)還具有差距。下一步將針對上述情況做深入研究。