夏秀峰，方 鵬，周大海，安云哲，吳東翰，張學(xué)鑫

(沈陽(yáng)航空航天大學(xué) 計(jì)算機(jī)學(xué)院，沈陽(yáng) 110136)

本文研究面向大規(guī)模圖的聚類問(wèn)題。給定圖G(V,E),V為圖的頂點(diǎn)集合，E為圖的邊集合。圖聚類是將圖G劃分成一組子圖{G1,G2,…,Gn}。給定任意子圖Gi(Vi,Ei)，Gj(Vj,Ej),它們滿足Vi∩Vj=?,Ei∩Ej=?。此外，給定子圖Gi中頂點(diǎn)vi,它與Gi中多個(gè)頂點(diǎn)存在邊，而與其他子圖中頂點(diǎn)不存在邊或僅存在少量邊。

圖聚類問(wèn)題在社區(qū)檢測(cè)、模式識(shí)別、生物網(wǎng)絡(luò)以及異常值檢測(cè)等方面具有廣泛應(yīng)用[1-3]。如圖1中所示，{s1,s2，…，s10}為10名學(xué)生，他們構(gòu)成了圖中的頂點(diǎn)集合。對(duì)于任意2個(gè)學(xué)生si和sj，如果他們所修課程相同，則他們之間存在一條邊。顯然，{s1,s2,s3,s4}這4名同學(xué)對(duì)某一學(xué)科興趣程度較高，他們被劃分到同一個(gè)子圖G1中。同理，{s6,s7,s8,s9}這4名同學(xué)對(duì)另一學(xué)科興趣程度較高，他們被劃分到子圖G2中。這樣一來(lái)，當(dāng)為學(xué)生推薦課外書籍時(shí)，推薦系統(tǒng)可根據(jù)s1所購(gòu)買的圖書為s2,s3,s4進(jìn)行推薦。相似地，推薦系統(tǒng)可根據(jù)s6所購(gòu)買的圖書為s7,s8,s9進(jìn)行推薦。

圖1 學(xué)生購(gòu)書推薦系統(tǒng)

鑒于圖聚類問(wèn)題的重要性，許多學(xué)者針對(duì)圖聚類問(wèn)題展開(kāi)研究，常見(jiàn)算法包括k-core算法、k-dege算法、k-truss算法等[4-6]。在眾多研究成果中，最具代表性的算法為Chang等人[4]提出的基于頂點(diǎn)特征的pSCAN算法，該算法的核心思想是根據(jù)σ(u,v)來(lái)評(píng)估各頂點(diǎn)間的相似性。在這里，u和v表示圖數(shù)據(jù)中的頂點(diǎn)。現(xiàn)有算法的核心思想是：首先計(jì)算各頂點(diǎn)間的相似性，然后比較頂點(diǎn)間的相似性與給定相似性閾值的大小，最后按照給定的圖的最小規(guī)模閾值進(jìn)行聚類?；谠摱x得到的劃分結(jié)果可以有效實(shí)現(xiàn)圖的聚類。然而，現(xiàn)有算法需要計(jì)算每2個(gè)頂點(diǎn)間的相似性，導(dǎo)致了較高的計(jì)算代價(jià)。

鑒于此，本文提出一種基于代表參數(shù)的圖聚類處理框架RPGC(Representative Parameter Graph Cluster)。它的核心思想是選取一組代表性強(qiáng)的參數(shù)集合H{(σ1,μ1),(σ2,μ2)，…，(σm,μm)},分別計(jì)算基于這組參數(shù)的聚類結(jié)果。當(dāng)有新的聚類請(qǐng)求Q(σq,μq)到達(dá)時(shí)，算法可根據(jù)Q(σq,μq)的值在H中找到與之相似性最高的元組(σsim,μsim)，進(jìn)而根據(jù)(σsim,μsim)的聚類結(jié)果快速計(jì)算基于(σq,μq)的聚類結(jié)果。和前人所提算法相比，RPGC計(jì)算框架下的算法有效利用歷史聚類結(jié)果實(shí)現(xiàn)新聚類請(qǐng)求的快速響應(yīng)。主要貢獻(xiàn)如下：

(1)提出一種基于二部圖的代表參數(shù)選取算法。該算法首先將一組代表參數(shù)映射到網(wǎng)格G內(nèi)。以此為基礎(chǔ)，算法針對(duì)每個(gè)代表參數(shù)執(zhí)行范圍查詢，并根據(jù)聚類參數(shù)和結(jié)果之間的關(guān)系構(gòu)建二部圖。最后利用貪心算法實(shí)現(xiàn)代表性參數(shù)的選取。

(2)提出一種基于代表參數(shù)的圖結(jié)構(gòu)增量聚類算法。該算法的核心思想是找到與查詢參數(shù)相似性高的代表參數(shù)，根據(jù)代表參數(shù)和查詢參數(shù)之間的關(guān)系降低頂點(diǎn)間相似性關(guān)系的計(jì)算頻率，進(jìn)而降低整體計(jì)算代價(jià)。

1 研究現(xiàn)狀及問(wèn)題定義

1.1 研究現(xiàn)狀

現(xiàn)有圖聚類算法主要分成2種類型：第一種是基于模塊化或者基于密度的聚類方式，這種類型的圖聚類算法不考慮被聚類的頂點(diǎn)之外的頂點(diǎn)，如上文中所提到k-core算法、k-edge算法、k-truss算法等。此類算法的問(wèn)題是破壞了圖結(jié)構(gòu)的完整性；第二種類型是基于頂點(diǎn)角色的聚類方式，主要包括SCAN算法，SCAN++算法和pSCAN算法等[7-9]。它們的核心思想都是把頂點(diǎn)劃分到經(jīng)聚類得到的子圖中。

SCAN算法反復(fù)處理沒(méi)有被分配到任何簇中的頂點(diǎn)。如果一個(gè)頂點(diǎn)被當(dāng)做核心頂點(diǎn)，并且它與其他簇中的核心頂點(diǎn)之間不存在邊，SCAN算法就會(huì)為該頂點(diǎn)生成一個(gè)新的簇。該算法的缺點(diǎn)是必須計(jì)算圖G中的每一對(duì)相鄰頂點(diǎn)間的結(jié)構(gòu)相似性。SCAN++算法則避免了計(jì)算2個(gè)較遠(yuǎn)頂點(diǎn)間的結(jié)構(gòu)相似性。然而，該算法對(duì)圖的規(guī)模很敏感，不適合計(jì)算規(guī)模較大的圖。pSCAN算法通過(guò)剪枝和連接等方式降低了計(jì)算頂點(diǎn)間結(jié)構(gòu)相似性的成本，并有效加快了計(jì)算速度。但以上算法均未提前存儲(chǔ)簇類結(jié)果，每次都需要重新計(jì)算頂點(diǎn)間的相似性，這種方式需要的計(jì)算時(shí)間較長(zhǎng)[10]。

1.2 問(wèn)題定義

本文主要研究無(wú)向無(wú)權(quán)重圖的圖聚類問(wèn)題。給定圖G中頂點(diǎn)u和v，如果u和v之間存在一條邊，則稱v為u的鄰居，u也被稱為v的鄰居。

定義1(結(jié)構(gòu)化鄰居)對(duì)于圖G(V,E)中的任意頂點(diǎn),其結(jié)構(gòu)化鄰居的定義為N[u]={v∈V|(u,v)∈E}∪{u}。如果頂點(diǎn)u擁有d(u)個(gè)結(jié)構(gòu)化鄰居，那么頂點(diǎn)u的度為d(u)。

定義2(結(jié)構(gòu)相似性)在給定的圖G中，如果存在任意2個(gè)頂點(diǎn)u,v∈V，則可將頂點(diǎn)u,v的結(jié)構(gòu)相似性表示為

(1)

圖2 圖聚類示意圖

定義3(核心頂點(diǎn))給定2個(gè)參數(shù)閾值σ和μ，0≤σ≤1,μ≥2。對(duì)于圖中頂點(diǎn)u，當(dāng)Nσ[u]≥μ時(shí)，u被稱為核心頂點(diǎn)。否則，u被稱為非核心頂點(diǎn)。特別地，假設(shè)v是一個(gè)簇Gi中的核心頂點(diǎn)，如果G中的頂點(diǎn)v′滿足δ(v,v′)≥σ，v′將會(huì)被視作Gi中的元素。如果頂點(diǎn)v被視為Gi中的元素，它需滿足如下條件之一：(1)v是Gi中的核心頂點(diǎn)；(2)Gi中存在核心頂點(diǎn)v′滿足δ(v,v′)≥σ。

定義4(離群點(diǎn))給定圖G和2個(gè)參數(shù)σ和μ，{C1,C2,…,Cn}是一組在閾值范圍內(nèi)的核心簇集合，對(duì)于每一個(gè)頂點(diǎn)u∈G，如果該頂點(diǎn)不屬于任意一個(gè)簇，并且只和不多于一個(gè)簇相連接，則該頂點(diǎn)被稱為離群點(diǎn)。

定義5(橋結(jié)點(diǎn))給定圖G和2個(gè)參數(shù)σ和μ，{C1,C2,…,Cn}是一組在閾值范圍內(nèi)的核心簇集合。對(duì)于每一個(gè)頂點(diǎn)u∈G，如果該頂點(diǎn)不屬于任意一個(gè)簇，但和不少于2個(gè)簇相連，則該頂點(diǎn)被稱為橋結(jié)點(diǎn)。

定義6(簇)簇C是不少于2個(gè)頂點(diǎn)V(|C|≥2)構(gòu)成的集合,它具有如下特性：(1)如果一個(gè)核心頂點(diǎn)u∈C，那么C中所有頂點(diǎn)都和頂點(diǎn)u結(jié)構(gòu)可達(dá)。(2)對(duì)于任意的2個(gè)頂點(diǎn)v1,v2∈C，如果存在一定頂點(diǎn)u∈C，那么頂點(diǎn)u和頂點(diǎn)v1,v2結(jié)構(gòu)可達(dá)。

如圖2所示，給定相似性閾值ε=0.8,μ=4，圖2中的頂點(diǎn)可被劃分到2個(gè)簇C1={v1,v2,v3,v4}和C2={v6,v7,v8,v9}。

需要注意的是：給定一個(gè)核心頂點(diǎn)v∈Ci，對(duì)于其它頂點(diǎn)v′，如果δ(v,v′)≥σ，那么v′也是Ci中的元素。換句話說(shuō)，如果一個(gè)頂點(diǎn)是Ci中的元素，那么存在Ci中的核心頂點(diǎn)與該頂點(diǎn)之間的結(jié)構(gòu)相似性不小于σ，或者該頂點(diǎn)必然是核心頂點(diǎn)[11]。

定義7(問(wèn)題描述)設(shè)σ和μ是2個(gè)閾值，且滿足0≤σ≤1，μ≥2。圖聚類是將圖G(V,E)劃分成一組簇{C1,C2,…Cm}、橋結(jié)點(diǎn)和離群點(diǎn)的集合。對(duì)于每一個(gè)頂點(diǎn)v∈Ci，要么該頂點(diǎn)v是核心頂點(diǎn)，要么存在另外一個(gè)核心頂點(diǎn)v′∈Ci與頂點(diǎn)v之間的結(jié)構(gòu)相似性不小于閾值σ。如圖2所示，假設(shè)參數(shù)的閾值為σ=0.8,μ=4，則圖G可以被劃分成2個(gè)簇C1={v1,v2,v3,v4},C={v6,v7,v8,v9}。此外，v5為橋結(jié)點(diǎn)，v10為離群點(diǎn)。

2 基于代表參數(shù)的圖聚類算法

本文主要研究基于代表參數(shù)的圖聚類算法。正如前文所述，該算法提前構(gòu)建一組代表性強(qiáng)的參數(shù)RH{(σ1,μ1),(σ2,μ2)，…，(σm,μm)}集合，使用算法pSCAN分別基于這組參數(shù)計(jì)算聚類結(jié)果[12]。當(dāng)新聚類任務(wù)參數(shù)Q(σq,μq)被提交時(shí)，RPGC首先在參數(shù)集合H中找到與之相似程度最高的一組參數(shù)<σi,μi>。利用<σi,μi>下得到的聚類結(jié)果，增量地計(jì)算參數(shù)Q(σq,μq)下的聚類結(jié)果。

2.1 代表參數(shù)集選取算法

算法1：參數(shù)集選取算法

輸入：H{(σ1,μ1),(σ2,μ2)，…，(σm,μm)}。

輸出：參數(shù)集RH{(σ1,μ1),(σ2,μ2)，…，(σm,μm)}。

1.for eachiin{μ1,μ2,…,μm} do

2. find(μmax);

5.forifrom 1 tomdo

6. select(σi,μi);

7.Q{Q1,Q2,…,Qm}←pSCAN(σi,μi);

8.for eachiQ{Q1,Q2,…,Qm}

9. createBG{RH(Qi)};

10.RH(σi,μi)←wmax；

11. insert{RH(σi,μi)}；

12. returnRH{(σ1,μ1),(σ2,μ2)，…，(σm,μm)}。

如圖3a所示,算法分別基于閾值{(0.2,0.3),(0.4,0.6),(0.6,0.4),(0.8,0.7)}執(zhí)行范圍查詢?；诰垲悈?shù)閾值(0.2,0.3)得到的閾值為{G1,G5，G6}，基于閾值(0.4,0.6)得到的結(jié)果集為{G2，G5，G6}。以此為基礎(chǔ)，算法根據(jù)查詢結(jié)果構(gòu)建二部圖。其中，二部圖的左部表示查詢中心點(diǎn)，右部表示查詢結(jié)果。給定右部某代表參數(shù)h,它的出度表示它出現(xiàn)在多少個(gè)查詢結(jié)果集內(nèi)。如圖3b所示，G6的出度最高。因此，它被輸出至查詢結(jié)果集。隨后，算法重復(fù)上述操作構(gòu)建代表參數(shù)集RH。

圖3 閾值二維表和二分圖

2.2 基于代表參數(shù)集的增量聚類算法

當(dāng)有新的聚類請(qǐng)求q(σq,μq)提交時(shí)，算法首先在RH中找到2個(gè)歷史查詢(σl,μl)和(σu,μu)。其中，(σl,μl)指所有被(σq,μq)支配的參數(shù)中與(σq,μq)相似程度最高的。在這里，σl≤σq并且μl≤μq，則稱(σl,μl)被(σq,μq)支配。相似地，如果σu≥σq并且μu≥μq，則稱(σu,μu)支配(σq,μq)。本節(jié)引入(σl,μl)和(σu,μu)的原因在于可以利用這2組參數(shù)下的結(jié)果支持增量維護(hù)。

情況Iσq>σi,μq>μi。在這種情況下，2頂點(diǎn)之間具有如下性質(zhì)：(1)如果二者基于(σi,μi)是不相似的，那么它基于(σq,μq)得到的結(jié)果一定是不相似的；(2)如果二者基于(σi,μi)是相似的，那么它基于(σq,μq)得到的結(jié)果可能是相似的，也可能是不相似的。這導(dǎo)致(1)給定G中頂點(diǎn)ei、ej, 如果它們?cè)?σi,μi)下屬于同一個(gè)簇，那么它們?cè)?σq,μq)可能屬于不同的簇；(2)給定G中頂點(diǎn)ei、ej,如果它們?cè)?σi,μi)下不屬于同一個(gè)簇，那么它們?cè)?σq,μq)一定不屬于同一個(gè)簇；(3)如果G中頂點(diǎn)ei在(σi,μi)下是離群點(diǎn)或橋結(jié)點(diǎn)，那么它在(σq,μq)下仍然是離群點(diǎn)或橋結(jié)點(diǎn)。

基于上述性質(zhì)，增量聚類算法的核心思想是給定G中頂點(diǎn)ei、ej, 如果它們?cè)?σi,μi)下不屬于同一個(gè)簇，那么算法不檢查它們之間的相似性[13-15]。例如：當(dāng)提交任務(wù)中2個(gè)參數(shù)的值分別為0.5和8，而歷史特殊點(diǎn)的值為0.4和6，因?yàn)?.4<0.5,且6<8,故在歷史記錄中不能被劃分到同一個(gè)簇中的頂點(diǎn)，在新的任務(wù)提交后仍然不能被劃分到同一個(gè)簇中，即歷史記錄中是離群點(diǎn)的仍然是離群點(diǎn)，而不會(huì)因?yàn)閰?shù)改變而被劃分到核心頂點(diǎn)簇中。

情況IIσq<σi,μq<μi。在這種情況下，2頂點(diǎn)之間具有如下性質(zhì)：(1)如果二者基于σi,μi是相似的，那么它們基于(σq,μq)也一定是相似的；(2)如果二者基于(σi,μi)是不相似的，那么它們基于(σq,μq)得到的結(jié)果可能是相似的，也可能是不相似的。這導(dǎo)致(1)給定G中頂點(diǎn)ei、ej, 如果它們?cè)?σi,μi)下不屬于同一個(gè)簇，那么它們?cè)?σq,μq)一定不屬于同一個(gè)簇；(2)給定G中頂點(diǎn)ei、ej, 如果它們?cè)?σi,μi)下不屬于同一個(gè)簇，那么它們?cè)?σq,μq)一定不屬于同一個(gè)簇；(3)如果G中頂點(diǎn)ei在(σi,μi)下是離群點(diǎn)或橋結(jié)點(diǎn)，那么它在(σq,μq)下仍然是離群點(diǎn)或橋結(jié)點(diǎn)[16]。

例如：當(dāng)提交任務(wù)中2個(gè)參數(shù)的值分別為0.4和6，而歷史特殊點(diǎn)的值為0.5和8，因?yàn)?.4<0.5,且6<8,故在歷史記錄中不能被劃分到同一個(gè)簇中的頂點(diǎn)，在新的任務(wù)提交后仍然不能被劃分到同一個(gè)簇中，即歷史記錄中是核心點(diǎn)的頂點(diǎn)此時(shí)仍然是核心點(diǎn)，不會(huì)因?yàn)閰?shù)改變而被劃分到離群點(diǎn)或者橋結(jié)點(diǎn)的頂點(diǎn)簇中。

圖4 圖聚類示意圖

算法2增量計(jì)算算法

輸入：圖G(V,E)數(shù)據(jù)，相似性閾值0≤σ≤1,μ≥2。

輸出：圖G中簇{C1,C2,…Cm}集合。

1.for vertexu∈Vdo

2.ifσq=σi,μq=μi

3. return {C1,C2,…Cm};

4.else ifσq>σi,μq>μi

5. forifrom 1 tomdo/*m is number of C*/

6.pSCAN(Ci);

7.else ifσq<σi,μq<μi

8. calculate(bridge vertex, outlier vertex);

9.then return {C1,C2,…Cm};

如上述算法所示，輸入圖數(shù)據(jù)以及相似性閾值，首先查找給定的相似性閾值與存儲(chǔ)在閾值表中最接近的閾值。此時(shí)主要考慮3種情況：第一種情況，如果提交的閾值和閾值表中的閾值相等，直接數(shù)據(jù)聚類結(jié)果；第二種情況，如果提交的閾值大于與其最近的閾值表中的值，那么使用pSCAN算法找到已有閾值聚類結(jié)果，重新聚類，此時(shí)不需要計(jì)算已有的離群點(diǎn)和橋結(jié)點(diǎn)；第三種情況，如果提交的閾值小于與其最近的閾值表中的值，此時(shí)不需要重新聚類，只需要計(jì)算橋結(jié)點(diǎn)和離群點(diǎn)能否被劃分到現(xiàn)有的集合中即可[18]。其他情況與此類似，不需詳細(xì)說(shuō)明。

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

3.1 實(shí)驗(yàn)準(zhǔn)備

(1)數(shù)據(jù)集。實(shí)驗(yàn)的第一個(gè)真實(shí)數(shù)據(jù)集是2003年3月通過(guò)爬取亞馬遜網(wǎng)站商品購(gòu)買關(guān)聯(lián)的信息，如果某顧客購(gòu)買了商品i之后，又購(gòu)買了商品j，那么在i，j之間連接一條邊，表示它們之間有關(guān)聯(lián)。實(shí)驗(yàn)的第二個(gè)真實(shí)數(shù)據(jù)集LiveJournal來(lái)自于一個(gè)免費(fèi)的在線博客社區(qū)，用戶可以在此相互宣布友誼。LiveJournal還允許用戶組成一個(gè)組，其他成員隨后可以加入該組。該數(shù)據(jù)集將這些用戶定義的組視為真實(shí)的社區(qū)，可提供LiveJournal友誼社交網(wǎng)絡(luò)和真實(shí)的社區(qū)(見(jiàn)表1)。

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

此外，實(shí)驗(yàn)生成了8個(gè)合成數(shù)據(jù)集(見(jiàn)表2)。每個(gè)數(shù)據(jù)集包含多組圖數(shù)據(jù)的頂點(diǎn)和邊，旨在探討大規(guī)模數(shù)據(jù)集下RPGC計(jì)算框架下算法的計(jì)算時(shí)長(zhǎng)和通信代價(jià)。

表2 合成數(shù)據(jù)集

(2)參數(shù)設(shè)置。在本實(shí)驗(yàn)中2個(gè)重要參數(shù)需要測(cè)試。它們是相似度閾值σ和聚類常數(shù)μ。由于參數(shù)σ的范圍是0<σ≤1，但是若σ=0時(shí)，任意2個(gè)頂點(diǎn)都可以被聚類，對(duì)于研究頂點(diǎn)之間的相似性沒(méi)有意義，所以舍棄。同理當(dāng)σ=1時(shí)，2個(gè)頂點(diǎn)完全相同，對(duì)于研究頂點(diǎn)間相似性也沒(méi)有意義。所以選取參數(shù)σ的范圍是0.2～0.8，默認(rèn)值是0.5；參數(shù)μ的范圍是μ≥2，選取的μ的范圍是4～16，默認(rèn)值是10。

(3)實(shí)驗(yàn)方法。實(shí)驗(yàn)分成2組完成。第一組實(shí)驗(yàn)：通過(guò)數(shù)據(jù)量的不斷增加來(lái)比較算法SCAN++、pSCAN、RPGC之間的運(yùn)行時(shí)長(zhǎng)。通過(guò)比較運(yùn)行時(shí)長(zhǎng)得出參數(shù)σ對(duì)各算法的影響以及優(yōu)劣性。第二組實(shí)驗(yàn)：比較算法SCAN++、pSCAN、RPGC在不同數(shù)據(jù)集下的通信時(shí)長(zhǎng)，以及參數(shù)μ對(duì)各算法通信時(shí)長(zhǎng)的影響。

3.2 實(shí)驗(yàn)分析

(1)相似度參數(shù)σ對(duì)各算法的影響。本實(shí)驗(yàn)測(cè)試圖聚類參數(shù)σ對(duì)聚類時(shí)長(zhǎng)的影響。實(shí)驗(yàn)分別使用真實(shí)數(shù)據(jù)集和合成數(shù)據(jù)集測(cè)試，在參數(shù)σ變化的情況下，其他參數(shù)采用默認(rèn)值。實(shí)驗(yàn)結(jié)果如圖5所示。分別觀察圖5a～5c中的運(yùn)行時(shí)間，可以看到，隨著參數(shù)σ的逐漸增加，SCAN++算法的運(yùn)行時(shí)間逐漸增加，而pSCAN算法和RPGC計(jì)算框架下的算法運(yùn)行時(shí)間逐漸減少，RPGC計(jì)算框架下的算法平均消耗的時(shí)間僅為SCAN++的39%，pSCAN算法的66%。由于該算法提前計(jì)算產(chǎn)生了聚類結(jié)果，當(dāng)聚類任務(wù)提交的時(shí)候，只需要按照增量計(jì)算便可花費(fèi)較少的時(shí)間完成聚類，不需要逐一計(jì)算頂點(diǎn)間的結(jié)構(gòu)相似性。這種情況隨著數(shù)據(jù)量的增加，參數(shù)σ的增大顯得更加明顯。另外，隨著數(shù)據(jù)量的增加，參數(shù)σ的增大，對(duì)相似性的計(jì)算精度要求更高[19]，那么聚類就更加困難。同時(shí)隨著數(shù)據(jù)量的增加，需要更大的內(nèi)存空間和計(jì)算資源，RPGC計(jì)算框架下的算法卻只是在歷史聚類結(jié)果中重新聚類，因此可以節(jié)約內(nèi)存空間和CPU開(kāi)銷。

圖5 不同算法在不同參數(shù)σ下的運(yùn)行時(shí)間

(2)比較聚類參數(shù)μ對(duì)各算法的影響。這組實(shí)驗(yàn)測(cè)試圖聚類參數(shù)μ對(duì)聚類時(shí)長(zhǎng)的影響。這組實(shí)驗(yàn)使用3組數(shù)據(jù)集，在參數(shù)μ變化的情況下，其他參數(shù)采用默認(rèn)值。實(shí)驗(yàn)結(jié)果如圖6所示。

圖6 不同算法在不同參數(shù)μ下的運(yùn)行時(shí)間

由圖6很容易看出RPGC計(jì)算框架下的算法優(yōu)于其他2種算法，基于代表參數(shù)算法的運(yùn)行時(shí)間僅為SCAN++算法的45%，僅為pSCAN算法運(yùn)行時(shí)間的54%。但隨著數(shù)據(jù)量的增加，SCAN++算法和pSCAN算法需要更長(zhǎng)的時(shí)間，而RPGC計(jì)算框架下的算法則不同。其原因是RPGC計(jì)算框架下的算法不需要計(jì)算全部的核心頂點(diǎn)。而且隨著參數(shù)μ的增加，被劃分到同一個(gè)簇中的頂點(diǎn)越多，那么就需要更多的計(jì)算資源，而RPGC計(jì)算框架下的算法卻不需要這些計(jì)算資源。

基于代表參數(shù)的算法始終優(yōu)于現(xiàn)有的算法，因?yàn)镽PGC計(jì)算框架下的算法不需要計(jì)算所有頂點(diǎn)間的結(jié)構(gòu)相似性，不需要找到所有的核心頂點(diǎn)[20]，只是從現(xiàn)有的聚類結(jié)果為依據(jù)，通過(guò)計(jì)算少量頂點(diǎn)的相似性便可完成聚類。

4 結(jié)論

圖聚類是計(jì)算機(jī)圖模型中一個(gè)重要的問(wèn)題。本文提出的基于代表參數(shù)的聚類方式，能夠?qū)v史聚類中所使用的參數(shù)和聚類結(jié)果進(jìn)行存儲(chǔ)并更新，使得計(jì)算代價(jià)較小，節(jié)省大量的內(nèi)部存儲(chǔ)空間。通過(guò)實(shí)驗(yàn)驗(yàn)證了該算法的優(yōu)越性能。