融合節點屬性與結構信息的子空間異常社區檢測方法

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

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

0 概述

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

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

鑒于節點屬性信息相對于結構信息更能反映真實復雜網絡的特性,本文提出融合屬性和結構的子空間異常社區檢測方法(SBAM),在高質量社區定義的基礎上,設計基于子空間的社區質量評估模型,利用結構與屬性同時量化社區質量,挖掘較低分值的異常社區集合。

1 相關工作

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

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

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

本文方法利用正態性,從社區內部一致性和外部可分性上對社區質量進行評估。在結構上注重量化,由于社區之間的邊界邊會影響社區質量的正態性分數,因此本文方法融合社區內外部結構和屬性子空間,通過屬性圖的子空間與社區結構信息進行圖異常檢測。在真實數據集和人工數據集上驗證了本文方法的魯棒性和可擴展性,并且其在精確度和性能上優于現有社區檢測方法,如OddBall[1]和AMEN等,因此本文方法更適用于復雜網絡。

2 屬性子空間挖掘

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

2.1 問題定義

與傳統異常社區檢測方法不同,本文方法是在挖掘屬性子空間下對社區質量進行評估,將不同維度的重要程度屬性權重共同作為衡量社區質量的因素,消除異常社區檢測過程中僅考慮社區結構的片面性,使得挖掘到的異常社區更真實。

本文融合屬性與結構的子空間異常社區檢測框架如圖1所示,其具體步驟如下:

1)給定:帶節點屬性的社區集合C。

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

3)量化:依照定義的質量評估函數,對社區內部緊密性和外部分離性定量計算質量分數Q。

4)發現:將定量計算得到的社區質量分數升序排列,輸出質量分數較低的社區集合L。

圖1 融合屬性與結構的子空間異常社區檢測框架

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

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

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

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

(1)

(2)

對子空間進行標準化處理得到:

(3)

2.3 基于負熵加權的子空間推斷策略

利用負熵加權法確定屬性子空間,對于每一個特定社區Ci都有特定屬性權重向量wi,求解目標函數如下:

(4)

其中,ni是社區Ci中的節點個數,fvit為節點vi第t維屬性,γ是控制多維權重激勵強度的一個正參數。式(4)中第一部分是衡量社區內部的緊密程度,即社區內部節點間的距離,第二部分是負熵值。

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

(5)

2.4 子空間融合求解策略

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

(6)

3 融合節點屬性與結構信息的異常社區檢測

本節通過融合結構與屬性挖掘子空間策略,采用AMEN中的正規性分數設計思想[11]量化社區質量,通過對社區質量分數進行排序,找到分數較低的社區集合,即為檢測發現的異常社區集合。

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

社區質量評估函數與模塊度概念相似,用于量化社區質量。一個高質量的社區主要包含兩個標準:1)社區內部節點連接緊密程度和節點之間在子空間上的相似度;2)社區內節點連向外部鄰居節點的稀疏程度和內部節點與社區鄰居節點在子空間上的相異性。評估社區質量的優劣主要為:屬性相似且結構相似的節點應隸屬于同一社區,而不相似的節點應分離并隸屬于不同社區。

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

(7)

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

設圖G的兩個社區Ci和Bj均為圖G的子圖,則社區Ci的質量評估函數Q定義如下:

(8)

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

對于具有最高質量分值的社區:1)存在所有可能的內部邊緣且節點屬性和結構對相似性高,此時式(8)中的第一項最大化;2)由于社區沒有交叉邊或社區與社區之間存在的重疊邊相似性接近0,因此式(8)中的第二項可忽略。屬性圖的社區質量分數為負表示異常或質量較差,即異常社區。因此,需要極大化社區質量評估模型(式(8)),具體如下:

(9)

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

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

4 實驗結果與分析

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

4.1 實驗設置

4.1.1 數據集

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

表1 人工網絡數據集參數設置

為驗證本文方法在真實網絡上的效果,本節選取Facebook、Twitter和Google+ 3個具有真實社區的屬性網絡參數設置進行驗證,具體數據集如表2所示。其中,節點、邊、屬性是表述數據集中網絡的構建方式,節點代表網絡中的用戶,依據用戶與用戶之間的友誼關系、協從關系構建節點之間的邊,節點上附著的屬性是用戶個人信息等特征。

表2 真實網絡數據集參數設置

4.1.2 實驗基準及評價指標

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

(10)

其中,Nij是屬于真實社區i和檢測到的社區j的節點數量,Ni.是矩陣N中第i行元素的總和,N.j是矩陣N中第j列元素的總和,A表示網絡的真實劃分,B表示基于算法得到的劃分,CA是真實社區數量,CB是檢測到的社區數量。

4.2 結果分析

本節主要在人工網絡上對LFR基準網絡生成過程進行參數設置,設計在LFR基準網絡下各參數對SBAM方法的性能影響實驗,并對實驗結果進行分析。在真實網絡中,采用AMEN方法對真實網絡進行異常擾動并設計性能對比實驗。

4.2.1 人工網絡分析

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

表3 異常社區檢測方法在人工網絡數據集上的性能對比

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

圖2 節點個數和最小社區個數對異常社區檢測方法的性能影響

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

4.2.2 真實網絡分析

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

圖3表示隨著真實網絡異常擾動強度的增加,在不同數據集上,SBAM-L2方法能夠準確檢測異常社區,AMEN方法次之,但圖3不論是從屬性或者結構角度,還是從屬性融合結構的角度評估方法性能,SBAM-L2方法均為最優,其原因為SBAM-L2方法的特點是依據融合屬性和結構的信息,挖掘網絡中的子空間,實現異常社區檢測。實驗選取的真實網絡數據集Facebook、Twitter和Google+中節點與邊之間存在友誼關系或者協從關系,通過計算子空間求出社區質量分數值,而SBAM方法就是利用社區子空間結合社區結構信息得出異常社區質量分數值。

圖3 異常社區檢測方法在真實網絡數據集上擾動強度的變化情況

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

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

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

5 結束語

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