面向?qū)傩跃W(wǎng)絡(luò)的可重疊多向譜社區(qū)檢測算法*

李青青，馬慧芳,2，吳玉澤，劉海姣

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

1 引言

在網(wǎng)絡(luò)分析中，社區(qū)檢測是最重要和最基本的任務(wù)之一，常被認(rèn)為是圖聚類問題，應(yīng)用于合著關(guān)系網(wǎng)絡(luò)和細(xì)分市場識(shí)別[1]等領(lǐng)域。在許多應(yīng)用中，網(wǎng)絡(luò)中節(jié)點(diǎn)附有屬性信息(如合著關(guān)系網(wǎng)絡(luò)中作者的研究領(lǐng)域、發(fā)表論文篇數(shù)等信息)，且節(jié)點(diǎn)可屬于多個(gè)社區(qū)(如合著關(guān)系網(wǎng)絡(luò)中作者致力于多個(gè)研究領(lǐng)域)。隨著網(wǎng)絡(luò)分析研究的深入，現(xiàn)已有大量有效的社區(qū)檢測技術(shù)被提出。然而多數(shù)社區(qū)檢測方法并沒有考慮節(jié)點(diǎn)的附帶屬性等信息，并且已有可重疊的社區(qū)檢測方法往往難以定位離群點(diǎn)。在針對屬性網(wǎng)絡(luò)的社區(qū)檢測方法中，譜算法[2]是流行的社區(qū)檢測算法之一，具有實(shí)現(xiàn)簡單的優(yōu)勢且通常優(yōu)于傳統(tǒng)的社區(qū)檢測算法。

傳統(tǒng)譜算法主要針對結(jié)構(gòu)圖聚類，且節(jié)點(diǎn)隸屬于多個(gè)社區(qū)的信息被忽略，影響社區(qū)檢測的結(jié)果。近年來的譜算法對傳統(tǒng)譜算法進(jìn)行了改進(jìn)，可以歸納為以下兩方面：一是面向?qū)傩跃W(wǎng)絡(luò)的不可重疊譜社區(qū)檢測方法，其主要思想是綜合考慮網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和節(jié)點(diǎn)附著的屬性信息，使用歸一化拉普拉斯矩陣特征向量的譜算法。其中具有代表性的不可重疊社區(qū)檢測算法有，Jia等人[3]將屬性的重要性與信息熵相結(jié)合來選擇合適的屬性，并引入屬性約簡方法改進(jìn)譜聚類，提出了NRSR-SC(Spectral Clustering based on Neighborhood Rough Sets Reduction)算法。Bonald等人[4]考慮網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)并結(jié)合屬性信息分配給節(jié)點(diǎn)的權(quán)值，量化了節(jié)點(diǎn)間的相對重要性，這種譜嵌入是基于適當(dāng)?shù)睦绽棺儞Q的第一特征向量。盡管上述算法在效率和精度方面均有提升，但是隨著現(xiàn)實(shí)世界對網(wǎng)絡(luò)研究的深入，發(fā)現(xiàn)社區(qū)之間存在的自然重疊現(xiàn)象不容忽視。面向?qū)傩跃W(wǎng)絡(luò)的可重疊社區(qū)檢測方法結(jié)合了網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和節(jié)點(diǎn)屬性的相似度，綜合考量將信息映射成特征值與特征向量的方式。如Goyal等人[5]使用譜聚類算法解決社區(qū)檢測問題，設(shè)計(jì)了更快速的譜聚類近似算法。Li等人[6]針對網(wǎng)絡(luò)收斂特性，提出基于節(jié)點(diǎn)收斂度的重疊社區(qū)檢測算法SCNCD(Spectral Clustering based on Node Convergence Degree)。該算法同時(shí)考慮節(jié)點(diǎn)的局部和全局信息，利用改進(jìn)的PageRank算法得到全局網(wǎng)絡(luò)中各節(jié)點(diǎn)的重要性，并結(jié)合局部網(wǎng)絡(luò)信息度量結(jié)構(gòu)的收斂程度，通過譜聚類來識(shí)別重疊群落。盡管這類工作充分考慮了網(wǎng)絡(luò)中的信息并可用于可重疊的社區(qū)檢測任務(wù)中，但仍然無法基于譜算法檢測出網(wǎng)絡(luò)中的離群點(diǎn)，也無法控制重疊程度，且具有社區(qū)劃分?jǐn)?shù)量限制的局限性。

針對以上問題，本文從網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和屬性兩個(gè)角度出發(fā)，設(shè)計(jì)了面向?qū)傩跃W(wǎng)絡(luò)的可重疊多向譜社區(qū)檢測算法OMSCD(Overlapping Multiway Spectral Community Detection)。該算法可將網(wǎng)絡(luò)劃分成任意數(shù)量的社區(qū)并有效發(fā)現(xiàn)離群點(diǎn)。首先，從結(jié)構(gòu)和屬性兩方面綜合考慮，基于結(jié)合結(jié)構(gòu)和屬性信息的計(jì)算加權(quán)模塊度設(shè)計(jì)了最大化到向量分區(qū)的節(jié)點(diǎn)映射方法；其次，考慮簇中心向量的初始選擇對于社區(qū)檢測結(jié)果的影響，給出簇中心向量的初始選擇策略，并將其融合在面向?qū)傩跃W(wǎng)絡(luò)的重疊度和離群度制約中，實(shí)現(xiàn)具有離群點(diǎn)的可重疊社區(qū)的發(fā)現(xiàn)；再次，設(shè)計(jì)節(jié)點(diǎn)分配策略，將節(jié)點(diǎn)分配給與其簇中心向量具有最高內(nèi)積的社區(qū)；最后，通過節(jié)點(diǎn)隸屬社區(qū)的情況，高效地在屬性網(wǎng)絡(luò)中檢測出內(nèi)部結(jié)構(gòu)緊密、外部連接稀疏、可重疊和具有離群點(diǎn)的社區(qū)。將本文算法應(yīng)用于真實(shí)網(wǎng)絡(luò)中，實(shí)驗(yàn)結(jié)果表明，即使是在社區(qū)規(guī)模不平衡的情況下，本文算法也具有較好的性能，從而驗(yàn)證了本文算法的有效性和效率。

2 基礎(chǔ)知識(shí)

2.1 問題定義

給定屬性圖G=(V,E,F)，其中V={vi}i=1,…,n表示圖中節(jié)點(diǎn)集合；E={(vi,vj)|vi,vj∈V}表示邊集且|E|=m。G的拓?fù)浣Y(jié)構(gòu)記作鄰接矩陣A，若(vi,vj)∈E，則Aij=1；否則Aij=0。F={f1,f2,…,fd}是圖中屬性的集合。fvi=[fvi1,fvi2,…,fvid]T是節(jié)點(diǎn)vi∈V的屬性向量。構(gòu)建加權(quán)鄰接矩陣Aw，其元素定義如下：

(1)

此外，為了描述清晰起見，本文涉及到的常用符號(hào)定義總結(jié)如表1所示。

2.2 加權(quán)模塊度

模塊度常被用來衡量社區(qū)劃分質(zhì)量，對于無向無權(quán)圖，表示社區(qū)內(nèi)的真實(shí)連邊與網(wǎng)絡(luò)在隨機(jī)放置下的期望連邊之間的差值。模塊度越大表示社區(qū)劃分質(zhì)量越好。已有社區(qū)檢測方法中常常利用模塊度最大化思想來發(fā)現(xiàn)具有最高模塊度取值的網(wǎng)絡(luò)，從而捕獲網(wǎng)絡(luò)中的社區(qū)劃分。在面向?qū)傩跃W(wǎng)絡(luò)的社區(qū)檢測中，將節(jié)點(diǎn)所攜帶的屬性向量化，以其屬性相似性值作為邊權(quán)重，綜合節(jié)點(diǎn)的屬性和結(jié)構(gòu)信息。因此，用加權(quán)模塊度比用傳統(tǒng)模塊度度量社區(qū)劃分質(zhì)量效果更佳。

Table 1 Commonly used notations definition表1 常用符號(hào)定義

定義1(加權(quán)模塊度) 給定Aw，加權(quán)模塊度計(jì)算所下所示：

(2)

其中,mw是Aw中邊的權(quán)重和值；cij是指示函數(shù)，如果節(jié)點(diǎn)vi和節(jié)點(diǎn)vj在同一個(gè)社區(qū)，則cij=1，否則cij=0。容易看出，加權(quán)模塊度中考慮了屬性權(quán)重信息。其取值越接近于1，社區(qū)結(jié)構(gòu)越明顯，質(zhì)量越好。

Figure 1 Framework of overlapping multiway spectral community detection algorithm圖1 可重疊多向譜社區(qū)檢測算法框架

現(xiàn)實(shí)網(wǎng)絡(luò)中存在自然重疊的現(xiàn)象，很多網(wǎng)絡(luò)中存在可重疊社區(qū)。例如，在社交網(wǎng)絡(luò)中，其中的每個(gè)節(jié)點(diǎn)對應(yīng)于通常參與多個(gè)社區(qū)的個(gè)體。

定義2(可重疊社區(qū)) 圖中節(jié)點(diǎn)被劃為k個(gè)簇與離群點(diǎn)的集合C={C1,C2,…,Ck,Ck+1}，其中Ci(i=1,2,…,k)表示特定社區(qū)，Ck+1是離群點(diǎn)集合。C1∪C2∪…∪Ck?C，且?Ci∩Cj≠?，即網(wǎng)絡(luò)中的某些節(jié)點(diǎn)不僅僅隸屬于單個(gè)社區(qū)，而是可同時(shí)屬于多個(gè)社區(qū)。

2.3 可重疊的多向譜社區(qū)發(fā)現(xiàn)算法基本框架

本文提出的算法流程如圖1所示，首先通過計(jì)算節(jié)點(diǎn)間的屬性相似性將值賦給節(jié)點(diǎn)間的邊，生成加權(quán)鄰接矩陣；其次，將生成的加權(quán)鄰接矩陣視為加權(quán)圖，應(yīng)用加權(quán)模塊度來將加權(quán)模塊度矩陣分解成特征值與特征向量的表示形式，從而得到節(jié)點(diǎn)的向量化表示，并將其融入到加權(quán)模塊度中，重寫加權(quán)模塊度；再次，選擇初始簇中心向量，并設(shè)置重疊度與離群度制約；最后，將節(jié)點(diǎn)劃分到節(jié)點(diǎn)與其簇中心向量內(nèi)積最大的社區(qū)，循環(huán)更新，得到使得加權(quán)模塊度極大的具有離群點(diǎn)的可重疊社區(qū)。

3 面向?qū)傩跃W(wǎng)絡(luò)的可重疊多向譜社區(qū)檢測

3.1 節(jié)點(diǎn)映射

將節(jié)點(diǎn)屬性間的相關(guān)性轉(zhuǎn)化為節(jié)點(diǎn)間的邊權(quán)重信息，再將加權(quán)模塊度矩陣分解成特征值與特征向量的形式，得到了節(jié)點(diǎn)的向量化表示。根據(jù)定義1，可將加權(quán)模塊度矩陣分解[7,8]成如下形式：

加權(quán)模塊度矩陣為n×n的對稱矩陣B，其矩陣元素定義如下：

(3)

則式(2)中的Qw可改寫為：

(4)

(5)

由于B的對稱性，可將其改寫成特征值與特征向量的分解形式：

(6)

其中,λl是B的特征值;Uil是正交矩陣U的元素，正交矩陣U的列是特征值所對應(yīng)的特征向量。不失一般性，將特征值遞減排序：λ1≥λ2≥…≥λn。

結(jié)合式(2)和式(6)，重寫Qw為：

(7)

(8)

改寫式(8)如下：

(9)

根據(jù)加權(quán)模塊度的特征值與特征向量的近似，即將節(jié)點(diǎn)向量化表示，定義一組n個(gè)p維節(jié)點(diǎn)向量ri[9]，向量ri中各值由式(10)計(jì)算得到：

(10)

改寫式(9)得：

(11)

其中,i∈s表示節(jié)點(diǎn)vi屬于簇s。

更具體地，n個(gè)p維節(jié)點(diǎn)向量ri在整個(gè)優(yōu)化過程中是常數(shù)(因?yàn)閞i是用加權(quán)模塊度矩陣的特征值與特征向量表示的)。然后，將網(wǎng)絡(luò)劃分成簇的加權(quán)模塊度(除了常數(shù)1/(2mw))的貢獻(xiàn)和，其中一個(gè)簇的貢獻(xiàn)等于該簇中節(jié)點(diǎn)的向量和的平方。社區(qū)發(fā)現(xiàn)的目標(biāo)是最大化加權(quán)模塊度的劃分，該問題稱為最大和向量分割問題，簡稱向量分割問題。接下來，給出一種啟發(fā)式算法來快速解決向量分割問題。

3.2 簇中心向量的選擇

在面向?qū)傩缘目芍丿B的多向譜社區(qū)檢測算法中，將屬性數(shù)據(jù)作為網(wǎng)絡(luò)的輔助信息以增強(qiáng)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)間的強(qiáng)度。通過將考慮了網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和節(jié)點(diǎn)攜帶的外部屬性信息融入到加權(quán)模塊度公式中，得到了更精確的節(jié)點(diǎn)映射。通過每個(gè)節(jié)點(diǎn)的向量化表示，選擇k個(gè)社區(qū)的簇中心，以此來開展社區(qū)檢測任務(wù)。最簡單的k個(gè)簇中心的選擇策略是在n個(gè)節(jié)點(diǎn)中隨機(jī)選擇，但是這種策略具有較高的時(shí)間花銷。因此，本節(jié)設(shè)計(jì)了一種在屬性網(wǎng)絡(luò)中的可重疊多向譜算法的簇中心節(jié)點(diǎn)選擇策略。

考慮到在最簡單的情況下，選擇指向隨機(jī)方向且具有相同維度的簇中心向量即可。但是，由于網(wǎng)絡(luò)中存在社區(qū)結(jié)構(gòu)，希望指向少數(shù)方向的多數(shù)節(jié)點(diǎn)向量被聚類，沒有或者很少的向量指向其他方向。并且選擇遠(yuǎn)離集群方向的初始簇中心向量是沒意義的。因此，本文算法從節(jié)點(diǎn)向量中隨機(jī)選擇簇中心向量而不是選擇隨機(jī)方向的簇中心向量。這就保證如果大多數(shù)節(jié)點(diǎn)向量指向幾個(gè)方向，那么選擇也指向這些方向的初始簇中心向量。事實(shí)上只需要以這種方式選擇k個(gè)簇中心向量中的k-1個(gè)，最終向量將由簇中心向量總和為零來決定。

均勻向量l=(1,1,1,…)始終是加權(quán)模塊度矩陣的特征向量，這意味著所有其他特征向量的元素—即正交矩陣U的列必須總和為零(因?yàn)槠浔仨氄挥诰鶆蛳蛄?。根據(jù)式(10)有：

(12)

從而得到：

(13)

和

(14)

因此，一旦隨機(jī)選擇了k-1簇中心向量，第k個(gè)就可以利用式(14)計(jì)算。由于在初始化過程中存在一個(gè)隨機(jī)元素，所以在參數(shù)取值相同的相同網(wǎng)絡(luò)中，結(jié)果也不一定相同。因此，需在不同的初始條件下多次運(yùn)行算法，選擇最高加權(quán)模塊度的社區(qū)劃分。

3.3 屬性網(wǎng)絡(luò)的重疊度和離群度制約

給定參數(shù)α與β，對于M使用參數(shù)α與β進(jìn)行約束[11]：

(15)

3.4 可重疊的多向譜社區(qū)檢測

類似于k-means算法，OMSCD算法用向量代替點(diǎn)，向量內(nèi)積代替距離。首先，選擇簇中心向量矩陣R中的一個(gè)簇Cs，將節(jié)點(diǎn)向量ri分配給與其距離最近的簇中心向量所在的簇，然后根據(jù)這些分配為每個(gè)簇計(jì)算新的簇中心向量并重復(fù)，新的簇中心向量為每個(gè)簇中節(jié)點(diǎn)向量的和，即：

(16)

可將式(11)改寫以最大化式(17)的目標(biāo)函數(shù)：

(17)

當(dāng)Qw與在上一輪計(jì)算的Qw相比值有所下降時(shí)，則認(rèn)為上一輪使得Qw值極大的值為最好的劃分結(jié)果，即Qw達(dá)到收斂。社區(qū)檢測結(jié)果觀察加權(quán)模塊度的特性。假設(shè)將節(jié)點(diǎn)vi從一個(gè)社區(qū)Cs移動(dòng)到另一個(gè)社區(qū)Ct，設(shè)Rs和Rt表示不包括節(jié)點(diǎn)vi的貢獻(xiàn)的2個(gè)社區(qū)的簇中心向量。然后，在移動(dòng)之前，社區(qū)的簇中心向量是Rs+ri和Rt，移動(dòng)后是Rs和Rt+ri。所有其他社區(qū)在此期間保持不變。因此，在移動(dòng)節(jié)點(diǎn)vi時(shí)加權(quán)模塊度的變化△Qw是：

(18)

算法1OMSCD算法

Input：G=(V,E,F)，社區(qū)數(shù)k，重疊度參數(shù)α，離群度參數(shù)β。

Output：指示矩陣M。

1：利用式(1)計(jì)算Aw；

2：利用式(3)計(jì)算B；

3：利用式(6)分解矩陣B，得到B的特征值與特征向量；

4：fori=1ton

5： 利用式(10)計(jì)算ri；

6：endfor

7：初始化簇中心矩陣R；

8：初始化指示矩陣M全為0；

9：while目標(biāo)函數(shù)沒有收斂do

10：fori=1ton

11：forj=1tok

13：endfor

14：endfor

15： 初始化T=?，S=?，p=0；

16：whilep<(n+αn)do

17：ifp

19：S=S∪{vi*}；

20：else

22：endif

23：T=T∪{(vi*,Cl*)}；

24：p=p+1；

25：endwhile

26： 根據(jù)式(16)更新簇中心矩陣R；

27： 計(jì)算節(jié)點(diǎn)向量ri與簇中心向量Rs的內(nèi)積,更新矩陣O；

28： 根據(jù)式(17)計(jì)算目標(biāo)函數(shù)；

29：endwhile

在算法1中，第1～3行根據(jù)公式計(jì)算Aw、B、B的特征值與特征向量;第4～6行得到節(jié)點(diǎn)的向量化表示;第7行依據(jù)3.2節(jié)初始化簇中心向量；第9～29行將圖中的每個(gè)節(jié)點(diǎn)分配到相應(yīng)的社區(qū)中。第15行中T是存放節(jié)點(diǎn)vi屬于簇Cl的集合，集合中的元素為節(jié)點(diǎn)和相應(yīng)簇的二元組；S存放被分配了的節(jié)點(diǎn)的集合；第17～20行用來判斷重疊度是否達(dá)到要求，若達(dá)到，將節(jié)點(diǎn)進(jìn)行分配，否則停止分配；第26行更新簇中心向量；第28行計(jì)算目標(biāo)函數(shù)，得到最好的社區(qū)檢測結(jié)果。

時(shí)間復(fù)雜度分析：在算法1第3，4行計(jì)算節(jié)點(diǎn)向量時(shí)，時(shí)間復(fù)雜度為O(n)；將網(wǎng)絡(luò)劃分成k個(gè)可重疊的簇，計(jì)算節(jié)點(diǎn)向量ri與簇中心向量Rs的乘積oij，復(fù)雜度為O(nk)；再根據(jù)oij對節(jié)點(diǎn)進(jìn)行劃分時(shí)，時(shí)間復(fù)雜度為O((n+αn)×nk)，由于α經(jīng)常取較小的值，故時(shí)間復(fù)雜度為O(n2k)；給定指示矩陣，更新簇中心矩陣的時(shí)間復(fù)雜度為O(nk)；給定簇中心矩陣R，只需遍歷整個(gè)網(wǎng)絡(luò)一次來更新矩陣O，因此時(shí)間復(fù)雜度為O(nk)。設(shè)t為目標(biāo)函數(shù)收斂所需時(shí)間，整個(gè)算法的時(shí)間復(fù)雜度為O(n+tn2k)。

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

為了驗(yàn)證本文算法的有效性和效率，設(shè)計(jì)實(shí)驗(yàn)進(jìn)行驗(yàn)證，實(shí)驗(yàn)將回答以下幾個(gè)問題：

問題1OMSCD算法與現(xiàn)有在屬性網(wǎng)絡(luò)中的譜方法相比，性能方面存在哪些優(yōu)勢？

問題2針對在面向?qū)傩跃W(wǎng)絡(luò)的具有離群點(diǎn)的可重疊多向譜社區(qū)檢測任務(wù)，不同參數(shù)的設(shè)置是怎樣影響本文算法的？

問題3在真實(shí)的網(wǎng)絡(luò)中，實(shí)現(xiàn)社區(qū)檢測任務(wù)的效果如何？

4.1 實(shí)驗(yàn)數(shù)據(jù)集描述

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

使用LFR基準(zhǔn)[12]生成允許節(jié)點(diǎn)隸屬于多個(gè)社區(qū)的屬性網(wǎng)絡(luò)。具體地，節(jié)點(diǎn)的度和社區(qū)規(guī)模大小分布分別由指數(shù)T1和T2控制。給定社區(qū)所需的節(jié)點(diǎn)數(shù)，通過分區(qū)約束將鄰接矩陣分成塊，為每一個(gè)塊選擇概率Pij，以衡量每個(gè)區(qū)塊之間的密度。對角線上的塊為實(shí)際社區(qū)，非對角線塊為社區(qū)間的交叉邊。另外，為節(jié)點(diǎn)分配屬性fi∈[0,1]，屬性值需從正態(tài)分布N(μ,σ)中提取，其余的屬性從具有更大方差的正態(tài)分布N(0,1)中提取[13]。此外，為了檢測離群點(diǎn)與重疊社區(qū)，使該人工數(shù)據(jù)集至多具有βn個(gè)離群點(diǎn)，重疊度α的設(shè)置滿足0≤α≤(k-1)且α?(k-1)。其他參數(shù)設(shè)定為T1=2，T2=1，Pij=0.36，i≠j。表2給出了人工數(shù)據(jù)集的具體信息。

Table 2 Synthetic datasets表2 人工數(shù)據(jù)集

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

選取如表3所示的4個(gè)真實(shí)世界中可重疊的屬性網(wǎng)絡(luò)進(jìn)行驗(yàn)證。第1個(gè)數(shù)據(jù)集是DBLP(Digital Bibliography Library Project)的作者合著關(guān)系網(wǎng)絡(luò)。在該網(wǎng)絡(luò)中，節(jié)點(diǎn)表示作者，以作者間的合著關(guān)系為邊構(gòu)建關(guān)系網(wǎng)絡(luò)，邊權(quán)重表示作者間的合作次數(shù)。musae-Facebook數(shù)據(jù)集是Facebook站點(diǎn)的頁面-頁面圖。節(jié)點(diǎn)代表官方的Facebook頁面，邊表示站點(diǎn)之間的相互喜歡，節(jié)點(diǎn)特征從站點(diǎn)描述中提取而來。第3個(gè)數(shù)據(jù)m-wiki來源于英文維基百科，代表特定主題的頁面-頁面網(wǎng)絡(luò)，其中節(jié)點(diǎn)表示文章，邊表示文章之間的相互鏈接。第4個(gè)數(shù)據(jù)集是美國Political blogs之間的定向超鏈接網(wǎng)絡(luò)，將節(jié)點(diǎn)間的有向邊視為無向邊驗(yàn)證本文的算法。其節(jié)點(diǎn)表示博客，邊表示博客間的鏈接，政治傾向?yàn)閷傩?。真?shí)數(shù)據(jù)集的具體信息由表3所示。

Table 3 Real datasets表3 真實(shí)數(shù)據(jù)集

4.2 評價(jià)指標(biāo)

社區(qū)檢測任務(wù)常使用F-score和NMI作為評價(jià)指標(biāo)[14,15]，定義如下：

定義2(F-score)F-score是召回率和精確率的調(diào)和平均：

(19)

其中,Precision=|CT∩CF|/|CF|，Recall=|CT∩CF|/|CT|，CT表示真實(shí)社區(qū)，CF表示檢測到的社區(qū)。F-score值越大算法性能越好。

定義3(歸一化互信息NMI)NMI基于混淆矩陣N定義如下：

(20)

其中,Nij表示屬于真實(shí)社區(qū)Ci和檢測到的社區(qū)Cj的節(jié)點(diǎn)的數(shù)量，Ni.是矩陣N中第i行中的元素構(gòu)成的行向量，N.j對應(yīng)于矩陣N中第j列元素構(gòu)成的列向量。NMI度量了算法檢測結(jié)果與真實(shí)結(jié)果的相似性，相似性越高，NMI值越接近于1。

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

4.3.1 性能比較(問題1)

選取了NRSR-SC[3]、SCNCD[6]與本文算法分別從社區(qū)檢測的準(zhǔn)確性和運(yùn)行時(shí)間兩方面進(jìn)行比較。其中NRSR-SC算法創(chuàng)新地提出采用約簡屬性來改進(jìn)譜聚類進(jìn)行不可重疊的社區(qū)檢測；SCNCD算法同時(shí)考慮節(jié)點(diǎn)的局部和全局信息通過譜聚類來識(shí)別重疊社區(qū)。因此，本文選取上述2種算法作為實(shí)驗(yàn)參照。

表4顯示了在不同數(shù)據(jù)集上NRSR-SC、SCNCD算法與OMSCD算法結(jié)果的F-score和NMI的值。從表4中可以看到，NRSR-SC算法在較小的數(shù)據(jù)集上相比其他算法的性能較低，如Political blogs。這是由于屬性約簡方法降低了部分性能。SCNCD算法同時(shí)考慮了局部和全局的信息使其在較小的數(shù)據(jù)集上表現(xiàn)出了良好的性能，然而較多考慮局部信息使其在較大數(shù)據(jù)集上的性能有所降低。不論NRSR-SC算法還是SCNCD算法都對數(shù)據(jù)集的規(guī)模比較敏感，算法的F-score和NMI值受到了數(shù)據(jù)集規(guī)模的影響。而OMSCD算法由于選擇了與大多節(jié)點(diǎn)方向類似的簇中心向量，同時(shí)可檢測出重疊社區(qū)和離群點(diǎn)，不僅在不同規(guī)模的數(shù)據(jù)集上的性能表現(xiàn)較好，而且也具有較好的精度。

Figure 2 Comparison of algorithms runtime on different datasets圖2 不同數(shù)據(jù)集上算法運(yùn)行時(shí)間對比

圖2給出了在4個(gè)真實(shí)數(shù)據(jù)集和3個(gè)人工數(shù)據(jù)集上的運(yùn)行時(shí)間對比結(jié)果。隨著數(shù)據(jù)集規(guī)模的不同，3種算法的運(yùn)行時(shí)間有所變化。其中OMSCD算法在各個(gè)數(shù)據(jù)集上都表現(xiàn)出了良好的性能，其運(yùn)行時(shí)間是所有算法中最短的，比其他算法快6 s左右。一方面，這是源于本文算法節(jié)點(diǎn)映射時(shí)近似求解了對加權(quán)模塊度貢獻(xiàn)最大的特征值特征向量。另一方面，這是由于OMSCD算法簇中心向量的初始選擇，使其效率高于其他算法的。NRSR-SC算法和SCNCD算法的運(yùn)行時(shí)間之所以長于本文算法的，是源于NRSR-SC算法屬性約簡過程占用了較多的時(shí)間，而SCNCD算法則是由于利用了節(jié)點(diǎn)收斂度等方法，使其在較大規(guī)模數(shù)據(jù)集上花費(fèi)了較長時(shí)間。

4.3.2 參數(shù)研究(問題2)

分析OMSCD算法2個(gè)重要參數(shù)α與β，討論如何選擇α與β?，F(xiàn)實(shí)中，一些聚類算法的模型參數(shù)設(shè)置不直觀，或者難以預(yù)測特定的參數(shù)設(shè)置的結(jié)果，但是OMSCD算法中的參數(shù)是直觀的，允許用戶自己設(shè)置。因此，用戶可以從自身的領(lǐng)域出發(fā)決定參數(shù)的設(shè)置。接下來將給出參數(shù)α與β對于本文算法的影響分析來估計(jì)參數(shù)α與β的設(shè)置。

Table 4 Comparison with other algorithms表4 與其他算法的比較

Figure 3 Influence of α on OMSCD algorithm on different datasets圖3 不同數(shù)據(jù)集上α對于OMSCD算法的影響

從圖4中可觀察到，隨著β值的增大，OMSCD算法的NMI值在逐漸下降。主要原因是較大的β會(huì)將原本隸屬于社區(qū)內(nèi)的節(jié)點(diǎn)視為離群點(diǎn)進(jìn)行處理，從而對社區(qū)檢測結(jié)果產(chǎn)生影響。在本文中，離群度參數(shù)β的設(shè)置是非窮舉的。接下來將給出運(yùn)行本文算法進(jìn)行社區(qū)檢測時(shí)離群度參數(shù)β的設(shè)置建議。在運(yùn)行本文算法時(shí)，設(shè)zi表示節(jié)點(diǎn)vi與最接近的簇中心之間的距離。計(jì)算zi(i=1,…,n)的平均值(用μ表示)和標(biāo)準(zhǔn)差(用σ表示)。如果距離zi大于μ+3σ，則認(rèn)為節(jié)點(diǎn)vi為異常點(diǎn)。也就是說，如果通過遵循統(tǒng)計(jì)中的3σ規(guī)則，節(jié)點(diǎn)到其最接近聚類的距離大于均值的3個(gè)標(biāo)準(zhǔn)差，則認(rèn)為節(jié)點(diǎn)是異常點(diǎn)。這樣，就可以估計(jì)離群點(diǎn)的數(shù)值，從而得到β值。

Figure 4 Influence of β on OMSCD algorithm on different datasets圖4 不同數(shù)據(jù)集上β上對于OMSCD算法的影響

4.4 案例分析(問題3)

在本節(jié)中，設(shè)計(jì)一個(gè)案例分析來觀察所提出的OMSCD算法的性質(zhì)。研究節(jié)點(diǎn)上所附著的屬性對于節(jié)點(diǎn)向量表示的作用，解釋4.3.1節(jié)所提到的簇中心向量的選擇對于社區(qū)檢測結(jié)果的影響以及是否可準(zhǔn)確地檢測出離群點(diǎn)和可重疊社區(qū)，并觀測OMSCD算法的實(shí)用性。該案例將在美國的Political blogs網(wǎng)絡(luò)上進(jìn)行，Political blogs網(wǎng)絡(luò)相對較小，可以直觀地顯示OMSCD算法的結(jié)果。

實(shí)驗(yàn)結(jié)果如圖5所示，其中重疊度參數(shù)α=1，離群度參數(shù)β=0.007。利用OMSCD算法進(jìn)行社區(qū)檢測任務(wù)。

Figure 5 Community detection results of OMSCD algorithm on the American Political blogs network圖5 OMSCD算法對美國Political blogs 網(wǎng)絡(luò)的社區(qū)檢測結(jié)果

從圖5可以看出，OMSCD算法將其分成了2個(gè)簇，矩形框中的節(jié)點(diǎn)、虛線橢圓區(qū)域中的節(jié)點(diǎn)分別表示政治傾向?yàn)檎珊头磁傻男畔?。網(wǎng)絡(luò)中的重疊社區(qū)為實(shí)線橢圓框圈中區(qū)域，表示政治傾向?yàn)橹辛⑴?。未圈中的?jié)點(diǎn)是離群點(diǎn)，表示不參與任何派系。結(jié)果顯示，在屬性網(wǎng)絡(luò)Political blogs中，采用融合屬性信息和網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的加權(quán)模塊度，通過加權(quán)模塊度最大化得到的節(jié)點(diǎn)向量有效地提高了社區(qū)檢測精度，并進(jìn)一步證明了簇中心向量的初始選擇策略有助于提高算法的效率。此外，利用重疊度和離群度制約檢測出了可重疊社區(qū)以及網(wǎng)絡(luò)中存在的離群點(diǎn)。

5 結(jié)束語

本文針對現(xiàn)有譜算法受限于劃分?jǐn)?shù)量且難以控制重疊程度的局限性，提出了面向?qū)傩跃W(wǎng)絡(luò)的具有離群點(diǎn)的可重疊多向譜社區(qū)檢測算法。首先通過計(jì)算節(jié)點(diǎn)間的屬性相似性將值賦給節(jié)點(diǎn)間的邊，生成加權(quán)鄰接矩陣。同時(shí)，將屬性信息融入到加權(quán)模塊度中，利用考慮屬性信息的加權(quán)模塊度將節(jié)點(diǎn)映射到向量空間，通過設(shè)置重疊度和離群度，實(shí)現(xiàn)可重疊的多向譜社區(qū)檢測。在真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)表明，本文算法在社區(qū)檢測任務(wù)中優(yōu)于傳統(tǒng)的譜算法。