融合結(jié)構(gòu)與屬性視圖的可重疊社區(qū)發(fā)現(xiàn)算法*

昌 陽(yáng)，馬慧芳,2

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

1 引言

社區(qū)發(fā)現(xiàn)算法是發(fā)現(xiàn)社區(qū)內(nèi)部結(jié)構(gòu)和組織原則的基本工具，在多個(gè)領(lǐng)域發(fā)揮著重要作用，如生物網(wǎng)絡(luò)的新陳代謝網(wǎng)絡(luò)分析、社交網(wǎng)絡(luò)中的社區(qū)劃分等。許多真實(shí)世界的網(wǎng)絡(luò)不僅包含結(jié)構(gòu)信息[1]，節(jié)點(diǎn)上還附加了豐富的屬性，但僅考慮一類(lèi)信息源不足以確定社區(qū)結(jié)構(gòu)，原因有2個(gè)：一是結(jié)構(gòu)通常是稀疏和嘈雜的，若僅使用結(jié)構(gòu)信息來(lái)執(zhí)行聚類(lèi)，通常會(huì)導(dǎo)致不好的劃分結(jié)果；二是若僅使用屬性信息進(jìn)行聚類(lèi)，不相關(guān)的屬性信息也可能會(huì)導(dǎo)致非最優(yōu)的聚類(lèi)結(jié)果。

傳統(tǒng)的社區(qū)發(fā)現(xiàn)算法僅針對(duì)結(jié)構(gòu)和屬性之一進(jìn)行挖掘，或是將兩者線性疊加再進(jìn)行挖掘，故不能有效進(jìn)行信息源的融合[2 - 4]。Whang等人[5]提出的NEO-K-Means(Non-Exhaustive Overlapping K-Means)和Jing等人[6]提出的EWKM(Entropy Weighting K-Means)都是對(duì)K-Means的擴(kuò)展，前者考慮了類(lèi)簇之間的重疊性和離群點(diǎn)的情況，但未考慮結(jié)構(gòu)和屬性信息，后者考慮了子空間和節(jié)點(diǎn)屬性，未考慮結(jié)構(gòu)信息。與上述不同，部分社區(qū)檢測(cè)算法同時(shí)考慮了節(jié)點(diǎn)間的屬性和結(jié)構(gòu)信息。例如，Yang等人[7]提出的CESNA(Communities from Edge Structure and Node Attributes)算法考慮了2種信息源，但相對(duì)重要性無(wú)法自動(dòng)計(jì)算；Chen等人[8]提出的TW-K-Means(Two-level variable Weighting K-Means)算法未考慮可重疊的情況；Ruan等人[9]提出的CODICIL(COmmunity Discovery Inferred from Content Information and Link-structure)算法使用屬性為每個(gè)節(jié)點(diǎn)找到最近的鄰居，然后通過(guò)將每個(gè)節(jié)點(diǎn)與其相鄰點(diǎn)相連來(lái)保留圖屬性信息對(duì)圖進(jìn)行重構(gòu)；Cohn等人[10]以實(shí)驗(yàn)方式調(diào)整每個(gè)信息源的重要性，簡(jiǎn)單地將所有節(jié)點(diǎn)權(quán)重固定為特定值。然而，并非所有待聚類(lèi)的節(jié)點(diǎn)的結(jié)構(gòu)和屬性信息在決定節(jié)點(diǎn)的隸屬關(guān)系時(shí)都具有相同的重要性。此外，作為傳統(tǒng)聚類(lèi)算法在高維空間中的延伸，基于子空間的聚類(lèi)算法認(rèn)為每個(gè)類(lèi)簇是由屬性子集標(biāo)識(shí)的一組數(shù)據(jù)，且不同類(lèi)簇可以用不同屬性子集表示。故此，本文設(shè)計(jì)了一種計(jì)算類(lèi)簇子空間的算法，在算法每輪迭代過(guò)程中更新各類(lèi)簇的屬性子空間。通過(guò)定義合理的目標(biāo)函數(shù)約束條件對(duì)傳統(tǒng)的K-Means聚類(lèi)算法進(jìn)行修正，從而計(jì)算每個(gè)類(lèi)簇中各個(gè)維度的權(quán)重，使用權(quán)重值來(lái)標(biāo)識(shí)不同類(lèi)簇中維度的相對(duì)重要性。

綜上，本文提出了一種融合結(jié)構(gòu)與屬性視圖的可重疊社區(qū)發(fā)現(xiàn)COCD(Combination structure and attribute view for Overlapping Community Detection algorithm)算法,同時(shí)考慮了網(wǎng)絡(luò)中的結(jié)構(gòu)和屬性信息，可以自動(dòng)計(jì)算兩者的相對(duì)重要性以及社區(qū)中特定屬性的權(quán)重并揭示子空間。

2 準(zhǔn)備工作

2.1 問(wèn)題定義

給定屬性網(wǎng)絡(luò)G=(V,E,F)，其中V={v1,v2,…,vn}是n個(gè)節(jié)點(diǎn)集合；E是邊集，且|E|=m；F={f1,f2,…,fr}是r個(gè)屬性的集合；A表示鄰接矩陣，若節(jié)點(diǎn)vi和vj間有邊，則Aij=1，否則為0。假設(shè)將圖劃分為k個(gè)社區(qū)，C={c1,c2,…,ck}。表1總結(jié)了本文用到的重要符號(hào)。

Table 1 Several important mathematical notations表1 本文所用到的符號(hào)

2.2 雙視圖的構(gòu)建

將圖G分別表示為屬性視圖G1和結(jié)構(gòu)視圖G2，其中G1用屬性矩陣AF=[fij]∈Rn×r表示，fij為節(jié)點(diǎn)vi在第j維上的屬性；G2用結(jié)構(gòu)矩陣As=[Bij]∈Rn×d表示，Bij為節(jié)點(diǎn)vi在第j維上的結(jié)構(gòu)嵌入值。

2.2.1 屬性視圖的構(gòu)建

對(duì)于屬性圖中的每一個(gè)節(jié)點(diǎn)，它與r維向量表示的屬性相關(guān)聯(lián)。每個(gè)向量中的元素是節(jié)點(diǎn)的屬性值。屬性值可以是單個(gè)單詞、標(biāo)簽等，取決于給定網(wǎng)絡(luò)的上下文。給定數(shù)據(jù)點(diǎn)矩陣X=[Xij]∈Rn×m，每個(gè)數(shù)據(jù)點(diǎn)上附著各自的屬性{f1,f2,…,fr}，由此形成屬性矩陣。

2.2.2 結(jié)構(gòu)視圖的構(gòu)建

構(gòu)建結(jié)構(gòu)視圖旨在將信息網(wǎng)絡(luò)嵌入低維空間，可將每個(gè)節(jié)點(diǎn)都表示為一個(gè)低維向量。經(jīng)典的圖嵌入算法之一如DeepWalk[11]，通過(guò)對(duì)圖隨機(jī)游走得到一些序列，把序列當(dāng)句子，利用word2vec就可以得到每一個(gè)“詞”的向量。node2vec[12]可以看作是對(duì) DeepWalk 的一種更廣義的抽象，主要是對(duì)DeepWalk的隨機(jī)游走策略進(jìn)行了改進(jìn)，因?yàn)槠胀ǖ碾S機(jī)游走不能很好地保留節(jié)點(diǎn)的局部信息，所以node2vec增加了2個(gè)參數(shù)來(lái)對(duì)節(jié)點(diǎn)鄰居加以控制，以獲取鄰域信息和更復(fù)雜的依賴(lài)信息。Graph2vec[13]直接對(duì)整個(gè)圖進(jìn)行嵌入，原理與DeepWalk類(lèi)似。近期提出的用于隨機(jī)塊模型的不同的隱私鄰接譜嵌入算法ASE(Adjacency Spectral Embedding)[14]，通過(guò)鄰接譜嵌入估計(jì)接近于Frobenius范數(shù)的潛在位置，并在模擬網(wǎng)絡(luò)和真實(shí)網(wǎng)絡(luò)中達(dá)到與期望參數(shù)相當(dāng)?shù)母呔龋瑏?lái)有效地進(jìn)行圖嵌入。LINE(Large-scale Information Network Embedding)[15]作為圖嵌入的經(jīng)典算法，融合了一階與二階相似度，可以有效地將大規(guī)模網(wǎng)絡(luò)嵌入到低維向量空間，其適用性廣泛，這也是本文選擇LINE進(jìn)行嵌入的原因。

定義1(結(jié)構(gòu)相似度) 節(jié)點(diǎn)對(duì)(vi,vj)的結(jié)構(gòu)相似度是其鄰居網(wǎng)絡(luò)結(jié)構(gòu)之間的相似度，ui是vi被視為節(jié)點(diǎn)時(shí)的表示，u′i是vi被視為其他節(jié)點(diǎn)特定“上下文”時(shí)的表示。若無(wú)節(jié)點(diǎn)同時(shí)和vi與vj連接，則vi和vj的結(jié)構(gòu)相似度是0。結(jié)構(gòu)相似度計(jì)算公式如下所示：

(1)

(2)

O=-∑(vi,vj)∈ESijlogp(vj|vi)

(3)

與LINE算法[15]類(lèi)似，通過(guò)學(xué)習(xí)n個(gè)節(jié)點(diǎn)作為節(jié)點(diǎn)的向量表示{ui|i=1,2,…,n}和作為“上下文”的向量表示{u′i|i=1,2,…,n}，使式(3)最小化，能夠用d維向量ui表示每個(gè)節(jié)點(diǎn)vi。

3 COCD算法

3.1 COCD目標(biāo)函數(shù)

現(xiàn)有的基于視圖的維度加權(quán)聚類(lèi)算法如TW-K-Means[8]可以執(zhí)行子空間聚類(lèi)任務(wù)。與在整個(gè)數(shù)據(jù)集的維度上分配權(quán)重不同，子空間聚類(lèi)算法為每個(gè)類(lèi)簇中的每一維度分配權(quán)重，因此，不同的類(lèi)簇具有不同的權(quán)重值集合，為了保持可擴(kuò)展性，在這些新的子空間聚類(lèi)算法中采用了K-Means 的聚類(lèi)過(guò)程。在每次迭代中，不僅能同時(shí)計(jì)算視圖和維度的權(quán)重，還能為視圖中的每個(gè)維度分配權(quán)重。本文融合節(jié)點(diǎn)間的屬性和結(jié)構(gòu)信息改進(jìn)了TW-K-Means算法，將固有的子空間聚類(lèi)算法集成到重疊社區(qū)發(fā)現(xiàn)的框架中，不僅能自適應(yīng)地計(jì)算2個(gè)視圖的相對(duì)重要性，還能挖掘可重疊的社區(qū)及子空間。將數(shù)據(jù)點(diǎn)X進(jìn)行預(yù)處理后，構(gòu)建結(jié)構(gòu)視圖和屬性視圖，再聚類(lèi)為k個(gè)簇的過(guò)程建模為以下目標(biāo)函數(shù)的最小化：

(4)

其中,U是指示矩陣，表示節(jié)點(diǎn)和簇的隸屬關(guān)系；Z表示簇中心矩陣；w是一個(gè)2×1且元素都初始化為1/2的列向量，表示視圖的相對(duì)重要性；h是m×1的列向量，表示視圖下每一維屬性的相對(duì)重要性。右側(cè)第1項(xiàng)是簇內(nèi)分散程度的總和，l表示簇編號(hào);i表示節(jié)點(diǎn)編號(hào)；j表示每一個(gè)視圖的維度，j=1時(shí)表示結(jié)構(gòu)視圖，j=2時(shí)表示屬性視圖;t表示視圖編號(hào),t=1,2;G1和G2分別是結(jié)構(gòu)視圖維度和屬性視圖維度的集合。第2項(xiàng)和第3項(xiàng)是2個(gè)負(fù)熵權(quán)，λ和η是2個(gè)正參數(shù)。約束于：

其中,α控制聚類(lèi)之間的重疊度，0≤α≤(k-1)。算法流程圖如圖1所示。

Figure 1 Flowchart of the overlapping community detection algorithm combing structure with attribute view圖1 融合結(jié)構(gòu)和屬性視圖的可重疊社區(qū)發(fā)現(xiàn)算法流程圖

如圖1所示，首先，對(duì)數(shù)據(jù)進(jìn)行預(yù)處理后，獲取社區(qū)發(fā)現(xiàn)算法所需的雙視圖。一方面，從原始屬性圖上獲取屬性矩陣；另一方面，利用結(jié)構(gòu)相似度方法將圖嵌入到低維空間，轉(zhuǎn)換成低維向量之后得到結(jié)構(gòu)矩陣。由此獲得算法需要的原始數(shù)據(jù)矩陣。其次，隨機(jī)初始化簇中心矩陣、視圖權(quán)重以及每一個(gè)視圖中的每一維權(quán)重；再計(jì)算數(shù)據(jù)點(diǎn)與簇中心的加權(quán)距離矩陣，根據(jù)加權(quán)距離矩陣，將數(shù)據(jù)點(diǎn)分配給距離最近的簇，得到指示矩陣。然后，利用指示矩陣和數(shù)據(jù)矩陣對(duì)每個(gè)簇中的數(shù)據(jù)每一維度求平均值，更新簇中心矩陣。再次，子空間聚類(lèi)算法為每個(gè)類(lèi)簇中的每一維度分配權(quán)重，再更新視圖權(quán)重向量和視圖上屬性的維度權(quán)重向量，即揭示子空間。最后，計(jì)算目標(biāo)函數(shù)的值，查看目標(biāo)函數(shù)值是否收斂，若已收斂，結(jié)束算法，得到指示矩陣；若仍未收斂，迭代上述過(guò)程，直到目標(biāo)函數(shù)收斂或者達(dá)到最大迭代次數(shù)，結(jié)束算法。此外，目標(biāo)函數(shù)給出了關(guān)于算法重疊度的約束條件，使得算法可以檢測(cè)網(wǎng)絡(luò)中的重疊社區(qū)。

3.2 模型優(yōu)化

通過(guò)迭代求解以下最小化問(wèn)題來(lái)最小化式(4)：

優(yōu)化目標(biāo)函數(shù)的方法是對(duì)U、Z和w以及h進(jìn)行部分優(yōu)化。通過(guò)迭代算法使得目標(biāo)函數(shù)趨于局部極小值，優(yōu)化部分每一步都是嚴(yán)格遞減的，故算法收斂于局部最小值。對(duì)于固定U、Z和h，根據(jù)w對(duì)目標(biāo)函數(shù)進(jìn)行最小化時(shí)，本文與文獻(xiàn)[8]類(lèi)似使用如下函數(shù)更新目標(biāo)函數(shù)。視圖權(quán)重wt和視圖下維度權(quán)重hj的計(jì)算公式如下所示:

當(dāng)且僅當(dāng)給定U、Z和h，下式成立：

(5)

證明對(duì)于hj，最小化目標(biāo)函數(shù)式(4)，若j=1，hj表示第1個(gè)視圖上第j維的重要性，若j=2，hj表示第2個(gè)視圖上第j維的重要性。對(duì)于t=1,2，存在約束∑j∈Gthj=1,0≤hj≤1,t=1,2，通過(guò)隔離包含{h1,h2,…,hm}的項(xiàng),并添加合適的拉格朗日乘數(shù)得到形式化后的拉格朗日函數(shù)：

η∑j∈Gthjloghj+γt(∑j∈Gthj-1)]

(6)

其中,Qj是在固定U、Z、w時(shí)第j維的雙視圖權(quán)重，

對(duì)于γt和hj，將L{h1,h2,…,hm}的梯度設(shè)置為0，得到：

?L{h1,h2,…,hm}/?γt=∑j∈Gthj-1=0

(7)

?L{h1,h2,…,hm}/?vj=Qj+η(1+loghj)+γt=0

(8)

由式(8)得到：

hj=exp[(-Qj-γt-η)/η]=

exp[(-Qj-η)/η]exp(-γt/η)

(9)

將式(9)代入式(6)得到：

(10)

故

exp(-γt/η)=1/∑j∈Gtexp[(-Qj-η)/η]

(11)

將式(11)代入式(9)得到：

hj=exp(-Qj/η)/∑m∈Gtexp(-Qm/η)

同上可得：

當(dāng)且僅當(dāng)給定U、Z和w，下式成立：

hj=exp(-Qj/η)/∑m∈Gtexp(-Qm/η)

(12)

3.3 COCD算法偽代碼

根據(jù)上述最小化過(guò)程總結(jié)COCD算法總結(jié)如算法1所示。

算法1COCD算法

Input：數(shù)據(jù)點(diǎn)矩陣X，簇個(gè)數(shù)k，控制重疊的參數(shù)α，正參數(shù)η，λ。

Output：U,Z,h,w。

1.隨機(jī)選取k個(gè)簇中心Z;

2.fort=1to2do

3.wt=1/2;

4.forallj∈Gtdo

5.hj=1/|Gt|;

6.endfor

7.endfor

8.r←0;

9.repeat

10. 計(jì)算每一個(gè)數(shù)據(jù)點(diǎn)與所有簇中心的加權(quán)距離矩陣[djl]n×k;

11. 初始化全為0指示矩陣U;

12. 初始化T=φ,p=0;

13.whilep<(n+αn)do

15.endwhile

16. 更新簇中心矩陣Z,根據(jù)式(5)更新w,根據(jù)式(6)更新h;

17.r←r+1;

18.until目標(biāo)函數(shù)值到達(dá)局部最小值或達(dá)到迭代次數(shù)

在算法1中，X是進(jìn)行預(yù)處理之前的n個(gè)數(shù)據(jù)點(diǎn)矩陣；k是輸入簇的個(gè)數(shù)；α是控制重疊程度的參數(shù)，η，λ是2個(gè)正參數(shù)；T表示存放節(jié)點(diǎn)被分配到簇的集合，集合中的元素是節(jié)點(diǎn)和簇的二元組，表示該節(jié)點(diǎn)被劃分到了相應(yīng)的簇；p是確定重疊度的參數(shù)。1～7行是初始化過(guò)程，初始化簇中心矩陣Z、視圖權(quán)重向量w、視圖下維度權(quán)重向量h。第10行是計(jì)算加權(quán)距離矩陣。第11、12行初始化一些參數(shù)。第13～15行用來(lái)判斷重疊度是否達(dá)到要求，若未達(dá)到要求，繼續(xù)分配數(shù)據(jù)，否則停止分配，第13行進(jìn)行(1+α)n次賦值，保證目標(biāo)函數(shù)滿足第1個(gè)約束條件。第16行更新簇中心矩陣Z、視圖權(quán)重向量w、視圖下維度的權(quán)重向量h。第18行判斷目標(biāo)函數(shù)是否收斂。

COCD算法涉及到的主要計(jì)算步驟有以下3步，運(yùn)行時(shí)復(fù)雜度可以分析如下：

(1)劃分：將數(shù)據(jù)分類(lèi)為k個(gè)可重疊的類(lèi)簇，計(jì)算加權(quán)距離矩陣，復(fù)雜度為O(nk)；再根據(jù)加權(quán)距離矩陣將數(shù)據(jù)點(diǎn)進(jìn)行劃分時(shí)，時(shí)間復(fù)雜度為O((n+αn)×nk)，由于α經(jīng)常比較小，故復(fù)雜度為O(n2k)。

(2)更新簇中心：給定指示矩陣U，更新簇中心就是在同一個(gè)類(lèi)簇中找到數(shù)據(jù)對(duì)象的均值。因此，對(duì)于k個(gè)類(lèi)簇，這一步的計(jì)算復(fù)雜度是O(nk(|G1|+|G2|))。

(3)更新視圖權(quán)重w及視圖維度權(quán)重h：給定U，Z與h，根據(jù)式(5)更新w，只需遍歷整個(gè)數(shù)據(jù)集一次來(lái)更新h，因此此步驟的復(fù)雜度為O(nk(|G1|+|G2|));給定U,Z與w，根據(jù)式(5)更新h，同理，只需遍歷整個(gè)數(shù)據(jù)集一次來(lái)更新h，因此此步驟的復(fù)雜度為O(nk(|G1|+|G2|))。

如果聚類(lèi)過(guò)程需要td次迭代才收斂，則該算法的總計(jì)算復(fù)雜度為max(O(tdnk(|G1|+|G2|)),O(tdn2k))。COCD算法使目標(biāo)函數(shù)值單調(diào)下降，直到其收斂到局部最小值。

4 實(shí)驗(yàn)

為了全面評(píng)估COCD的有效性和效率，本節(jié)分別在人工和真實(shí)數(shù)據(jù)集上設(shè)計(jì)了2組實(shí)驗(yàn)。首先描述實(shí)驗(yàn)所用數(shù)據(jù)集；其次觀察不同參數(shù)值對(duì)實(shí)驗(yàn)結(jié)果的影響，選擇適宜的參數(shù)；然后分析算法的可擴(kuò)展性；最后選取4個(gè)典型的社區(qū)發(fā)現(xiàn)算法及未經(jīng)3.2節(jié)優(yōu)化的本文低階算法COCD(Naive)與本文算法在人工網(wǎng)絡(luò)和在真實(shí)網(wǎng)絡(luò)上對(duì)比算法性能。

4.1 數(shù)據(jù)集與評(píng)價(jià)指標(biāo)

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

具有基準(zhǔn)社區(qū)的人工網(wǎng)絡(luò)是基于LFR基準(zhǔn)[17]生成的，其具有與真實(shí)世界網(wǎng)絡(luò)類(lèi)似的特征。通過(guò)設(shè)置人工網(wǎng)絡(luò)的一些重要參數(shù)，最終生成了具有5個(gè)基準(zhǔn)社區(qū)結(jié)構(gòu)的人工網(wǎng)絡(luò)(syn1～syn5),如表2所示。

Table 2 Synthetic network datasets表2 人工網(wǎng)絡(luò)數(shù)據(jù)集

4.1.2 真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集

對(duì)已有文獻(xiàn)中所廣泛應(yīng)用的網(wǎng)絡(luò)數(shù)據(jù)集進(jìn)行了收集和整理，具體有：Flickr數(shù)據(jù)集[18]是圖像共享網(wǎng)絡(luò)，節(jié)點(diǎn)表示用戶(hù)，邊是友誼關(guān)系，屬性為用戶(hù)的圖像標(biāo)簽，用戶(hù)有此標(biāo)簽屬性給1，否則給0。Amazon數(shù)據(jù)集來(lái)自產(chǎn)品共同購(gòu)買(mǎi)網(wǎng)絡(luò)，可從斯坦福大型網(wǎng)絡(luò)數(shù)據(jù)集獲得，其中節(jié)點(diǎn)是產(chǎn)品，共同購(gòu)買(mǎi)的產(chǎn)品通過(guò)邊連接，屬性為產(chǎn)品具有的特征，每個(gè)節(jié)點(diǎn)都包含多種類(lèi)型的屬性。Cora是一個(gè)論文數(shù)據(jù)集，本文采用常振超等人[19]的方法，對(duì)原始Cora數(shù)據(jù)集進(jìn)行精簡(jiǎn)，去除了在論文中詞頻統(tǒng)計(jì)小于10的單詞，其中，邊是論文之間的引用關(guān)系，至少引用一次，兩者之間相互引用均記為一條連接關(guān)系，文檔所有者之間相互引用均記為一條連接關(guān)系，以文檔所出現(xiàn)的單詞作為文檔的節(jié)點(diǎn)屬性。3個(gè)真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集總結(jié)如表3所示。

Table 3 Real network datasets表3 真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集

4.1.3 評(píng)價(jià)指標(biāo)

本文采用與文獻(xiàn)[2]和文獻(xiàn)[4]中相同的對(duì)經(jīng)典F1分?jǐn)?shù)和NMI(Normalized Mutual Informaiton)分?jǐn)?shù)的改進(jìn)評(píng)價(jià)指標(biāo)平均F1分?jǐn)?shù)和平均NMI分?jǐn)?shù)來(lái)進(jìn)行評(píng)估。

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

4.2.1 參數(shù)設(shè)置

COCD算法包括3個(gè)重要參數(shù)α，η和λ，本小節(jié)討論如何在實(shí)驗(yàn)中設(shè)置這3個(gè)重要參數(shù)。參數(shù)α是直觀的，允許指定類(lèi)簇的重疊程度，參數(shù)η和λ可以通過(guò)實(shí)驗(yàn)來(lái)驗(yàn)證其最優(yōu)值。用戶(hù)可以用經(jīng)驗(yàn)知識(shí)來(lái)估計(jì)參數(shù)α，如果從經(jīng)驗(yàn)知識(shí)中獲取不到，也可以通過(guò)使用以下討論的啟發(fā)式來(lái)估計(jì)α值。

圖2a和圖2b分別顯示了COCD算法在5個(gè)人工數(shù)據(jù)集上取不同η和λ值時(shí)對(duì)聚類(lèi)結(jié)果的影響。由于篇幅限制，且使用NMI分?jǐn)?shù)的量化結(jié)果與F1分?jǐn)?shù)的一致，故僅將使用F1分?jǐn)?shù)量化的結(jié)果表示出來(lái)。從圖2能看出，η和λ從0.5變?yōu)?的過(guò)程中，F(xiàn)1分?jǐn)?shù)的波動(dòng)不大，即聚類(lèi)精度對(duì)這2個(gè)參數(shù)不敏感。結(jié)果表明COCD算法對(duì)參數(shù)η和λ具有魯棒性。

4.2.2 可擴(kuò)展性分析

通過(guò)測(cè)量在不斷增大規(guī)模的人工網(wǎng)絡(luò)上的運(yùn)行時(shí)間來(lái)評(píng)估COCD的可擴(kuò)展性。為了進(jìn)行評(píng)估，考慮6類(lèi)基線社區(qū)檢測(cè)方法：(1)僅使用網(wǎng)絡(luò)結(jié)構(gòu)的方法—BIGCLAM(CLuster Affiliation Model for BiG networks)[3]；(2)僅使用節(jié)點(diǎn)屬性的方法—MAC(Multi-Assignment Clustering)[6]；(3)將兩者結(jié)合的方法—CESNA[7]；(4)考慮了節(jié)點(diǎn)屬性以及子空間的算法—EWKM[5]；(5)多視圖聚類(lèi)算法(不能檢測(cè)重疊社區(qū))—TW-K-Means[8]；(6)未經(jīng)過(guò)3.2節(jié)優(yōu)化的算法—COCD(Naive)。

圖3顯示了算法的運(yùn)行時(shí)間與網(wǎng)絡(luò)規(guī)模的關(guān)系?？偟膩?lái)說(shuō)，本文算法COCD是最快的算法，一小時(shí)左右的時(shí)間可以處理約30萬(wàn)個(gè)節(jié)點(diǎn)；MAC是最慢的，而B(niǎo)IGCLAM比CESNA快，因?yàn)樗褂门cCESNA類(lèi)似的優(yōu)化過(guò)程，但沒(méi)有考慮節(jié)點(diǎn)屬性。對(duì)于小型網(wǎng)絡(luò)(最多17萬(wàn)個(gè)節(jié)點(diǎn))，BIGCLAM比COCD(Naive)更快，但是當(dāng)網(wǎng)絡(luò)規(guī)模變大時(shí)，COCD(Naive)會(huì)更快。此外，COCD(Naive)是沒(méi)有經(jīng)過(guò)迭代優(yōu)化的算法，時(shí)間復(fù)雜度一般情況下比COCD的小，但對(duì)式(4)中帶有約束的目標(biāo)函數(shù)進(jìn)行最小化時(shí)，會(huì)形成一類(lèi)非線性?xún)?yōu)化問(wèn)題，使得目標(biāo)函數(shù)的解是未知的，所以本文對(duì)指示矩陣U、簇中心矩陣Z以及視圖的相對(duì)重要性向量w和視圖下每一維屬性的相對(duì)重要性h進(jìn)行部分優(yōu)化,達(dá)到目標(biāo)函數(shù)最小化的目的。最終通過(guò)迭代方法使得目標(biāo)函數(shù)趨于局部極小值。故運(yùn)行時(shí)間會(huì)比COCD的長(zhǎng)。

Figure 3 Algorithm running time comparison圖3 算法運(yùn)行時(shí)間比較

4.2.3 人工網(wǎng)絡(luò)和實(shí)際網(wǎng)絡(luò)結(jié)果分析

與4.1.1節(jié)所提出的對(duì)比算法一致，比較本文算法與5個(gè)對(duì)比算法在5個(gè)由LFR基準(zhǔn)生成的人工網(wǎng)絡(luò)數(shù)據(jù)集和3個(gè)真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上的平均F1分?jǐn)?shù)與平均NMI值。結(jié)果如表4和表5所示。

Table 4 Average F1-scores and average NMI-scores of algorithms on five synthetic datasets表4 5個(gè)人工數(shù)據(jù)集上各算法的平均F1分?jǐn)?shù)與平均NMI分?jǐn)?shù)

Table 5 Average F1-scores and average NMI-scores of algorithms on real datasets表5 真實(shí)數(shù)據(jù)集上各算法的平均F1分?jǐn)?shù)與平均NMI分?jǐn)?shù)

表4顯示了人工網(wǎng)絡(luò)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果，COCD在10個(gè)案例上有8個(gè)都得到了最佳的性能。表5顯示了在真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果，將COCD與沒(méi)有節(jié)點(diǎn)屬性的BIGCLAM進(jìn)行比較，注意到COCD得到了更好的性能，因?yàn)樗Y(jié)合了來(lái)自節(jié)點(diǎn)屬性和網(wǎng)絡(luò)的信息。同樣，COCD也優(yōu)于MAC，因?yàn)楹笳咧魂P(guān)注節(jié)點(diǎn)屬性。自然地，COCD絕不會(huì)比僅使用單一信息源的最先進(jìn)算法表現(xiàn)更差。注意到本文基線算法TW-K-Means在人工數(shù)據(jù)集和真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上的表現(xiàn)不如CESNA和COCD，這是因?yàn)門(mén)W-K-Means在進(jìn)行社區(qū)發(fā)現(xiàn)時(shí)未考慮重疊度的問(wèn)題，而真實(shí)網(wǎng)絡(luò)中社區(qū)是自然重疊的，故當(dāng)社區(qū)存在重疊情況時(shí)檢測(cè)效果不佳。此外，在將COCD的性能與同時(shí)考慮網(wǎng)絡(luò)結(jié)構(gòu)和節(jié)點(diǎn)屬性的算法(CESNA)和考慮節(jié)點(diǎn)屬性以及子空間的算法(EWKM)和COCD(Naive)的性能進(jìn)行比較時(shí)，也能再次觀察到COCD的強(qiáng)大性能。

COCD在人工數(shù)據(jù)集上的NMI值和F1分?jǐn)?shù)優(yōu)于真實(shí)數(shù)據(jù)集上的值，這是無(wú)可厚非的。此外，對(duì)于真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集，COCD在內(nèi)容共享網(wǎng)絡(luò)(如Flickr)上相比社交網(wǎng)絡(luò)上性能增益更佳。例如，在Flickr網(wǎng)絡(luò)上與除本文算法外性能最佳的算法相比，COCD在平均F1分?jǐn)?shù)和平均NMI分?jǐn)?shù)中分別獲得15%和13%的相對(duì)增益，可能的解釋是，在內(nèi)容共享網(wǎng)絡(luò)中，節(jié)點(diǎn)的屬性(內(nèi)容)在連接生成中起著更大的作用?？偟膩?lái)說(shuō)，在16個(gè)案例中,COCD在12個(gè)案例上性能最佳。

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

本文提出了一種新的社區(qū)發(fā)現(xiàn)算法——COCD算法，融合了2種信息源來(lái)對(duì)屬性圖進(jìn)行聚類(lèi)。該算法可以自適應(yīng)計(jì)算2個(gè)視圖的相對(duì)重要性，并且還為對(duì)應(yīng)視圖中的每個(gè)維度分配權(quán)重以及挖掘子空間。這是一種可擴(kuò)展的算法，用于大型復(fù)雜網(wǎng)絡(luò)中的重疊社區(qū)檢測(cè)。實(shí)驗(yàn)表明，在人工網(wǎng)絡(luò)數(shù)據(jù)集和實(shí)際網(wǎng)絡(luò)數(shù)據(jù)集上，與之前經(jīng)典的社區(qū)發(fā)現(xiàn)算法相比，本文提出的COCD算法都顯示了較好的性能，提高了社區(qū)發(fā)現(xiàn)的有效性和高效性。