趙琪琪,馬慧芳,2,劉海姣,賈俊杰

(1.西北師范大學(xué) 計算機(jī)科學(xué)與工程學(xué)院,蘭州 730070; 2.桂林電子科技大學(xué) 廣西可信軟件重點實驗室,廣西 桂林 541004)

0 概述

隨著信息技術(shù)的快速發(fā)展,各行業(yè)的數(shù)據(jù)規(guī)模日益增加,因此數(shù)據(jù)異常檢測顯得尤為重要,其廣泛應(yīng)用于政務(wù)數(shù)據(jù)異常檢測、商業(yè)欺詐檢測、醫(yī)療記錄異常分析等方面,而針對網(wǎng)絡(luò)社區(qū)的異常檢測成為近年來研究的熱點。傳統(tǒng)無屬性網(wǎng)絡(luò)異常社區(qū)檢測方法通常僅利用社區(qū)結(jié)構(gòu)信息無法檢測到內(nèi)部屬性不一致的社區(qū)[1-2],可用于稠密子圖的社區(qū)挖掘及僅考慮結(jié)構(gòu)的異常社區(qū)檢測,但不適用于真實世界中的復(fù)雜網(wǎng)絡(luò)。這是因為現(xiàn)實世界的網(wǎng)絡(luò)多數(shù)由節(jié)點、邊和與節(jié)點相關(guān)的屬性向量組成,且這些網(wǎng)絡(luò)質(zhì)量層次不齊、數(shù)量龐大,如何量化屬性網(wǎng)絡(luò)中的社區(qū)質(zhì)量顯得尤為重要。近年來,研究人員面向?qū)傩跃W(wǎng)絡(luò)提出一些異常社區(qū)檢測方法,例如將所有可用屬性視為同等重要[3-4],或者采用無監(jiān)督技術(shù)來確定屬性的重要性權(quán)重構(gòu)成屬性子空間向量用于節(jié)點屬性相似度計算[5-6]。社區(qū)子空間在結(jié)構(gòu)上是內(nèi)部緊密連接,與網(wǎng)絡(luò)其余部分分離,并且在此類屬性子空間下社區(qū)內(nèi)部節(jié)點間具有相似性。在屬性網(wǎng)絡(luò)中,高質(zhì)量的社區(qū)更加模塊化并且趨向于具有相似屬性特征的社區(qū)[7],即具有相同屬性的節(jié)點結(jié)構(gòu)也相似。

因此,研究人員利用屬性對異常社區(qū)檢測的影響所提出的方法,通過社區(qū)內(nèi)部屬性信息來衡量社區(qū)質(zhì)量,并對社區(qū)之間存在邊界邊的連通性進(jìn)行量化,用以衡量社區(qū)質(zhì)量[8],或用于尋找屬性網(wǎng)絡(luò)中的離群點及子圖[9-10]。屬性網(wǎng)絡(luò)中社區(qū)質(zhì)量的好壞可以通過綜合社區(qū)結(jié)構(gòu)和屬性信息進(jìn)行衡量,例如社區(qū)內(nèi)部節(jié)點連接稀疏程度、節(jié)點間子空間的屬性相異度信息、社區(qū)內(nèi)節(jié)點連向外部鄰居節(jié)點的緊密程度和內(nèi)部節(jié)點與社區(qū)鄰居節(jié)點基于子空間的相似情況。AMEN[11]模型將模塊度思想運用到社區(qū)檢測中,建立正規(guī)性模型量化社區(qū)質(zhì)量,用于檢測屬性網(wǎng)絡(luò)中社區(qū)內(nèi)部一致性較差但外部緊密連接的異常社區(qū)。然而,基于AMEN模型的節(jié)點屬性權(quán)重挖掘方法僅考慮節(jié)點結(jié)構(gòu)相似度對異常社區(qū)檢測的影響,并未考慮到節(jié)點附著屬性信息對異常社區(qū)檢測所帶來的影響。

鑒于節(jié)點屬性信息相對于結(jié)構(gòu)信息更能反映真實復(fù)雜網(wǎng)絡(luò)的特性,本文提出融合屬性和結(jié)構(gòu)的子空間異常社區(qū)檢測方法(SBAM),在高質(zhì)量社區(qū)定義的基礎(chǔ)上,設(shè)計基于子空間的社區(qū)質(zhì)量評估模型,利用結(jié)構(gòu)與屬性同時量化社區(qū)質(zhì)量,挖掘較低分值的異常社區(qū)集合。

1 相關(guān)工作

文獻(xiàn)[12]研究真實網(wǎng)絡(luò)中的社區(qū)統(tǒng)計特性、社區(qū)劃分情況以及社區(qū)質(zhì)量如何在不同社區(qū)規(guī)模下發(fā)生變化,研究表明大型高質(zhì)量社區(qū)存在,并且這一發(fā)現(xiàn)已被GLEICH等人[13]的研究所證實。文獻(xiàn)[14]分析社交網(wǎng)絡(luò)結(jié)構(gòu)并發(fā)現(xiàn)社交網(wǎng)絡(luò)中在線和離線社交關(guān)系的相似性。文獻(xiàn)[1]指出egonet特性在真實網(wǎng)絡(luò)中形成類似冪律的模式,其他有關(guān)大型真實圖上結(jié)構(gòu)和動態(tài)的研究均沒有聚焦于社區(qū)[15-16]。上述研究主要關(guān)注無屬性網(wǎng)絡(luò),還有一些研究在無屬性圖上量化了社區(qū)結(jié)構(gòu),例如文獻(xiàn)[7]提出模塊度;文獻(xiàn)[17]分析了一系列關(guān)于量化社區(qū)結(jié)構(gòu)的研究并在基準(zhǔn)社區(qū)上對這些方法的性能進(jìn)行對比;文獻(xiàn)[18]研究了屬性集與密集子圖之間的結(jié)構(gòu)相關(guān)模式。

社區(qū)挖掘算法旨在通過模塊化實現(xiàn)社區(qū)檢測[19-20],還有一些應(yīng)用于圖劃分的社區(qū)挖掘算法[21]以及基于種子集擴(kuò)展[22-23]、非負(fù)矩陣分解[24]和標(biāo)簽傳播[25]的重疊社區(qū)檢測方法,這些研究主要關(guān)注無屬性圖,然而在屬性圖上的社區(qū)檢測成為近年來的研究熱點。此類研究的重點在于發(fā)現(xiàn)結(jié)構(gòu)緊密且屬性相似的子空間社區(qū),其側(cè)重于社區(qū)內(nèi)部密度,卻忽略了社區(qū)邊界邊。

文獻(xiàn)[26]利用頻繁子圖挖掘和信息理論來識別具有單一屬性的異常子圖。文獻(xiàn)[27]提出一個新的社區(qū)異常值識別方法,但該方法識別出的異常值在完整屬性空間和屬于同一社區(qū)的其他屬性空間中的數(shù)值不同。文獻(xiàn)[10]側(cè)重于提取從用戶偏好推斷出的預(yù)定義屬性子集的社區(qū),同時該方法會輸出在該子集中部分或完全偏離的社區(qū)異常值。

本文方法利用正態(tài)性,從社區(qū)內(nèi)部一致性和外部可分性上對社區(qū)質(zhì)量進(jìn)行評估。在結(jié)構(gòu)上注重量化,由于社區(qū)之間的邊界邊會影響社區(qū)質(zhì)量的正態(tài)性分?jǐn)?shù),因此本文方法融合社區(qū)內(nèi)外部結(jié)構(gòu)和屬性子空間,通過屬性圖的子空間與社區(qū)結(jié)構(gòu)信息進(jìn)行圖異常檢測。在真實數(shù)據(jù)集和人工數(shù)據(jù)集上驗證了本文方法的魯棒性和可擴(kuò)展性,并且其在精確度和性能上優(yōu)于現(xiàn)有社區(qū)檢測方法,如OddBall[1]和AMEN等,因此本文方法更適用于復(fù)雜網(wǎng)絡(luò)。

2 屬性子空間挖掘

對于特定社區(qū)而言,節(jié)點附加的屬性對社區(qū)質(zhì)量都有一定的影響,然而不同屬性的影響不同。因此,本節(jié)針對不同的異常社區(qū)檢測要求,設(shè)計3種基于屬性維度重要性量化的子空間求解策略,即基于屬性平均距離的子空間求解策略,基于負(fù)熵加權(quán)的子空間推斷策略和融合屬性平均距離和基于負(fù)熵加權(quán)的子空間求解策略,通過挖掘每個社區(qū)所對應(yīng)的屬性權(quán)重向量,獲得社區(qū)屬性權(quán)重子空間。

2.1 問題定義

與傳統(tǒng)異常社區(qū)檢測方法不同,本文方法是在挖掘?qū)傩宰涌臻g下對社區(qū)質(zhì)量進(jìn)行評估,將不同維度的重要程度屬性權(quán)重共同作為衡量社區(qū)質(zhì)量的因素,消除異常社區(qū)檢測過程中僅考慮社區(qū)結(jié)構(gòu)的片面性,使得挖掘到的異常社區(qū)更真實。

本文融合屬性與結(jié)構(gòu)的子空間異常社區(qū)檢測框架如圖1所示,其具體步驟如下:

1)給定:帶節(jié)點屬性的社區(qū)集合C。

2)挖掘:各社區(qū)中的子空間向量wi,i∈(1,2,…,k)。

3)量化:依照定義的質(zhì)量評估函數(shù),對社區(qū)內(nèi)部緊密性和外部分離性定量計算質(zhì)量分?jǐn)?shù)Q。

4)發(fā)現(xiàn):將定量計算得到的社區(qū)質(zhì)量分?jǐn)?shù)升序排列,輸出質(zhì)量分?jǐn)?shù)較低的社區(qū)集合L。

圖1 融合屬性與結(jié)構(gòu)的子空間異常社區(qū)檢測框架

2.2 基于屬性平均距離的子空間求解策略

在特定社區(qū)中挖掘子空間,基于屬性平均距離的子空間求解策略采用提取社區(qū)焦點屬性維度的思想,將對社區(qū)產(chǎn)生影響較大的屬性維度賦予較大的權(quán)重值,而忽略對社區(qū)影響較小的屬性維度,降低子空間的求解復(fù)雜度。另外,該策略適用于提取焦點屬性的異常社區(qū)檢測,并且量化了節(jié)點屬性對社區(qū)生成的重要性影響。

設(shè)當(dāng)前待檢測社區(qū)為Ci=(Vi,Ei,Fi),Ci∈C,|Vi|=ni,Sc={|vi∈Vi,vj∈Vi}是社區(qū)Ci的節(jié)點對集合,|Sc|=(ni2-ni)/2。設(shè)Se={|vi∈V/Vi,vj∈V/Vi}是隨機(jī)取自屬性圖G中去除社區(qū)Ci節(jié)點的節(jié)點對集合。為保證Se中包含足夠多的節(jié)點對且各節(jié)點間距離較遠(yuǎn),設(shè)|Se|=r|Sc|,隸屬于同一社區(qū)中的節(jié)點對間距離較小,即當(dāng)前社區(qū)Ci中的節(jié)點對集合Sc節(jié)點間距離較小;反之,不屬于同一社區(qū)的節(jié)點對間距離Se較大。

定義1(節(jié)點對屬性平均距離) 給定節(jié)點對集合S,節(jié)點vi和節(jié)點vj在第t維屬性上的平均距離gt(S)定義為:

(1)

(2)

對子空間進(jìn)行標(biāo)準(zhǔn)化處理得到:

(3)

2.3 基于負(fù)熵加權(quán)的子空間推斷策略

利用負(fù)熵加權(quán)法確定屬性子空間,對于每一個特定社區(qū)Ci都有特定屬性權(quán)重向量wi,求解目標(biāo)函數(shù)如下:

(4)

其中,ni是社區(qū)Ci中的節(jié)點個數(shù),fvit為節(jié)點vi第t維屬性,γ是控制多維權(quán)重激勵強(qiáng)度的一個正參數(shù)。式(4)中第一部分是衡量社區(qū)內(nèi)部的緊密程度,即社區(qū)內(nèi)部節(jié)點間的距離,第二部分是負(fù)熵值。

通過最小化目標(biāo)函數(shù)求得社區(qū)Ci的屬性子空間權(quán)重向量wi=(w1,w2,…,wr)T,wi在服從約束的條件下,該社區(qū)屬性子空間的少數(shù)維度權(quán)重較大,其余維度的權(quán)重值較小。需要注意的是,每一個社區(qū)中的權(quán)重列向量只與當(dāng)前社區(qū)相關(guān)。

(5)

2.4 子空間融合求解策略

為快速精確地求解社區(qū)子空間,本文提出融合屬性平均距離和負(fù)熵加權(quán)的子空間求解模型,具體如下:

(6)

3 融合節(jié)點屬性與結(jié)構(gòu)信息的異常社區(qū)檢測

本節(jié)通過融合結(jié)構(gòu)與屬性挖掘子空間策略,采用AMEN中的正規(guī)性分?jǐn)?shù)設(shè)計思想[11]量化社區(qū)質(zhì)量,通過對社區(qū)質(zhì)量分?jǐn)?shù)進(jìn)行排序,找到分?jǐn)?shù)較低的社區(qū)集合,即為檢測發(fā)現(xiàn)的異常社區(qū)集合。

在現(xiàn)實中大量社區(qū)互相重疊且不能直接簡單分割,即社區(qū)間有交叉邊且邊上權(quán)重不可忽略。在異常社區(qū)檢測任務(wù)中,很多社區(qū)并非是單獨存在,即某一社區(qū)與其他社區(qū)相互重疊并含有交叉邊,或在社區(qū)外部存在中心節(jié)點且對該社區(qū)內(nèi)部產(chǎn)生影響。因此,本文在挖掘各個社區(qū)的子空間后,根據(jù)社區(qū)質(zhì)量評估模型,定義社區(qū)質(zhì)量評估函數(shù)Q,定量計算社區(qū)質(zhì)量分?jǐn)?shù)值,并采集分?jǐn)?shù)較低的異常社區(qū)集合。

社區(qū)質(zhì)量評估函數(shù)與模塊度概念相似,用于量化社區(qū)質(zhì)量。一個高質(zhì)量的社區(qū)主要包含兩個標(biāo)準(zhǔn):1)社區(qū)內(nèi)部節(jié)點連接緊密程度和節(jié)點之間在子空間上的相似度;2)社區(qū)內(nèi)節(jié)點連向外部鄰居節(jié)點的稀疏程度和內(nèi)部節(jié)點與社區(qū)鄰居節(jié)點在子空間上的相異性。評估社區(qū)質(zhì)量的優(yōu)劣主要為:屬性相似且結(jié)構(gòu)相似的節(jié)點應(yīng)隸屬于同一社區(qū),而不相似的節(jié)點應(yīng)分離并隸屬于不同社區(qū)。

定義2(節(jié)點加權(quán)屬性相似度) 社區(qū)Ci中兩個節(jié)點vi、vj之間的加權(quán)屬性相似度定義如下:

(7)

其中,‖fvi-fvj‖2表示節(jié)點vi、vj屬性列向量差值二范式,節(jié)點加權(quán)屬性相似度為[0,1],wi是屬性子空間的權(quán)重行向量,計算兩個節(jié)點屬性之間的相似度,即節(jié)點屬性的加權(quán)相似度。

設(shè)圖G的兩個社區(qū)Ci和Bj均為圖G的子圖,則社區(qū)Ci的質(zhì)量評估函數(shù)Q定義如下:

(8)

其中,Aij是社區(qū)Ci的鄰接矩陣Ai中的元素,fvi為社區(qū)Ci中節(jié)點vi屬性的列向量,fvb為社區(qū)Bj中節(jié)點vb屬性的列向量,qi表示節(jié)點vi的度,qb表示節(jié)點vb的度。

對于具有最高質(zhì)量分值的社區(qū):1)存在所有可能的內(nèi)部邊緣且節(jié)點屬性和結(jié)構(gòu)對相似性高,此時式(8)中的第一項最大化;2)由于社區(qū)沒有交叉邊或社區(qū)與社區(qū)之間存在的重疊邊相似性接近0,因此式(8)中的第二項可忽略。屬性圖的社區(qū)質(zhì)量分?jǐn)?shù)為負(fù)表示異?；蛸|(zhì)量較差,即異常社區(qū)。因此,需要極大化社區(qū)質(zhì)量評估模型(式(8)),具體如下:

(9)

其中,相似性s(fvi,fvj)的計算可由定義2求得。

由于本文方法是一種啟發(fā)式優(yōu)化方法,因此容易在社區(qū)劃分中找到最佳解決方案以獲得良好的圖劃分效果。因為圖的劃分會影響社區(qū)檢測結(jié)果,所以本文方法不是完全隨機(jī)地將屬性圖初始化為若干子圖,而是使用重疊社區(qū)檢測算法來初始化屬性圖進(jìn)行社區(qū)劃分。

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

為全面評估本文SBAM方法的有效性和效率,本節(jié)分別在人工數(shù)據(jù)集和真實數(shù)據(jù)集上設(shè)計兩組實驗。首先,對實驗所用的人工數(shù)據(jù)集和真實數(shù)據(jù)集進(jìn)行描述;其次,觀察不同參數(shù)值對實驗結(jié)果的影響,選擇合適的參數(shù);最后,選取兩個典型的社區(qū)劃分算法在人工網(wǎng)絡(luò)中與本文方法進(jìn)行比較,并在真實網(wǎng)絡(luò)中與AMEN方法[11]進(jìn)行對比。由于本文方法涉及3種子空間求解策略,因此為表示方便,將基于屬性平均距離的子空間求解策略記為SBAM-L1,基于負(fù)熵加權(quán)的子空間推斷策略記為SBAM-L2,融合屬性平均距離與負(fù)熵加權(quán)的子空間求解策略記為SBAM-L3。

4.1 實驗設(shè)置

4.1.1 數(shù)據(jù)集

由于LFR基準(zhǔn)網(wǎng)絡(luò)[28]具有與真實網(wǎng)絡(luò)類似的特征,因此可基于LFR基準(zhǔn)網(wǎng)絡(luò)生成人工屬性網(wǎng)絡(luò)。社區(qū)的度和社區(qū)大小規(guī)模的分布是分別由指數(shù)T1和T2支配的冪律分布?；鶞?zhǔn)網(wǎng)絡(luò)的參數(shù)設(shè)置如下:節(jié)點個數(shù)n,平均節(jié)點度davg,最大節(jié)點度dmax,最小社區(qū)成員個數(shù)cmin,最大社區(qū)成員個數(shù)cmax、混合參數(shù)μ,邊數(shù)m、屬性數(shù)d、社區(qū)數(shù)|C|、社區(qū)平均大小|S|?；旌蠀?shù)控制網(wǎng)絡(luò)的失真程度,μ值越大,基準(zhǔn)網(wǎng)絡(luò)越失真。為獲得帶屬性的基準(zhǔn)網(wǎng)絡(luò),附加3種類型的屬性向量到所有節(jié)點,即數(shù)值、二進(jìn)制和分類。附加的屬性向量由4個參數(shù)控制,即屬性總個數(shù)r、屬性子空間個數(shù)k、異常社區(qū)數(shù)量l和相似概率p。此外,為選擇合適的基準(zhǔn)精確評估各對比方法的有效性和效率。在設(shè)定實驗最佳參數(shù)時,分別對n、μ、cmin、r、k和p進(jìn)行 600組基準(zhǔn)測試,實驗結(jié)果中的最佳參數(shù)設(shè)置如表1所示。

表1 人工網(wǎng)絡(luò)數(shù)據(jù)集參數(shù)設(shè)置

為驗證本文方法在真實網(wǎng)絡(luò)上的效果,本節(jié)選取Facebook、Twitter和Google+ 3個具有真實社區(qū)的屬性網(wǎng)絡(luò)參數(shù)設(shè)置進(jìn)行驗證,具體數(shù)據(jù)集如表2所示。其中,節(jié)點、邊、屬性是表述數(shù)據(jù)集中網(wǎng)絡(luò)的構(gòu)建方式,節(jié)點代表網(wǎng)絡(luò)中的用戶,依據(jù)用戶與用戶之間的友誼關(guān)系、協(xié)從關(guān)系構(gòu)建節(jié)點之間的邊,節(jié)點上附著的屬性是用戶個人信息等特征。

表2 真實網(wǎng)絡(luò)數(shù)據(jù)集參數(shù)設(shè)置

4.1.2 實驗基準(zhǔn)及評價指標(biāo)

本文實驗中人工網(wǎng)絡(luò)部分采用LFR基準(zhǔn)網(wǎng)絡(luò)在混合參數(shù)μ=0時的網(wǎng)絡(luò)形態(tài),真實網(wǎng)絡(luò)的對比方法為AMEN[11]、OddBall[1]和SODA[29],其中,OddBall方法通過無屬性圖上社區(qū)內(nèi)部一致性評估社區(qū)質(zhì)量,SODA方法根據(jù)屬性圖上社區(qū)內(nèi)部一致性和外部可分性量化社區(qū)質(zhì)量。實驗評價指標(biāo)為歸一化互信息NMI[30]和AUC,其中,NMI基于混淆矩陣N的定義,矩陣中的行表示真實社區(qū)、列表示檢測到的社區(qū),具體計算如下:

(10)

其中,Nij是屬于真實社區(qū)i和檢測到的社區(qū)j的節(jié)點數(shù)量,Ni.是矩陣N中第i行元素的總和,N.j是矩陣N中第j列元素的總和,A表示網(wǎng)絡(luò)的真實劃分,B表示基于算法得到的劃分,CA是真實社區(qū)數(shù)量,CB是檢測到的社區(qū)數(shù)量。

4.2 結(jié)果分析

本節(jié)主要在人工網(wǎng)絡(luò)上對LFR基準(zhǔn)網(wǎng)絡(luò)生成過程進(jìn)行參數(shù)設(shè)置,設(shè)計在LFR基準(zhǔn)網(wǎng)絡(luò)下各參數(shù)對SBAM方法的性能影響實驗,并對實驗結(jié)果進(jìn)行分析。在真實網(wǎng)絡(luò)中,采用AMEN方法對真實網(wǎng)絡(luò)進(jìn)行異常擾動并設(shè)計性能對比實驗。

4.2.1 人工網(wǎng)絡(luò)分析

通過實驗測試隨著參數(shù)k、μ的變化,OddBall、SODA和SBAM方法的NMI及運行時間變化規(guī)律。表3給出在人工網(wǎng)絡(luò)上算法50次運行結(jié)果中最佳NMI和運行時間的平均值,采用SBAM-L2方法進(jìn)行性能對比,其中“—”表示實驗時間超過24 h,其NMI和時間消耗不再列出。由表3可以看出,總體上,隨著參數(shù)k、μ的變化,本文方法的有效性和效率均優(yōu)于OddBall和SODA方法。在混合參數(shù)μ小于0.3時,3種方法的NMI值均為1,可見3種方法在沒有異常擾動的情況下均能較好地完成異常社區(qū)檢測任務(wù),而隨著混合參數(shù)μ的增大,OddBall和SODA方法性能不同程度地降低;在混合參數(shù)μ<0.3且挖掘子空間個數(shù)較少時,SODA方法時間消耗少于本文方法所需時間,其原因在于本文方法適用于復(fù)雜網(wǎng)絡(luò)中的屬性網(wǎng)絡(luò),其在挖掘多個屬性子空間上具有優(yōu)勢,而當(dāng)需要挖掘較少的屬性子空間時,SODA方法則更適用。

表3 異常社區(qū)檢測方法在人工網(wǎng)絡(luò)數(shù)據(jù)集上的性能對比

圖2表示隨著網(wǎng)絡(luò)中n和cmin的增加,本文方法和對比方法的NMI值變化情況。實驗中α的初始值設(shè)置為0.5,結(jié)合多次實驗結(jié)果表明:當(dāng)α=0.42時實驗效果最佳。

圖2 節(jié)點個數(shù)和最小社區(qū)個數(shù)對異常社區(qū)檢測方法的性能影響

由圖2可以看出,SBAM方法在LFR基準(zhǔn)人工網(wǎng)絡(luò)中,節(jié)點個數(shù)和最小社區(qū)個數(shù)不斷增加,NMI值也呈現(xiàn)上升趨勢,而OddBall和SODA方法的NMI值均低于SBAM方法,即便在圖2(b)中SBAM方法的NMI值有所下降,但也仍接近于1,可見SBAM方法適合大型網(wǎng)絡(luò)中的異常社區(qū)檢測,得到該實驗結(jié)果的原因在于SBAM方法提供了3種節(jié)點屬性子空間求解策略,當(dāng)網(wǎng)絡(luò)中的節(jié)點個數(shù)逐漸增加時,節(jié)點與節(jié)點之間的結(jié)構(gòu)和屬性信息均增加,此時更容易實現(xiàn)子空間向量的求解,所以SBAM方法更適合檢測大型網(wǎng)絡(luò)中的異常社區(qū)。

4.2.2 真實網(wǎng)絡(luò)分析

本節(jié)將SBAM方法在3個真實數(shù)據(jù)集Facebook、Twitter和Google+上與AMEN方法進(jìn)行對比。首先,為產(chǎn)生真實異常值,采用AMEN中對真實網(wǎng)絡(luò)進(jìn)行不同程度異常擾動來獲取異常社區(qū)的方法;然后,根據(jù)OddBall和SODA方法分別從結(jié)構(gòu)、屬性、屬性融合結(jié)構(gòu)的角度出發(fā),利用NMI均值和AUC值對實驗結(jié)果進(jìn)行綜合評估,本次實驗采用SBAM-L2方法進(jìn)行性能對比。

圖3表示隨著真實網(wǎng)絡(luò)異常擾動強(qiáng)度的增加,在不同數(shù)據(jù)集上,SBAM-L2方法能夠準(zhǔn)確檢測異常社區(qū),AMEN方法次之,但圖3不論是從屬性或者結(jié)構(gòu)角度,還是從屬性融合結(jié)構(gòu)的角度評估方法性能,SBAM-L2方法均為最優(yōu),其原因為SBAM-L2方法的特點是依據(jù)融合屬性和結(jié)構(gòu)的信息,挖掘網(wǎng)絡(luò)中的子空間,實現(xiàn)異常社區(qū)檢測。實驗選取的真實網(wǎng)絡(luò)數(shù)據(jù)集Facebook、Twitter和Google+中節(jié)點與邊之間存在友誼關(guān)系或者協(xié)從關(guān)系,通過計算子空間求出社區(qū)質(zhì)量分?jǐn)?shù)值,而SBAM方法就是利用社區(qū)子空間結(jié)合社區(qū)結(jié)構(gòu)信息得出異常社區(qū)質(zhì)量分?jǐn)?shù)值。

圖3 異常社區(qū)檢測方法在真實網(wǎng)絡(luò)數(shù)據(jù)集上擾動強(qiáng)度的變化情況

本文提出的3種子空間求解策略對異常社區(qū)檢測性能產(chǎn)生了不同程度的影響,因此分別采用SBAM-L1、SBAM-L2以及SBAM-L3 3種方法進(jìn)行100次實驗,權(quán)重系數(shù)因子α設(shè)置為實驗最佳值0.42,求解SBAM方法和AMEN方法的NMI均值,具體實驗結(jié)果如圖4所示。

圖4 基于3種子空間求解策略的SBAM與AMEN方法性能對比

由圖4可知,SBAM方法與AMEN方法在3種子空間求解策略的性能比較上,本文方法的NMI均值略微高于AMEN方法,且對于兩種子空間求解策略而言,在3個真實數(shù)據(jù)集上,SBAM-L2方法的性能略優(yōu)于SBAM-L1方法。SBAM-L2方法性能更優(yōu)的原因在于該方法考慮了每一維度的重要性,僅維度權(quán)重不同,而SBAM-L1方法是對屬性進(jìn)行權(quán)重重要性的提取,不重要的屬性維度權(quán)重賦值為0,在某種程度上無法揭示出真實網(wǎng)絡(luò)的屬性子空間。然而,SBAM-L3方法融合了兩種子空間求解策略,既考慮求解子空間的計算速度也權(quán)衡屬性每一維度的重要性,采用權(quán)重系數(shù)調(diào)節(jié)因子α來量化兩種策略對挖掘社區(qū)子空間的影響,但SBAM-L2方法對模型影響更大,在快速精準(zhǔn)求解子空間的應(yīng)用場景下,可采用融合模型挖掘子空間。因此,對于需要嚴(yán)格保留社區(qū)完整形態(tài)的異常社區(qū)檢測,負(fù)熵加權(quán)策略更實用;而若僅選取局部的焦點屬性來快速求解子空間,則屬性平均距離策略更適合。針對不同的異常社區(qū)檢測任務(wù),可采用不同的子空間求解策略。由圖4可看出,本文方法可在真實網(wǎng)絡(luò)中較準(zhǔn)確地發(fā)現(xiàn)異常社區(qū)。

5 結(jié)束語

本文針對屬性圖中的異常社區(qū)檢測問題,提出融合屬性與結(jié)構(gòu)的子空間異常社區(qū)檢測方法,設(shè)計3種子空間求解策略,并利用社區(qū)質(zhì)量評估模型檢測異常社區(qū)。實驗結(jié)果表明,該方法既能檢測高質(zhì)量社區(qū),又能發(fā)現(xiàn)異常社區(qū)。在人工網(wǎng)絡(luò)數(shù)據(jù)集和真實網(wǎng)絡(luò)數(shù)據(jù)集上的實驗結(jié)果驗證了本文方法的魯棒性和可擴(kuò)展性,在真實屬性圖上的實驗結(jié)果表明該方法更符合現(xiàn)實復(fù)雜網(wǎng)絡(luò)特性,但在網(wǎng)絡(luò)節(jié)點結(jié)構(gòu)信息上,其未考慮社區(qū)重疊對社區(qū)檢測結(jié)果的影響,這將是下一步研究的重點。