劉海姣，馬慧芳,2,昌 陽,李志欣

(1. 西北師范大學(xué) 計算機科學(xué)與工程學(xué)院，甘肅 蘭州 730070；2. 桂林電子科技大學(xué) 廣西可信軟件重點實驗室, 廣西 桂林 541004；3. 廣西師范大學(xué) 廣西多源信息挖掘與安全重點實驗室，廣西 桂林 541004)

0 引言

現(xiàn)實世界中大量復(fù)雜系統(tǒng)均可以抽象為復(fù)雜網(wǎng)絡(luò)模型，如社交網(wǎng)絡(luò)、交通網(wǎng)絡(luò)、生物網(wǎng)絡(luò)等。網(wǎng)絡(luò)的研究具有重要意義。例如，對社會網(wǎng)絡(luò)結(jié)構(gòu)的清晰認識，可以幫助人們更好地理解各種社會現(xiàn)象[1-2]。隨著社會的不斷發(fā)展，網(wǎng)絡(luò)中的社區(qū)發(fā)現(xiàn)已經(jīng)引起了廣泛的關(guān)注。特別是目標社區(qū)發(fā)現(xiàn)已成為近年來的研究熱點。目標社區(qū)發(fā)現(xiàn)是指挖掘與用戶偏好一致的節(jié)點所構(gòu)成的社區(qū)。該社區(qū)內(nèi)部連接緊密，且與外部分離較好。目標社區(qū)發(fā)現(xiàn)在科學(xué)研究、商業(yè)推廣等領(lǐng)域有了越來越多的應(yīng)用[3]。例如，化妝品銷售經(jīng)理可能更關(guān)注于社交網(wǎng)絡(luò)中的某個社區(qū)。該社區(qū)成員具有一定的年齡、性別以及收入水平，經(jīng)理可以向社區(qū)中的成員進行推薦并期望通過口碑傳播的方式推廣其產(chǎn)品；銷售體育用品的市場營銷經(jīng)理需要挖掘有體育用品需求的用戶所在的社區(qū)。然后，根據(jù)社區(qū)中用戶的需求向少數(shù)成員提供試用產(chǎn)品，以期待產(chǎn)品在社區(qū)中受歡迎。

現(xiàn)有的社區(qū)發(fā)現(xiàn)方法大致可分為以下兩種: 一種是基于無監(jiān)督聚類技術(shù)，另一種是基于半監(jiān)督聚類技術(shù)[4]。大多數(shù)采用無監(jiān)督聚類技術(shù)的社區(qū)發(fā)現(xiàn)方法中，在所有可用屬性視為同等重要，或者采用無監(jiān)督技術(shù)來確定屬性權(quán)重。近年來具有代表性的工作包括: Chen等[5]提出了一種子空間圖—結(jié)構(gòu)匹配尋蹤算法，用于解決不同得分函數(shù)和拓撲約束的問題。Gunnemann等[6]提出一種無監(jiān)督的譜權(quán)重聚類方法用于檢測每個社區(qū)的相關(guān)屬性的子集，并采用譜聚類來學(xué)習(xí)社區(qū)結(jié)構(gòu)。但是，基于無監(jiān)督聚類技術(shù)的社區(qū)發(fā)現(xiàn)方法未能考慮先驗信息。與上述方法不同，半監(jiān)督聚類技術(shù)則考慮了用戶給定的約束。Li等[7]提出了一種元路徑圖聚類框架(VEPathCluster)，該框架將元路徑節(jié)點—中心聚類和元路徑邊-中心聚類相結(jié)合。Yang等[8]提出一種基于模塊度的深度學(xué)習(xí)社區(qū)檢測方法，并將該方法推廣到一種半監(jiān)督的社區(qū)檢測算法中。目標社區(qū)發(fā)現(xiàn)是一種新的半監(jiān)督局部聚類方法，挖掘到的社區(qū)內(nèi)部節(jié)點受用戶偏好控制。Perozzi 等[3]提出了一種面向用戶的屬性圖挖掘方法(FocusCO)。該方法允許用戶通過提供一組樣本節(jié)點來引導(dǎo)社區(qū)，所提供的樣本節(jié)點被認為是相似的，并且與用戶感興趣的社區(qū)節(jié)點相似。FocusCO沒有說明需要多少示例節(jié)點，但明確指出需要兩個以上的樣例節(jié)點。Wu等[9]提出了一種在目標子空間中挖掘目標社區(qū)集合的方法，該方法根據(jù)用戶提供的兩個樣本節(jié)點擴展到一組樣本節(jié)點，從中推導(dǎo)出目標屬性權(quán)重并挖掘目標社區(qū)的集合。然而，現(xiàn)有的半監(jiān)督目標社區(qū)聚類技術(shù)雖然考慮了用戶的偏好，但在聚類過程中僅考慮了節(jié)點的屬性信息或只利用節(jié)點的部分屬性[10]。

針對以上問題，本文面向用戶提出一種基于熵加權(quán)屬性子空間的目標社區(qū)發(fā)現(xiàn)(Target Community Detection Based on Attribute Subspace with Entropy Weighting, i.e.TC-AE )方法，挖掘與用戶偏好相關(guān)的社區(qū)?？紤]到用戶提供的樣例節(jié)點潛在的屬于目標社區(qū)。首先，從屬性和結(jié)構(gòu)兩個方面綜合考慮節(jié)點間的相似度，利用樣例節(jié)點及其鄰居擴展得到目標社區(qū)中心點集；其次，在中心點集上，設(shè)計一種熵加權(quán)屬性子空間權(quán)重計算方法，最小化社區(qū)內(nèi)部節(jié)點間的距離，并最大化負熵值來刺激更多的屬性。得到目標社區(qū)的屬性子空間權(quán)重，既可以確定目標社區(qū)的屬性子空間，又可以避免用稀疏數(shù)據(jù)通過少數(shù)屬性識別社區(qū)的問題，從而有助于精準的確定目標社區(qū)；再次，利用目標社區(qū)的屬性子空間權(quán)重，基于節(jié)點的屬性和結(jié)構(gòu)相似度重寫網(wǎng)絡(luò)中邊的權(quán)重；最后，定義社區(qū)適度函數(shù)并結(jié)合重寫后網(wǎng)絡(luò)中邊的權(quán)重改進社區(qū)適度函數(shù)，以中心節(jié)點集為核心，挖掘基于用戶偏好的內(nèi)部連接緊密且與外部分離較好目標社區(qū)。此外，該方法可以擴展到網(wǎng)絡(luò)中多個社區(qū)發(fā)現(xiàn)任務(wù)中。在人工數(shù)據(jù)和真實網(wǎng)絡(luò)數(shù)據(jù)上的實驗結(jié)果驗證了本文所提算法的有效性和效率以及應(yīng)用價值?；陟丶訖?quán)屬性子空間的目標社區(qū)發(fā)現(xiàn)框架圖如圖1所示。

1 屬性子空間權(quán)重挖掘

對于一個社區(qū)而言，每個屬性對社區(qū)均有貢獻，但貢獻不同，部分貢獻較高的屬性構(gòu)成屬性子空間。在社區(qū)發(fā)現(xiàn)過程中為每個屬性分配一個權(quán)重，以衡量屬性在該社區(qū)中的貢獻，貢獻越大則子空間所對應(yīng)的屬性權(quán)重值越大。因此，對于目標社區(qū)發(fā)現(xiàn)而言首要任務(wù)是捕獲基于屬性子空間的屬性權(quán)重即屬性子空間權(quán)重，然后在屬性子空間權(quán)重的指導(dǎo)下挖掘目標社區(qū)。本文首先從屬性和結(jié)構(gòu)兩個方面綜合考慮節(jié)點間的相似度，基于用戶給定的樣例節(jié)點挖掘目標社區(qū)中心點集，然后在目標社區(qū)中心點集指導(dǎo)下推斷該社區(qū)的屬性子空間權(quán)重。

圖1 熵加權(quán)屬性子空間的目標社區(qū)發(fā)現(xiàn)框架圖

1.1 中心點集采集

中心點集的采集是為了挖掘目標社區(qū)的屬性子空間權(quán)重。對于目標社區(qū)，其內(nèi)部節(jié)點只在對應(yīng)屬性子空間權(quán)重下彼此相似且與外部節(jié)點不相似。本文結(jié)合節(jié)點間的屬性相似度與結(jié)構(gòu)相似度利用用戶給定的樣例節(jié)點挖掘目標社區(qū)中心點集。

定義1(節(jié)點屬性相似度): 節(jié)點u和v的屬性相似度s(u,v)定義如式(1)所示。

s(u,v)=exp(-‖f(u)-f(v)‖2)

(1)

其中，‖f(u)-f(v)‖2為節(jié)點u，v屬性列向量差值二范式，節(jié)點間屬性相似性介于0和1之間。

定義2(節(jié)點結(jié)構(gòu)相似度): 節(jié)點u和v的結(jié)構(gòu)相似度σ(u,v)定義如式(2)所示[11]。

(2)

其中，N(u)={v∈V|u,v之間有邊}∪{u}，d(u)=|N(u)|-1。直觀地說，對于兩個節(jié)點，其共同鄰居節(jié)點越多，結(jié)構(gòu)相似度越大。任意兩個節(jié)點間的結(jié)構(gòu)相似度介于0和1之間。

對于給定圖G={V,E,F}，由于用戶給定的樣例節(jié)點個數(shù)有限，不能夠提供更為有效的信息。所以，以用戶所給定的樣例節(jié)點作為目標社區(qū)中心點擴展得到中心點集。具體考慮到與中心點來自同一社區(qū)的鄰居節(jié)點，應(yīng)該在屬性與結(jié)構(gòu)上彼此相似。首先初始化目標社區(qū)中心點集Z={z}，中心點集計算如式(3)所示。

Z={v|{(s(z,v)+σ(z,v))/2>β},

v∈(V-Z)}

(3)

其中，β為相似度閾值。然后，根據(jù)式(3)擴展得到社區(qū)中心點集Z={z1,z2,…,zc}。其中，c為中心點集中節(jié)點的個數(shù)。

1.2 基于熵加權(quán)的屬性子空間權(quán)重挖掘

對于目標社區(qū)中心點集，計算使它們彼此相似的屬性權(quán)重，則該屬性權(quán)重就是能夠使得社區(qū)中的內(nèi)部節(jié)點基于屬性彼此相似且與外部節(jié)點不相似。換句話說，該權(quán)重應(yīng)該使中心點集中節(jié)點彼此之間基于屬性有一個很小的距離。與文獻[12]迭代的計算每個簇的屬性權(quán)重不同，本文在不需要迭代優(yōu)化的情況下，定義目標社區(qū)屬性子空間權(quán)重，用目標函數(shù)計算屬性子空間權(quán)重向量。目標函數(shù)定義如式(4)所示。

(4)

通過對F(L)最小化，求得式(5):

(5)

推導(dǎo)過程詳見附錄。

2 社區(qū)發(fā)現(xiàn)

推斷出目標社區(qū)的屬性子空間權(quán)重L=[l1,l2,…,lr]后，挖掘中心點集及權(quán)重所對應(yīng)的目標社區(qū)。本節(jié)以中心點集Z作為目標社區(qū)的種子，調(diào)整種子以找到基于屬性子空間權(quán)重內(nèi)部連接緊密且與外部有較好分離性的目標社區(qū)。值得注意的是，在推斷目標社區(qū)時是局部提取的，而不是劃分整個圖。

2.1 目標社區(qū)質(zhì)量評估

為了衡量社區(qū)內(nèi)節(jié)點的緊密程度，以及與外部節(jié)點的分離程度，本文定義了適度函數(shù)[2]作為一個局部的質(zhì)量函數(shù)用來評估目標社區(qū)的內(nèi)部緊密性和外部可分離性。

定義3(社區(qū)適度): 社區(qū)M的適度被定義如式(6)所示。

(6)

其中，invol(M)=∑vi,vj∈Maij表示社區(qū)節(jié)點內(nèi)部度之和，vol(M)=∑vi∈M,vj∈Vaij表示社區(qū)節(jié)點度之值，當社區(qū)具有較多的內(nèi)部邊，較少的交叉邊時，適度值較大。

為了評估目標社區(qū)質(zhì)量，將目標社區(qū)基于屬性子空間權(quán)重下的屬性和結(jié)構(gòu)相似度設(shè)置為邊權(quán)值，然后相應(yīng)地修改適度函數(shù)來重新衡量網(wǎng)絡(luò)。基于目標社區(qū)屬性子空間權(quán)重L，節(jié)點屬性相似度根據(jù)式(1)被更新為如式(7)所示。

sL(u,v)

(7)

在重寫權(quán)重的網(wǎng)絡(luò)中，如果兩個內(nèi)部節(jié)點在屬性和結(jié)構(gòu)上更為相似，則它們之間的邊將得到一個較大的權(quán)重。重寫權(quán)重的社區(qū)適度函數(shù)被定義如式(8)所示。

(8)

社區(qū)適度可以評估目標社區(qū)的質(zhì)量。當社區(qū)擁有較多的內(nèi)部邊，并且社區(qū)內(nèi)部節(jié)點與外部節(jié)點之間的交叉邊較少，與此同時基于推斷的目標權(quán)重，社區(qū)內(nèi)部節(jié)點間具有更高的屬性和結(jié)構(gòu)相似度時，目標社區(qū)的適度值較大。

2.2 目標社區(qū)發(fā)現(xiàn)

確定了目標社區(qū)中心點集及對應(yīng)的屬性子空間權(quán)重后，從圖G挖掘中心點集及屬性子空間權(quán)重所在的目標社區(qū)。先以中心點集作為目標社區(qū)的種子，再擴展種子以找到目標社區(qū)。算法1中描述了初始目標社區(qū)的挖掘過程。

算法1 初始目標社區(qū)挖掘輸入:屬性圖G={V,E,F},中心節(jié)點集Z,屬性子空間權(quán)重L輸出:初始目標社區(qū)集合M′1. CN=?;#存儲候選節(jié)點2. M′=Z;#初始化初始目標社區(qū)集合3.CN={v|vi和v之間有邊,vi∈Z,v?Z∧v∈V};#將集合中現(xiàn)有節(jié)點的鄰居節(jié)點作為候選節(jié)點4.ΔfitL(M′)=0,ΔfitL(M′)best=0;#ΔfitL(M′)記錄每次添加節(jié)點時目標社區(qū)適度值的變化ΔfitL(M′)best記錄適度值的最大變化5.Repeat6. bestNode=null;#最佳候選節(jié)點7. Foreachv∈CNdo8. ΔfitL(M′)=fitL(M′,add(v))-fitL(M′);#節(jié)點v加入社區(qū)時適度值得變化9. IfΔfitL(M′)>ΔfitL(M′)best≥0

續(xù)表

本文采用貪婪算法對目標社區(qū)進行局部調(diào)整，在每次迭代中，計算所有可能調(diào)整適度變化的操作，選擇適度正變化最大的節(jié)點加入目標社區(qū)。迭代繼續(xù)，直到?jīng)]有節(jié)點的加入導(dǎo)致適度發(fā)生正的改變，社區(qū)的適度值不再增加。算法1中，第8行(M′, add(v))表示將節(jié)點v加入社區(qū)M′的操作。

節(jié)點的添加是基于一種改進的最優(yōu)搜索策略，每次添加的節(jié)點都是當前最優(yōu)的選擇，在算法2中采用了追溯策略檢查是否有節(jié)點的移除使得社區(qū)的適度正向增加。

算法2 目標社區(qū)更新輸入:初始目標社區(qū)M′輸出:更新后的目標社區(qū)M1. CN=M′; #存儲候選節(jié)點2.M=M′;#初始化目標社區(qū)集合3.ΔfitL(M)=0,ΔfitL(M)best=0;#ΔfitL(M)記錄每次刪除節(jié)點時目標社區(qū)適度值的變化,ΔfitL(M)best記錄適度值的最大變化4.Repeat5. bestNode=null;#記錄最佳刪除節(jié)點6. Foreachv∈CNdo7. ΔfitL(M)=fitL(M,remove(v))-fitL(M);8. IfΔfitL(M)>ΔfitL(M)best≥0;9. ΔfitL(M)best=ΔfitL(M);10. bestNode=v;11. Endfor12.CN←CN/{bestNode};#更新候選節(jié)點集合13.M←M/{bestNode};#更新目標社區(qū)集合14.ΔfitL(M)best=0;15.UntilbestNode=null;#直到?jīng)]有節(jié)點的刪除使得目標社區(qū)的適度值正向增加停止循環(huán)16.ReturnM;

算法2中第7行(M, remove(v))表示將節(jié)點v從M中刪除。

社區(qū)的適度值介于0到1之間，每次選擇節(jié)點加入社區(qū)或者刪除社區(qū)中的節(jié)點都能使得目標社區(qū)的適度值正向增加，因此算法的收斂性得到保證。

2.3 方法擴展

本文所提出的方法不僅適用于基于用戶的目標社區(qū)發(fā)現(xiàn)任務(wù)，同樣適用于網(wǎng)絡(luò)中多個社區(qū)的挖掘以及離群點檢測任務(wù)。挖掘的同一社區(qū)的節(jié)點之間彼此相似而不同社區(qū)的節(jié)點之間相似度較低。

首先，在節(jié)點集中隨機選取一個節(jié)點v作為第一個社區(qū)的中心z1，利用基于熵加權(quán)屬性子空間權(quán)重的目標社區(qū)發(fā)現(xiàn)方法，挖掘得到以z1為中心的屬性權(quán)重L1及社區(qū)M1。其次，從屬性和結(jié)構(gòu)兩個方面綜合考慮節(jié)點間的相似度，基于改進的K-medoid算法[13]計算得到下一個社區(qū)中心點，利用得到的社區(qū)中心點挖掘?qū)?yīng)社區(qū)。重復(fù)迭代，直到無法得到滿足條件的新的中心點。

對于給定圖G={V,E,F}，先初始化社區(qū)集合K=?，離群點集合C=?，在節(jié)點集中隨機選取第一個點v作為第一個社區(qū)的中心z1，Z={z1}，V=V-{z1}。利用基于熵加權(quán)屬性子空間的目標社區(qū)發(fā)現(xiàn)方法得到z1所在的社區(qū)M1V，且K被更新為K=K{M1}。再根據(jù)式(9)選取G中與集合K所包含得社區(qū)中的節(jié)點基于屬性和結(jié)構(gòu)最大相似度最小的節(jié)點作為下一個社區(qū)中心點，如式(9)所示。

(9)

其中，zi為第i個社區(qū)的中心，α為決定社區(qū)中心個數(shù)的閾值，若α越大則得到的社區(qū)中心個數(shù)越多得到的社區(qū)越多。不斷重復(fù)直到V中無滿足式(9)的點時結(jié)束，得到的社區(qū)中心為Z={z1,z2,…,zk}，社區(qū)集合K={M1,M2,…,Mk}以及所對應(yīng)的屬性子空間權(quán)重L={L1,L2,…,Lk}，k為社區(qū)的個數(shù)，孤立點集合C=V-M。

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

為了驗證TC-AE算法的有效性和效率，在本節(jié)中，分別在人工數(shù)據(jù)集和真實數(shù)據(jù)集上設(shè)計了兩組實驗。首先，對實驗所用的人工數(shù)據(jù)集和真實數(shù)據(jù)集進行描述；其次，觀察不同β和γ的參數(shù)值對實驗結(jié)果的影響，選擇適宜的參數(shù)；最后，選取兩個目標社區(qū)劃分算法和一個典型的社區(qū)劃分算法與本文方法進行比較。

3.1 數(shù)據(jù)描述

3.1.1 人工數(shù)據(jù)集

本節(jié)生成了具有不同節(jié)點數(shù)目社區(qū)的人工網(wǎng)絡(luò)，這些社區(qū)內(nèi)部節(jié)點之間基于屬性相似且彼此連接緊密。人工網(wǎng)絡(luò)生成算法是基于人工分區(qū)模型[14]。簡單地說，給定每個集群中所需的節(jié)點數(shù)，通過分區(qū)約束將鄰接矩陣分割成塊。對于每一個塊Bi j，選擇一個概率pi j，除對角線外，使用隨機繪制過程分配一個1，即一條可能存在的邊，其余為0。換句話說，pi j衡量了每個區(qū)塊的密度。對角線上的塊構(gòu)成實際的社區(qū)，非對角線塊產(chǎn)生社區(qū)之間的交叉邊。本文設(shè)定pi j=0.35，0.10

然后，對生成的社區(qū)分配一個不相同的屬性子集(子空間)或不分配任何屬性。值得注意的是，在現(xiàn)實世界的圖中，每個社區(qū)中的成員基于多個屬性彼此相似。對于每個帶有屬性子空間的社區(qū)，其節(jié)點基于分配的屬性子集中的每個屬性i，屬性值fi從均值i∈[0,1]和方差σ=0.001的正態(tài)分布N(μi,σ)中提取，使得社區(qū)的節(jié)點在對應(yīng)的屬性子空間上“一致”。其余的屬性是從方差更大的正態(tài)分布N(0,1)中提取的。對于沒有分配屬性子空間的社區(qū)其節(jié)點屬性值均從方差大的正態(tài)分布N(0,1)中提取的。

本文共生成了6個內(nèi)部節(jié)點基于屬性子空間彼此相似且連接緊密的社區(qū)(社區(qū)1—社區(qū)6)和1個不分配任何屬性子空間的社區(qū)(社區(qū)7)，總共有7個社區(qū)。實驗利用給定的來自社區(qū)1的樣例節(jié)點挖掘社區(qū)1。人工網(wǎng)絡(luò)數(shù)據(jù)集如表1所示。

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

3.1.2 真實數(shù)據(jù)集

選取4個真實世界中的屬性網(wǎng)絡(luò)進行驗證。Polbooks(1)http://www-personal.umich.edu/～mejn/netdata/是從Amazon上銷售的與美國政治相關(guān)書籍頁面上建立起來的網(wǎng)絡(luò)。節(jié)點代表在Amazon在線書店上銷售的美國政治相關(guān)圖書，邊代表一定數(shù)量的讀者同時購買了這兩本圖書。網(wǎng)絡(luò)中的節(jié)點分成為3個社區(qū): 分別是“自由派”“保守派”和“中間派”。這些派別的劃分是由Mark Newman根據(jù)Amazon上對于圖書觀點以及評價情況的人工分析得到的。Enron Mail(2)http://bailando.sims.berkeley.edu/enron/是目前在電子郵件相關(guān)研究中使用最多的公開數(shù)據(jù)集，其郵件數(shù)據(jù)是安然公司150位高級管理人員的來往郵件。郵件按主題分為13個類。DBLP(3)https://dblp.uni-trier.de/xml/是計算機領(lǐng)域作者的合著網(wǎng)絡(luò)，以作者與作者合著的國際期刊和會議等公開發(fā)表的論文為邊構(gòu)建關(guān)系網(wǎng)絡(luò)。DBLP集成元素不多，只有最基本的論文題目、時間、作者、發(fā)表類型及期刊或會議名稱等等，包括國際期刊和會議等公開發(fā)表的論文。DBLP中以作者的主要研究方向所在的十個領(lǐng)域為社區(qū)劃分標準。LastFM(4)http://www.dtic.upf.edu/～ocelma/MusicRecommendationDataset/lastfm-360K.html是用戶收聽音樂的信息，具體包括雙向的朋友關(guān)系、藝術(shù)家、用戶收聽藝術(shù)家信息、用戶對藝術(shù)家的標簽信息、藝術(shù)家標簽信息。LastFM中的成員被劃分到該成員收聽最多的音樂風(fēng)格，例如，house、Britpop、Trip-Hop、Gangsta Rap等。預(yù)處理后的真實數(shù)據(jù)信息詳見表2。

3.2 實驗結(jié)果及分析

為了評價挖掘出的目標社區(qū)是否符合“基于用戶偏好的內(nèi)部連接緊密且與外部分離較好”，本章采用兩種評價指標。一是，標準化互信息(NMI)均值[15]，即同一數(shù)據(jù)集中運行100次的NMI的平均值，度量了算法結(jié)果與標準結(jié)果之間的相似性。該相似性越高，NMI值越接近1；反之，則NMI值接近0。二是目標社區(qū)的模塊度Q[16]，反映了社區(qū)的一致程度。模塊度越大，則表明社區(qū)劃分效果越好。Q值的范圍在[-0.5,1)。研究表明當Q值在0.3～0.7之間時，說明聚類的效果較好。NMI與Q作為后續(xù)評價指標一并用于實驗效果的綜合評價[17]。

表2 真實數(shù)據(jù)集

3.2.1 參數(shù)分析

式(3)中，相似度閾值β作為選取中心點集時，鄰居節(jié)點與樣例節(jié)點間相似度的最低標準，在目標社區(qū)發(fā)現(xiàn)中有著極高的重要性。為選擇合適的閾值，將β作為自變量，給定不同的β觀察標準化互信息NMI均值和模塊度Q的變化。該實驗在5種數(shù)據(jù)集上進行。如圖2所示，x軸為β在0到1之間的不同取值，y軸為NMI均值或模塊度Q的變化情況。

圖2 參數(shù)β對NMI均值和模塊度Q的影響

可以看到在β=0.75時，五個數(shù)據(jù)集上的NMI均值都較高，即將參數(shù)β設(shè)定為0.75可使得算法結(jié)果與標準結(jié)果之間的相似度趨于最大化，該數(shù)值也將用作后續(xù)實驗中參數(shù)的取值。

根據(jù)式(2)的目標函數(shù)可以知道γ是一個正調(diào)節(jié)因子，用于控制多維度權(quán)重的一個正參數(shù)激勵強度。本小節(jié)將通過實驗對參數(shù)進行調(diào)節(jié)，以確定最優(yōu)的實驗參數(shù)。將參數(shù)γ作為自變量，給定不同的參數(shù)值觀察NMI均值的變化。通過比對不同的參數(shù)下的NMI均值，取使得目標社區(qū)的NMI均值最大的參數(shù)值作為給定參數(shù)，該實驗分別在人工數(shù)據(jù)集和真實數(shù)據(jù)集上進行。如圖3所示，x軸為參數(shù)γ在0到1之間的不同取值，y軸為NMI均值或模塊度Q的變化情況。

圖3 參數(shù)γ的對NMI均值和模塊度Q的影響

當γ在[0.4,0.7]時，五個數(shù)據(jù)集上的NMI均值變化較小，因此γ的值設(shè)定為0.5，該數(shù)值也將用作后續(xù)實驗中參數(shù)γ的取值。

3.2.2 與其他算法的對比

選取兩個目標社區(qū)劃分算法FocusCO、TSCM和一個經(jīng)典的社區(qū)發(fā)現(xiàn)算法Girvan-Newman(G -N)[18]與本文方法分別從發(fā)現(xiàn)的目標社區(qū)質(zhì)量和時間兩方面進行比較。其中，F(xiàn)ocusCO創(chuàng)新的提出了以用戶為中心的屬性圖目標社區(qū)發(fā)現(xiàn)方法；TSCM基于目標子空間挖掘目標社區(qū)集合；G -N作為經(jīng)典的社區(qū)發(fā)現(xiàn)算法不執(zhí)行目標社區(qū)劃分，則測量該方法返回的最佳社區(qū)與標準社區(qū)之間的相似度。因此，本文選取上述3種方法作為實驗參照，各算法對比如表3所示。

表3 與現(xiàn)存方法對比

在人工數(shù)據(jù)集上，分別對4種方法進行實驗，并對實驗結(jié)果進行綜合評估。NMI均值和模塊度Q的值越大，則表明社區(qū)劃分效果越好。

圖4展示了本文所提出的算法和所選對比算法在NMI均值和模塊度Q上的比較。由圖可知，在人工數(shù)據(jù)集上，本文所提出的算法挖掘的目標社區(qū)NMI均值最高與標準社區(qū)最為相似，效率最高；FocusCO與TSCM算法挖掘的目標社區(qū)NMI均值較為接近且均低于本文所提出算法；G-N算法效率最低。

為了進一步驗證實驗效果，本節(jié)在4個真實數(shù)據(jù)集上與3個對比算法進行實驗，利用NMI均值和模塊度Q值對實驗結(jié)果進行綜合評估。

圖5展示了本文所提出的算法和對比算法在NMI均值和模塊度Q上的比較。由圖可知，在4種數(shù)據(jù)集上，本文所提出的算法挖掘的目標社區(qū)NMI均值在所有真實數(shù)據(jù)集較為穩(wěn)定且最高。如圖5(a)所示，在Polbooks數(shù)據(jù)集上，TW-EC挖掘的目標社區(qū)模塊度Q略低于TSCM。由算法可知，在挖掘目標社區(qū)時，同時考慮節(jié)點間的加權(quán)屬性相似度和結(jié)構(gòu)相似度并更新節(jié)點間邊的權(quán)重信息。在以適度函數(shù)作為衡量標準擴展中心點集時，降低了部分權(quán)重值較低的邊對于目標社區(qū)的影響。因而，模塊度Q略低于TSCM。

圖4 4種算法在人工數(shù)據(jù)集上的結(jié)果對比

圖5 4種算法在真實數(shù)據(jù)集上的結(jié)果對比

圖 5(續(xù))

4 總結(jié)

針對現(xiàn)有的大多數(shù)社區(qū)發(fā)現(xiàn)算法未能充分考慮用戶的偏好，本文提出一種基于熵加權(quán)屬性子空間的目標社區(qū)發(fā)現(xiàn)方法，挖掘與用戶偏好相關(guān)的社區(qū)。該方法利用用戶所提供的樣例節(jié)點挖掘目標社區(qū)的種子集合，基于種子集合推斷能夠使得目標社區(qū)內(nèi)部節(jié)點基于屬性彼此相似的屬性子空間權(quán)重；然后，結(jié)合節(jié)點間的加權(quán)屬性相似性和結(jié)構(gòu)相似性擴展中心點集得到目標社區(qū)。解決了傳統(tǒng)社區(qū)發(fā)現(xiàn)算法忽略節(jié)點的屬性權(quán)重或只利用部分屬性的問題。最后，分別在人工數(shù)據(jù)集和真實數(shù)據(jù)集上實驗，證明了本文所提算法的效率和有效性。