融合節(jié)點(diǎn)屬性與結(jié)構(gòu)信息的子空間異常社區(qū)檢測(cè)方法

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

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

0 概述

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

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

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

1 相關(guān)工作

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

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

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

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

2 屬性子空間挖掘

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

2.1 問題定義

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

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

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

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

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

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

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

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

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

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

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

(1)

(2)

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

(3)

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

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

(4)

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

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

(5)

2.4 子空間融合求解策略

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

(6)

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

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

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

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

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

(7)

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

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

(8)

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

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

(9)

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

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

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

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

4.1 實(shí)驗(yàn)設(shè)置

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

由于LFR基準(zhǔn)網(wǎng)絡(luò)[28]具有與真實(shí)網(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é)點(diǎn)個(gè)數(shù)n,平均節(jié)點(diǎn)度davg,最大節(jié)點(diǎn)度dmax,最小社區(qū)成員個(gè)數(shù)cmin,最大社區(qū)成員個(gè)數(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é)點(diǎn),即數(shù)值、二進(jìn)制和分類。附加的屬性向量由4個(gè)參數(shù)控制,即屬性總個(gè)數(shù)r、屬性子空間個(gè)數(shù)k、異常社區(qū)數(shù)量l和相似概率p。此外,為選擇合適的基準(zhǔn)精確評(píng)估各對(duì)比方法的有效性和效率。在設(shè)定實(shí)驗(yàn)最佳參數(shù)時(shí),分別對(duì)n、μ、cmin、r、k和p進(jìn)行 600組基準(zhǔn)測(cè)試,實(shí)驗(yàn)結(jié)果中的最佳參數(shù)設(shè)置如表1所示。

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

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

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

4.1.2 實(shí)驗(yàn)基準(zhǔn)及評(píng)價(jià)指標(biāo)

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

(10)

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

4.2 結(jié)果分析

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

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

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

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

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

圖2 節(jié)點(diǎn)個(gè)數(shù)和最小社區(qū)個(gè)數(shù)對(duì)異常社區(qū)檢測(cè)方法的性能影響

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

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

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

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

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

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

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

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

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

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