基于網(wǎng)絡(luò)拓?fù)渑c節(jié)點(diǎn)元數(shù)據(jù)的社團(tuán)檢測(cè)算法

劉宇廷,畢海濱,郭 強(qiáng),倪穎杰

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

0 概述

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

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

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

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

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

1.1 隨機(jī)塊模型

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

(1)

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

1.2 隨機(jī)塊模型的改進(jìn)

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

puv=dudvθsu,sv

(2)

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

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

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

2 基于網(wǎng)絡(luò)拓?fù)渑c節(jié)點(diǎn)元數(shù)據(jù)的社團(tuán)檢測(cè)

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

(3)

由隨機(jī)塊模型可知基于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的先驗(yàn)概率模型為:

(4)

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

(5)

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

(6)

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

(7)

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

(8)

因此,基準(zhǔn)網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)社團(tuán)分配的先驗(yàn)概率模型為:

(9)

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

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

(10)

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

2.2 基于EM算法的推導(dǎo)

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

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

圖1 Jensen不等式的幾何表示

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

(11)

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

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

由此可以得到以下公式:

(12)

(13)

(14)

(15)

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

(16)

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

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

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

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

(17)

(18)

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

(19)

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

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

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

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

4)計(jì)算似然值與評(píng)價(jià)函數(shù),查看是否收斂。如果否,從第2個(gè)步驟開(kāi)始執(zhí)行。

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

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

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

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

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

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

通過(guò)設(shè)置不同的參數(shù),生成用來(lái)對(duì)比的基準(zhǔn)網(wǎng)絡(luò),實(shí)驗(yàn)中使用的參數(shù)如表2所示。

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

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

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

3.1.2 基準(zhǔn)網(wǎng)絡(luò)實(shí)驗(yàn)結(jié)果

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

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

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

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

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

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

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

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

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

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

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

3.2.2 特征提取

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

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

3.2.3 真實(shí)網(wǎng)絡(luò)實(shí)驗(yàn)結(jié)果

通常使用BIC準(zhǔn)則評(píng)價(jià)高斯混合模型,

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

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

與FN算法得到的社團(tuán)劃分對(duì)比,準(zhǔn)確率與NMI對(duì)比如表6所示,由于傳統(tǒng)社團(tuán)檢測(cè)算法FN無(wú)法比較NMI,因此只能對(duì)比社團(tuán)檢測(cè)的準(zhǔn)確率。

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

3.3 結(jié)果分析

3.3.1 基準(zhǔn)網(wǎng)絡(luò)實(shí)驗(yàn)結(jié)果分析

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

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

3.3.2 Facebook網(wǎng)絡(luò)實(shí)驗(yàn)結(jié)果分析

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

本文算法檢測(cè)到的社團(tuán)與真實(shí)社團(tuán)對(duì)比具有如下特點(diǎn):

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

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

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

4 結(jié)束語(yǔ)

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

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