基于熵加權(quán)屬性子空間的目標(biāo)社區(qū)發(fā)現(xiàn)

劉海姣，馬慧芳,2,昌 陽(yáng),李志欣

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

0 引言

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

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

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

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

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

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

1.1 中心點(diǎn)集采集

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

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

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

(1)

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

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

(2)

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

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

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

v∈(V-Z)}

(3)

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

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

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

(4)

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

(5)

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

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

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

2.1 目標(biāo)社區(qū)質(zhì)量評(píng)估

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

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

(6)

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

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

sL(u,v)

(7)

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

(8)

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

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

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

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

續(xù)表

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

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

算法2 目標(biāo)社區(qū)更新輸入:初始目標(biāo)社區(qū)M′輸出:更新后的目標(biāo)社區(qū)M1. CN=M′; #存儲(chǔ)候選節(jié)點(diǎn)2.M=M′;#初始化目標(biāo)社區(qū)集合3.ΔfitL(M)=0,ΔfitL(M)best=0;#ΔfitL(M)記錄每次刪除節(jié)點(diǎn)時(shí)目標(biāo)社區(qū)適度值的變化,ΔfitL(M)best記錄適度值的最大變化4.Repeat5. bestNode=null;#記錄最佳刪除節(jié)點(diǎn)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é)點(diǎn)集合13.M←M/{bestNode};#更新目標(biāo)社區(qū)集合14.ΔfitL(M)best=0;15.UntilbestNode=null;#直到?jīng)]有節(jié)點(diǎn)的刪除使得目標(biāo)社區(qū)的適度值正向增加停止循環(huán)16.ReturnM;

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

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

2.3 方法擴(kuò)展

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

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

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

(9)

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

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

為了驗(yàn)證TC-AE算法的有效性和效率，在本節(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è)目標(biāo)社區(qū)劃分算法和一個(gè)典型的社區(qū)劃分算法與本文方法進(jìn)行比較。

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

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

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

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

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

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

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

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

3.2 實(shí)驗(yàn)結(jié)果及分析

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

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

3.2.1 參數(shù)分析

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

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

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

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

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

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

3.2.2 與其他算法的對(duì)比

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

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

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

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

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

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

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

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

圖 5(續(xù))

4 總結(jié)

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