采用模糊k核多粒度分解機(jī)制的高效社區(qū)發(fā)現(xiàn)

李宏平，劉 群

(重慶郵電大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，重慶 400000)

0 引 言

社區(qū)結(jié)構(gòu)的發(fā)現(xiàn)對(duì)于理解復(fù)雜網(wǎng)絡(luò)中的結(jié)構(gòu)有重要作用[1-4]。Newman算法[5]在傳統(tǒng)算法的基礎(chǔ)上大幅度降低了運(yùn)算時(shí)間，使得社區(qū)發(fā)現(xiàn)不再局限于小規(guī)模網(wǎng)絡(luò)。louvain算法[6]進(jìn)一步優(yōu)化了大規(guī)模網(wǎng)絡(luò)圖上的社區(qū)發(fā)現(xiàn)運(yùn)算時(shí)間。LPA算法[7]通過(guò)少量預(yù)定義社區(qū)標(biāo)簽預(yù)測(cè)其余大部分未定義節(jié)點(diǎn)的標(biāo)簽，實(shí)現(xiàn)對(duì)大規(guī)模網(wǎng)絡(luò)的快速社區(qū)劃分。Walktrap算法[8]采用計(jì)算節(jié)點(diǎn)間的相似性的方式高效地捕捉各種規(guī)模網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)。貝葉斯模塊選擇算法[9]能高效、可解釋地計(jì)算出節(jié)點(diǎn)的社區(qū)分配以及社區(qū)的最佳數(shù)量。雖然上述方法對(duì)時(shí)間復(fù)雜度有所降低，但是它們的計(jì)算時(shí)間與節(jié)點(diǎn)數(shù)量的關(guān)系密切相關(guān)，仍然需要花費(fèi)較多的計(jì)算時(shí)間，尤其對(duì)于規(guī)模較大的網(wǎng)絡(luò)，問(wèn)題更加顯著。可見(jiàn)，如何在減少社區(qū)發(fā)現(xiàn)算法運(yùn)算時(shí)間的同時(shí)保證社區(qū)發(fā)現(xiàn)的精確度是社區(qū)發(fā)現(xiàn)領(lǐng)域還存在的一個(gè)問(wèn)題。

針對(duì)上述問(wèn)題，本文提出了一種基于模糊k-core的社區(qū)發(fā)現(xiàn)算法，首先使用k-core子圖代表整個(gè)社區(qū)結(jié)構(gòu)的分布，以減少社區(qū)劃分的運(yùn)算時(shí)間；在傳統(tǒng)k-core分解的基礎(chǔ)上運(yùn)用模糊理論的隸屬度函數(shù)得到模糊k-core子圖，最大可能地保留高重要性節(jié)點(diǎn)，對(duì)模糊k-core子圖進(jìn)行社區(qū)劃分，并將劃分結(jié)果合理有效地?cái)U(kuò)散到其余節(jié)點(diǎn)，以保證社區(qū)發(fā)現(xiàn)準(zhǔn)確度。實(shí)驗(yàn)結(jié)果表明，本算法在不同規(guī)模的真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上與以上大部分算法相比，在減少運(yùn)算時(shí)間的同時(shí)保證了社區(qū)劃分的準(zhǔn)確性，體現(xiàn)出了較強(qiáng)的綜合性能。

1 相關(guān)知識(shí)

1.1 k-core分解

k-core分解可以區(qū)分不同節(jié)點(diǎn)的結(jié)構(gòu)重要性并保留節(jié)點(diǎn)的鄰域關(guān)系。該方法遞歸刪除度數(shù)小于k的節(jié)點(diǎn)，直到所有其余頂點(diǎn)的度數(shù)都大于或等于k。k-core分解是一種基于節(jié)點(diǎn)的度，以提取核心節(jié)點(diǎn)集為目標(biāo)的算法。

定義1 圖的凝聚度：表示一個(gè)圖網(wǎng)絡(luò)中節(jié)點(diǎn)與節(jié)點(diǎn)之間聯(lián)系的緊密程度，通常由連通度和直徑這兩個(gè)度量指標(biāo)進(jìn)行衡量，其中連通度是將一個(gè)連通圖轉(zhuǎn)變?yōu)榉沁B通圖所需要?jiǎng)h除節(jié)點(diǎn)數(shù)的最小值，直徑是任意兩節(jié)點(diǎn)之間最短路徑的最大值。圖的凝聚度與連通度成正比，與直徑成反比。

定義2 k-core：存在一個(gè)圖G(V，E)，V表示節(jié)點(diǎn)集，E表示節(jié)點(diǎn)間的邊集，d(v)表示節(jié)點(diǎn)v的度數(shù)。假設(shè)H是G的一個(gè)子圖，δ(H)表示H子圖的最小度，H中的每一個(gè)節(jié)點(diǎn)都至少有δ(H)個(gè)鄰接點(diǎn)；若H是G的一個(gè)引導(dǎo)子圖且δ(H)≥k，不包含于其余任意一個(gè)最小度大于等于k的引導(dǎo)子圖，則H子圖為圖G的一個(gè)k-core，用KG(V，E)表示[10]。

定義3 k-remainder：由k-core得到(k+1)-core的修剪過(guò)程中被刪除的節(jié)點(diǎn)集[10]。Rk表示節(jié)點(diǎn)集，rk表示相應(yīng)的節(jié)點(diǎn)數(shù)。

圖1用不同的空心圓(分別為J1,J2,J3)顯示k值分別取1、2、3時(shí)的k-core。由于任意節(jié)點(diǎn)v的d(v)≥1，所以每個(gè)節(jié)點(diǎn)都屬于1-core(由J1包圍)，R0為空集，r0=0。遞歸刪除d(v)<2的節(jié)點(diǎn)(圓形)后，其它節(jié)點(diǎn)d(v)≥2，形成2-core(由J2包圍)，同時(shí)被刪除的所有節(jié)點(diǎn)構(gòu)成1-remainder，由R1表示，R1=15。進(jìn)一步的修剪可以識(shí)別由三角形節(jié)點(diǎn)集所組成的3-core(由J3包圍)，同時(shí)在修剪過(guò)程中被刪除的所有菱形節(jié)點(diǎn)構(gòu)成2-remainder，由R2表示，R2=5。此時(shí)，如果繼續(xù)修剪，在從3-core中得到4-core的過(guò)程中，所有三角形節(jié)點(diǎn)都將被刪除，所以圖1的kmax=3，且三角形節(jié)點(diǎn)構(gòu)成3-remainder，由R3表示，R3=9。從圖中可以明顯看出，如果一個(gè)節(jié)點(diǎn)屬于3-core，則它也屬于2-core和1-core。根據(jù)以上例證可以看出，處于核心位置的節(jié)點(diǎn)往往具有較高的k值。

圖1 k-core分解

定義4 核塌縮序列：CCS(core collpase sequences)[10]可以直觀展現(xiàn)一個(gè)圖網(wǎng)絡(luò)的凝聚度分布，表示為 {Rk/|V(G)|}，其中|V(G)|為圖G的總節(jié)點(diǎn)數(shù)，k值上限為圖G所包含的最小k-core的k值。以圖1為例，整個(gè)圖網(wǎng)絡(luò)的節(jié)點(diǎn)總數(shù)為30，其中R0=0，R1=15，R2=5，R3=9，則該網(wǎng)絡(luò)的CCS為 {0，1/2，1/6，3/10}。

k-core分解可以將網(wǎng)絡(luò)劃分為凝聚度不同的子網(wǎng)。k值越大，子網(wǎng)的凝聚度就越高。CCS直觀地展示了凝聚度從弱到強(qiáng)的子網(wǎng)在整個(gè)網(wǎng)絡(luò)的規(guī)模占比，反應(yīng)了整個(gè)網(wǎng)絡(luò)圖的節(jié)點(diǎn)分布結(jié)構(gòu)。

本文在傳統(tǒng)k-core分解的基礎(chǔ)上采用模糊k-core分解的方法，使更多的高重要性節(jié)點(diǎn)得以保留在k-core子圖中。

1.2 傳統(tǒng)模糊理論

模糊集理論對(duì)經(jīng)典集合理論的擴(kuò)展，最主要的貢獻(xiàn)在于引入了集合中元素對(duì)該集合的隸屬度[11]。

定義5 隸屬度：主要通過(guò)隸屬函數(shù)A(x)表示。用取值于區(qū)間[0，1]的隸屬度函數(shù)A(x)表征x∈A的程度高低。A(x)越接近于1，表示x∈A的程度越高，A(x)越接近于0表示x∈A的程度越低。

“粒度”源于模糊集理論[12]，對(duì)于粒度的計(jì)算是一種來(lái)自不同層次，不同視角的思維方式[13,14]。k-core中也存在粒度，其將原始網(wǎng)絡(luò)劃分為多個(gè)子網(wǎng)絡(luò)，每個(gè)具有不同k值的子網(wǎng)都代表一個(gè)粒度層。k值越大，子網(wǎng)中的節(jié)點(diǎn)數(shù)越少，子網(wǎng)中的節(jié)點(diǎn)重要性越高。

本文通過(guò)使用模糊k-core分解，將原網(wǎng)絡(luò)劃分為多粒度網(wǎng)絡(luò)，相較于傳統(tǒng)k-core分解的嚴(yán)格劃分，此多粒度網(wǎng)絡(luò)能更大程度地保留高重要性節(jié)點(diǎn)，更能從局部體現(xiàn)整個(gè)網(wǎng)絡(luò)的社區(qū)分布。

2 基于模糊k-core的社區(qū)發(fā)現(xiàn)算法設(shè)計(jì)

2.1 問(wèn)題描述

整個(gè)算法包括模糊k-core分解，子圖社區(qū)劃分和社區(qū)標(biāo)簽擴(kuò)散3個(gè)步驟。首先對(duì)目標(biāo)圖網(wǎng)絡(luò)進(jìn)行模糊k-core分解，得到整個(gè)網(wǎng)絡(luò)的核心節(jié)點(diǎn)集(即模糊k-core子圖)；之后對(duì)核心節(jié)點(diǎn)集進(jìn)行社區(qū)劃分，使每個(gè)節(jié)點(diǎn)得到社區(qū)標(biāo)簽；最后將社區(qū)標(biāo)簽擴(kuò)散到網(wǎng)絡(luò)中其余所有節(jié)點(diǎn)，完成整個(gè)網(wǎng)絡(luò)的社區(qū)劃分。大致流程如圖2所示。

圖2 算法流程

2.2 模糊k-core分解

盡管k-core表示的概念很明確，每個(gè)節(jié)點(diǎn)與集合的隸屬關(guān)系也很清楚，可以很好地將重要性不同的節(jié)點(diǎn)劃分為不同的網(wǎng)絡(luò)層，但是k-core分解在捕獲節(jié)點(diǎn)重要性方面存在一些問(wèn)題，即其遞歸修剪過(guò)程過(guò)于嚴(yán)格，導(dǎo)致一些重要性高的節(jié)點(diǎn)沒(méi)有保留在k-core網(wǎng)絡(luò)中。由于并非所有概念都適合進(jìn)行清晰的劃分，為了捕獲更多的高重要性節(jié)點(diǎn)，本文提出基于k-core分解的模糊劃分。

如圖3所示，要獲得2-core子圖，就必須在經(jīng)過(guò)遞歸修剪過(guò)后，所有節(jié)點(diǎn)的度數(shù)都大于或等于2。圖3(a)描述了從1-core到2-core的第一次修剪過(guò)程。圖3(b)為經(jīng)過(guò)完整遞歸修剪過(guò)后的2-core子圖。在原始網(wǎng)絡(luò)G中，d(v1)=6，d(v2)=7，兩個(gè)節(jié)點(diǎn)的度數(shù)在圖G中屬于較大范疇，表明節(jié)點(diǎn)v1和v2在網(wǎng)絡(luò)中是高重要性節(jié)點(diǎn)。但根據(jù)k-core分解的定義，節(jié)點(diǎn)v1和v2在2-core的生成過(guò)程中將被刪除。為了更好地篩選出高重要性節(jié)點(diǎn)，需要在k-core分解算法基礎(chǔ)上，采用模糊函數(shù)對(duì)節(jié)點(diǎn)進(jìn)行二次判斷。

圖3 從1-core到2-core的分解過(guò)程

盡管k-core表示的概念很明確，每個(gè)節(jié)點(diǎn)與集合的隸屬關(guān)系也很清楚，可以很好地將重要性不同的節(jié)點(diǎn)劃分為不同的網(wǎng)絡(luò)層，但是k-core分解在捕獲節(jié)點(diǎn)重要性方面存在一些問(wèn)題，即其遞歸修剪過(guò)程過(guò)于嚴(yán)格，導(dǎo)致一些重要性高的節(jié)點(diǎn)沒(méi)有保留在k-core網(wǎng)絡(luò)中。由于并非所有概念都適合進(jìn)行清晰的劃分，為了捕獲更多的高重要性節(jié)點(diǎn)，本文提出基于k-core分解的模糊劃分。

模糊k-core分解關(guān)于隸屬度的模糊函數(shù)表示如下

d(v)d=d(v)-d(v)r

(1)

(2)

節(jié)點(diǎn)v為圖G中任意節(jié)點(diǎn)，d(v)表示節(jié)點(diǎn)v在完整網(wǎng)絡(luò)中的度數(shù)，d(v)r表示節(jié)點(diǎn)v在嚴(yán)格k-core分解過(guò)程中將會(huì)被刪除時(shí)的度數(shù)，d(v)d表示節(jié)點(diǎn)v原始度數(shù)與被k-core分解刪除時(shí)的度數(shù)之差，A(v)k為節(jié)點(diǎn)v的隸屬度，表示其隸屬于k-core的概率，其中b=2k。當(dāng)A(v)k≥0.5時(shí)，節(jié)點(diǎn)v屬于k-core。當(dāng)k=3時(shí)，將節(jié)點(diǎn)v保留在k-core子圖的條件是d(v)d≥5；當(dāng)k=5時(shí)，節(jié)點(diǎn)v保留在k-core子圖的條件是d(v)d≥8。與嚴(yán)格的k-core分解修剪條件相比，此模糊函數(shù)能保留更多的高重要性節(jié)點(diǎn)，k值越大時(shí)，效果越明顯。并且不會(huì)出現(xiàn)隸屬度值突增或者突減的情況，保證了不同k值下模糊匹配的平滑性。

若在k-core分解的基礎(chǔ)上附加模糊函數(shù)，就會(huì)對(duì)不同粒度層的k-core子圖進(jìn)行重新劃分，代表凝聚度分布的核塌縮序列也會(huì)相應(yīng)改變。如圖2和圖3所示，根據(jù)k-core分解的節(jié)點(diǎn)分配原則，節(jié)點(diǎn)v1和v2屬于R1，CCS為 {0，1/2，1/6，3/10}。根據(jù)模糊k-core分解的隸屬度函數(shù)對(duì)v1和v2進(jìn)行二次劃分后，節(jié)點(diǎn)v1被劃分到3-core，屬于R3；節(jié)點(diǎn)v2被劃分到4-core，屬于R4，并且其它節(jié)點(diǎn)同樣也會(huì)被隸屬度函數(shù)進(jìn)行重新劃分，比如節(jié)點(diǎn)v3原屬于3-core，被二次劃分到5-core，屬于R5。最終得到圖G的模糊子圖FKG(V，E)，其CCS為 {0，13/30，1/6，3/10，1/30，1/30}，可以看出，隨著模糊k-core分解的加入，CCS也能更詳細(xì)準(zhǔn)確地描述一個(gè)圖網(wǎng)絡(luò)的粒度層更豐富的凝聚度分布。

模糊k-core分解的算法過(guò)程如下：

算法1：模糊k-core分解

輸入：圖G(V，E)

輸出：模糊k-core子圖FKG(V，E)

(1)讀取數(shù)據(jù)集圖網(wǎng)絡(luò)G(V，E)；

(2) 對(duì)G(V，E)進(jìn)行模糊k-core分解；

(3)fori=1tokdo

(4)foreach nodevinVdo

(5)ifd(v)r≥ithen

(6) 保留該節(jié)點(diǎn)

(7)else

(8)ifd(v)

(9) 刪除該節(jié)點(diǎn)及其鄰邊//即該節(jié)點(diǎn)A(v)k=0

(10)else

(11)ifd(v)d

(13) 保留該節(jié)點(diǎn)

(14)else

(15) 刪除該節(jié)點(diǎn)及其鄰邊

(16)else

(17) 保留該節(jié)點(diǎn) //即該節(jié)點(diǎn)A(v)k=1

(18)endfor

(19)endfor

2.3 子圖社區(qū)劃分

存在一個(gè)圖G(V，E)，聚類算法在圖中找尋一種節(jié)點(diǎn)劃分方案，并為每個(gè)節(jié)點(diǎn)分配一個(gè)社區(qū)標(biāo)簽，擁有相同標(biāo)簽的節(jié)點(diǎn)共同形成一個(gè)集群，使得節(jié)點(diǎn)集被分割成n個(gè)不同的小集群C={C1，C2，C3，C4，……}，其中Cj?V且Cj≠?(i=1，2，3，4，……，n)，滿足Ci∩Cj=?(j=1，2，3，4，……，n且i≠j)，集合C被稱為圖G的一個(gè)社區(qū)結(jié)構(gòu)[15]。

模塊度Q是一種表示網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)強(qiáng)度的度量值，其取值范圍為[-1，1]，常用于衡量一個(gè)社區(qū)劃分結(jié)果的優(yōu)劣[5]。一個(gè)理想化的社區(qū)劃分，是社區(qū)內(nèi)部節(jié)點(diǎn)間相似度盡可能的高，同時(shí)社區(qū)外部節(jié)點(diǎn)間的相異度盡可能高，此時(shí)模塊度的值就越高。也就是說(shuō)，社區(qū)劃分的質(zhì)量越高對(duì)應(yīng)的模塊度Q越大[5]

(3)

Ai,j為網(wǎng)絡(luò)對(duì)應(yīng)鄰接矩陣中的一個(gè)元素，表示節(jié)點(diǎn)i與j之間的邊(可能存在，也可能不存在)

(4)

ci和cj分別是節(jié)點(diǎn)i和節(jié)點(diǎn)j所在的兩個(gè)社區(qū)，如果i和j在一個(gè)社區(qū)，即δ(ci，cj)則為1，否則為0。m表示網(wǎng)絡(luò)中所有邊的數(shù)量，ki表示所有與節(jié)點(diǎn)i相連的邊的數(shù)量(即節(jié)點(diǎn)i的度數(shù))

ki=∑j(Ai,j)

(5)

模塊度不僅可以用于衡量社區(qū)發(fā)現(xiàn)的優(yōu)劣，還可以作為目標(biāo)函數(shù)被優(yōu)化[16]。

圖G的模糊k-core子圖FKG(V，E)代表整個(gè)圖中重要性最高的節(jié)點(diǎn)集，對(duì)FKG(V，E)進(jìn)行局部劃分后再將標(biāo)簽擴(kuò)散到整個(gè)圖網(wǎng)絡(luò)，可以顯著降低運(yùn)算時(shí)間的同時(shí)保留或者提升社區(qū)劃分質(zhì)量。在本文提出的基于模糊k-core的社區(qū)發(fā)現(xiàn)算法中，對(duì)模糊k-core子圖進(jìn)行聚類的算法過(guò)程如下：

算法2：子圖社區(qū)劃分

輸入：模糊k-core子圖FKG(V，E)

輸出：社區(qū)結(jié)構(gòu)Cfk={C1，C2，C3，C4，……}

(1) 初始化: 為FKG(V，E)中的每個(gè)節(jié)點(diǎn)分配社區(qū)標(biāo)簽；

(2)do

(3) 計(jì)算社區(qū)結(jié)構(gòu)的模塊度Ql；

(4) 將每個(gè)節(jié)點(diǎn)劃分到其鄰接點(diǎn)所在社區(qū)，并計(jì)算模塊度QR

(5) ΔQ=QR-Ql

(6)While(ΔQ>0)do

(7) 保留當(dāng)前社區(qū)結(jié)構(gòu)

(8) 重復(fù)步驟(3)

(9)end

(10) 將同一社區(qū)節(jié)點(diǎn)集簡(jiǎn)化為單個(gè)節(jié)點(diǎn)

(11)While(ΔQ>0)

2.4 社區(qū)標(biāo)簽擴(kuò)散

由于模糊k-core子圖是整個(gè)圖網(wǎng)絡(luò)中重要性最高的節(jié)點(diǎn)集，這個(gè)節(jié)點(diǎn)集能夠代表整個(gè)圖網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)分布，即其余非模糊k-core子圖的所有節(jié)點(diǎn)都依附FKG(V，E)并隸屬于其社區(qū)劃分，所以可以根據(jù)模糊k-core子圖的標(biāo)簽分配結(jié)果推斷非FKG(V，E)節(jié)點(diǎn)的社區(qū)標(biāo)簽，從而完善并優(yōu)化整個(gè)圖的社區(qū)結(jié)構(gòu)。

首先，根據(jù)每個(gè)無(wú)標(biāo)簽節(jié)點(diǎn)的帶標(biāo)簽鄰接點(diǎn)數(shù)量，對(duì)所有無(wú)標(biāo)簽節(jié)點(diǎn)進(jìn)行降序排列。然后，按序列依次遍歷每個(gè)無(wú)標(biāo)簽節(jié)點(diǎn)，計(jì)算其鄰接點(diǎn)集中各標(biāo)簽的占比，為該節(jié)點(diǎn)分配占比最高的標(biāo)簽，直到所有節(jié)點(diǎn)都被分配到標(biāo)簽為止，完成整個(gè)圖網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)。算法過(guò)程如下：

算法3：社區(qū)標(biāo)簽擴(kuò)散

輸入：FKG(V，E)的社區(qū)結(jié)構(gòu)Cfk={Cfk1，Cfk2，Cfk3，Cfk4，…，Cfkn}

輸出：全網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)C={C1，C2，C3，C4，……，Cn}

(1)處理非FKG(V，E)節(jié)點(diǎn)集Vr；

(2)foreach nodevinVrdo

(3) 計(jì)算節(jié)點(diǎn)v帶標(biāo)簽的鄰接點(diǎn)數(shù)量

(4)endfor

(5) 對(duì)Vr中節(jié)點(diǎn)進(jìn)行降序排列，得到節(jié)點(diǎn)序列L

(6)fori=1tondo//n為L(zhǎng)中的節(jié)點(diǎn)數(shù)

(7) 計(jì)算節(jié)點(diǎn)vi的鄰接點(diǎn)集中各標(biāo)簽占比

(8) 為節(jié)點(diǎn)vi分配占比最高的標(biāo)簽

(9)endfor

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

本節(jié)通過(guò)在6個(gè)社會(huì)網(wǎng)絡(luò)數(shù)據(jù)集上的實(shí)驗(yàn)來(lái)驗(yàn)證基于模糊k-core的社區(qū)發(fā)現(xiàn)算法的有效性。第3.1節(jié)為實(shí)驗(yàn)準(zhǔn)備部分，介紹了實(shí)驗(yàn)環(huán)境。實(shí)驗(yàn)中使用的各類型的數(shù)據(jù)集，對(duì)比算法。模糊k-core分解的重要參數(shù)設(shè)置以及實(shí)驗(yàn)結(jié)果評(píng)價(jià)標(biāo)準(zhǔn)。本文將實(shí)驗(yàn)按照使用到的數(shù)據(jù)集規(guī)模大小分為兩部分，基于小數(shù)據(jù)集的實(shí)驗(yàn)將在第3.2節(jié)中詳細(xì)介紹，基于大數(shù)據(jù)集的實(shí)驗(yàn)將在第3.3節(jié)中詳細(xì)介紹。

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

實(shí)驗(yàn)的硬件環(huán)境為：Intel(R)Core(TM)i7-9700 @3.3 GHZ，RAM:16 GB，軟件環(huán)境為:Windows 10操作系統(tǒng)，編程語(yǔ)言為:Python。

本文選取了6個(gè)在復(fù)雜網(wǎng)絡(luò)領(lǐng)域常用的帶基準(zhǔn)的真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集對(duì)算法的有效性和準(zhǔn)確性進(jìn)行驗(yàn)證，見(jiàn)表1。這6個(gè)數(shù)據(jù)集都是無(wú)方向，無(wú)權(quán)值網(wǎng)絡(luò)，其中4個(gè)小數(shù)據(jù)集包括：

Karate網(wǎng)絡(luò)[17]是Zachary的一個(gè)空手道俱樂(lè)部的社交網(wǎng)絡(luò)，由34個(gè)節(jié)點(diǎn)和78條邊組成。節(jié)點(diǎn)表示該俱樂(lè)部成員，邊表示兩個(gè)節(jié)點(diǎn)成員是否在俱樂(lè)部之外有聯(lián)系。

Polbooks網(wǎng)絡(luò)[18]是美國(guó)的政治書(shū)籍所構(gòu)成的網(wǎng)絡(luò)，由105個(gè)節(jié)點(diǎn)和105條邊組成。節(jié)點(diǎn)表示Amazon.com所賣出的美國(guó)政治書(shū)籍，邊表示兩本書(shū)籍在購(gòu)買傾向上是相似的。

Football網(wǎng)絡(luò)[5]是美國(guó)職業(yè)足球隊(duì)所構(gòu)成的網(wǎng)絡(luò)，由115個(gè)節(jié)點(diǎn)和115條邊組成。節(jié)點(diǎn)表示每一個(gè)職業(yè)足球代表隊(duì)，邊表示兩個(gè)節(jié)點(diǎn)所代表的球隊(duì)至少進(jìn)行了一次比賽。

Dolphins網(wǎng)絡(luò)[19]是一些在一起生活的寬吻海豚所構(gòu)成的網(wǎng)絡(luò)，由62個(gè)節(jié)點(diǎn)和62條邊組成。節(jié)點(diǎn)代表每一只不同的海豚，邊表示兩個(gè)節(jié)點(diǎn)所代表的海豚經(jīng)常一起活動(dòng)。

另外還包括兩個(gè)相對(duì)較大的數(shù)據(jù)集，用于著重驗(yàn)證本文算法在運(yùn)算時(shí)間上的優(yōu)越性：

Amazon網(wǎng)絡(luò)[20]是由Amazon在線商城里所出售的商品所構(gòu)成的網(wǎng)絡(luò)，由334 863個(gè)節(jié)點(diǎn)和925 872條邊組成。節(jié)點(diǎn)表示每一個(gè)出售的商品，邊表示兩個(gè)節(jié)點(diǎn)所代表的商品經(jīng)常被一起購(gòu)買。

Youtube網(wǎng)絡(luò)[20]是由一個(gè)視頻分享網(wǎng)站所包含的社交網(wǎng)絡(luò)，由1 134 890個(gè)節(jié)點(diǎn)和2 987 624條邊組成。節(jié)點(diǎn)表示網(wǎng)站中每一個(gè)注冊(cè)用戶，邊表示兩個(gè)節(jié)點(diǎn)所代表的用戶聯(lián)系緊密。

各數(shù)據(jù)集的規(guī)模見(jiàn)表1。

表1 實(shí)驗(yàn)數(shù)據(jù)集

實(shí)驗(yàn)選取了一共6種算法，包括Newman，LPA，louvain，Walktrap等經(jīng)典算法以及近期的CBV[21]和TS[22]算法，與本文所提出的基于模糊k-core的社區(qū)發(fā)現(xiàn)算法在相同的4個(gè)小數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)對(duì)比。其中，Newman算法是基于貪心算法的快速社區(qū)發(fā)現(xiàn)算法，LPA算法是基于節(jié)點(diǎn)標(biāo)簽的全局社區(qū)發(fā)現(xiàn)算法，louvain算法是以模塊度優(yōu)化為目標(biāo)的全局社區(qū)發(fā)現(xiàn)算法，Walktrap是基于節(jié)點(diǎn)間距離的社區(qū)發(fā)現(xiàn)算法。

本文實(shí)驗(yàn)用于驗(yàn)證算法的指標(biāo)包括模塊度Q，NMI以及運(yùn)算時(shí)間。

由于實(shí)驗(yàn)所使用的數(shù)據(jù)集均是帶有基準(zhǔn)信息的真實(shí)數(shù)據(jù)集，所以除了模塊度，本文也使用NMI[23]表示算法對(duì)網(wǎng)絡(luò)的劃分結(jié)果與網(wǎng)絡(luò)的真實(shí)劃分之間的差異，其取值范圍為[0，1]，定義如下

(6)

CA為真實(shí)劃分的社區(qū)數(shù)量，CB為算法所得劃分的社區(qū)數(shù)量，Nij表示在算法所劃分的社區(qū)j中屬于真實(shí)社區(qū)i的節(jié)點(diǎn)數(shù)量，Ni.表示矩陣Nij的第i行元素之和，而N.j則是第j列元素之和。算法所得劃分與真實(shí)社區(qū)越相近，NMI值就越大，當(dāng)算法所得劃分與真實(shí)社區(qū)完全一致時(shí)，NMI(A，B)等于1。

在本文所提出的基于模糊k-core的社區(qū)發(fā)現(xiàn)算法中，模糊k-core剪枝過(guò)程中k值的取值對(duì)于實(shí)驗(yàn)結(jié)果有著重要影響。算法的核心在于經(jīng)過(guò)模糊k-core修剪后所得到核心子圖。模糊k-core子圖的規(guī)模隨著k值的增加而減小，即k值越大，算法所得到的子圖就越趨近網(wǎng)絡(luò)核心，越有利于挖掘出網(wǎng)絡(luò)的核心節(jié)點(diǎn)集，在進(jìn)行局部社區(qū)劃分時(shí)所需要的運(yùn)算時(shí)間就越少，但在算法的社區(qū)標(biāo)簽擴(kuò)散階段則需要更多的計(jì)算，所以k的取值需要取得一個(gè)平衡，使得算法在精確度和運(yùn)算時(shí)間上達(dá)到一個(gè)最佳平衡，基于此目的，本文提出節(jié)點(diǎn)剩余率指標(biāo)(子圖節(jié)點(diǎn)數(shù)/節(jié)點(diǎn)總數(shù))，通過(guò)該指標(biāo)，能夠快速的計(jì)算出各數(shù)據(jù)集的最佳k值。

表2列出了當(dāng)k值取不同的特定值時(shí)，各數(shù)據(jù)集在模糊k-core子圖中的節(jié)點(diǎn)剩余率，直觀地顯示各數(shù)據(jù)集節(jié)點(diǎn)度數(shù)的分布情況，即相同k值下，節(jié)點(diǎn)剩余率越高，網(wǎng)絡(luò)的平均度數(shù)越高，節(jié)點(diǎn)間的聯(lián)系就越緊密。在針對(duì)不同數(shù)據(jù)集進(jìn)行模糊k-core分解時(shí)，該數(shù)據(jù)集的節(jié)點(diǎn)剩余率是一個(gè)非常重要的參考數(shù)值，能夠迅速確定算法最佳k值的具體范圍，顯著降低最佳k值的計(jì)算時(shí)間。

3.2 基于小數(shù)據(jù)集的算法精確性驗(yàn)證

圖4、圖5展示了本文所提出的基于模糊k-core的社區(qū)發(fā)現(xiàn)算法分別在Karate，Polbooks，F(xiàn)ootball和Dolphins這4個(gè)數(shù)據(jù)集上所得到模塊度和NMI隨著k值不同的變化趨勢(shì)。表示精確度的模塊度和NMI值在不同的數(shù)據(jù)集上隨著k值的增加都有不同程度的變化。結(jié)合表2可知，當(dāng)占比率大于0.6時(shí)，模塊度值的變化相對(duì)很小，并隨著占比率的下降平緩降低。而NMI值在變化曲線上則更加復(fù)雜一些。綜合兩個(gè)精確度量值，可以得到各數(shù)據(jù)集的最優(yōu)k值，見(jiàn)表3。

表2 各數(shù)據(jù)集在模糊k-core子圖中的節(jié)點(diǎn)剩余率

圖4 小數(shù)據(jù)集不同k值下的模塊度變化

圖5 小數(shù)據(jù)集不同k值下的NMI變化

表3 各數(shù)據(jù)集最優(yōu)k值

根據(jù)上文所得最優(yōu)k值，將本文所提出的基于模糊k-core的社區(qū)發(fā)現(xiàn)算法與Newman，LPA，Louvain，Walktrap，CTS和TS這6個(gè)算法在Karate，Polbooks，F(xiàn)ootball和Dolphins這4個(gè)數(shù)據(jù)集上進(jìn)行算法精確度對(duì)比，對(duì)比實(shí)驗(yàn)結(jié)果見(jiàn)表4。

通過(guò)表4中的對(duì)比可以看出，本文提出的基于模糊k-core的社區(qū)發(fā)現(xiàn)算法在4個(gè)數(shù)據(jù)集的對(duì)比中綜合效果最好，說(shuō)明本算法在社區(qū)劃分與聚類的質(zhì)量上取得了較好的結(jié)果。具體表現(xiàn)為，在Karate數(shù)據(jù)集的對(duì)比中，本算法與Louvain算法在NMI值上并列第一，模塊度與TS算法并列第一；Polbooks數(shù)據(jù)集的對(duì)比中，算法在NMI值上與Walktrap算法并列第一并遠(yuǎn)高于其它算法，模塊度方面則與大部分算法持平；在Football數(shù)據(jù)集的對(duì)比中，本算法在模塊度上和大部分算法持平，但在NMI上稍落后于所對(duì)比的算法；而在Dolphins數(shù)據(jù)集的對(duì)比中，本算法在模塊度和NMI上都與效果最好的幾個(gè)算法持平。

表4 小數(shù)據(jù)集實(shí)驗(yàn)對(duì)比數(shù)據(jù)

3.3 基于大數(shù)據(jù)集的算法效率驗(yàn)證

圖6、圖7展示了本文所提出的基于模糊k-core的社區(qū)發(fā)現(xiàn)算法分別在Amazon和Youtube這兩個(gè)數(shù)據(jù)集上所得到模塊度和所需運(yùn)算時(shí)間隨著k值不同的變化趨勢(shì)。

圖6 大數(shù)據(jù)集不同k值下的模塊度變化

圖7 大數(shù)據(jù)集不同k值下的運(yùn)算時(shí)間變化

在Amazon和Youtube這兩個(gè)數(shù)據(jù)集上，模塊度和運(yùn)算時(shí)間隨著k值的增加都有不同程度的下降。隨著k值的增加，相對(duì)于模塊度的緩慢下降，運(yùn)算時(shí)間出現(xiàn)大幅度下降，特別是k值從2到10的變化趨勢(shì)尤其顯著，然后k值從11到20時(shí)逐漸緩和。所以對(duì)于這兩個(gè)大規(guī)模數(shù)據(jù)集，為了追求計(jì)算效率，設(shè)置k=10的值是比較理想的方式。

為了展示本文提出的基于模糊k-core的社區(qū)發(fā)現(xiàn)算法在運(yùn)行時(shí)間上的優(yōu)越性，將與GN，LPA和Louvain這3個(gè)經(jīng)典算法在SNAP所提供的Amazon和Youtube兩個(gè)大規(guī)模數(shù)據(jù)集上進(jìn)行模塊度和運(yùn)算時(shí)間的對(duì)比，見(jiàn)表5。

表5 大數(shù)據(jù)集實(shí)驗(yàn)對(duì)比

通過(guò)表5的對(duì)比結(jié)果可以看出，由于GN算法和LPA算法分別是自頂向下和自底向上的全局貪心算法，且沒(méi)有明確的衡量劃分好壞的終止指標(biāo)，所以其時(shí)間性能明顯較差。Louvain算法在此基礎(chǔ)上添加了模塊度這一標(biāo)準(zhǔn)，相比GN和LPA，明顯提高了算法的劃分精度和時(shí)間性能。但以上3個(gè)算法都針對(duì)全網(wǎng)的社區(qū)劃分，本文所提出的基于模糊k-core的社區(qū)發(fā)現(xiàn)算法則是以局部社區(qū)劃分為核心的算法，實(shí)驗(yàn)數(shù)據(jù)表明，本算法在保持算法精度的同時(shí)，大幅度減少了運(yùn)算時(shí)間，極大地增加了對(duì)大數(shù)據(jù)集進(jìn)行社區(qū)劃分的計(jì)算效率。

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

本文在標(biāo)準(zhǔn)k-core分解算法的修剪規(guī)則上融合了基于模糊集理論的隸屬度概念，提出了一種以模糊k-core分解為核心的局部社區(qū)發(fā)現(xiàn)算法。算法提出了一種隸屬度方程，通過(guò)利用隸屬度方程對(duì)被k-core分解所刪除的節(jié)點(diǎn)進(jìn)行二次判斷，最終確定是否將該節(jié)點(diǎn)保留在當(dāng)前粒度層，優(yōu)化了k-core分解的對(duì)節(jié)點(diǎn)重要性判斷的缺陷，使得更多的高重要節(jié)點(diǎn)得以保留在核心節(jié)點(diǎn)集。對(duì)模糊k-core子網(wǎng)進(jìn)行局部社區(qū)劃分后，將劃分的社區(qū)標(biāo)簽按照鄰接點(diǎn)集中的權(quán)重占比進(jìn)行標(biāo)簽擴(kuò)散，最終完成全局社區(qū)發(fā)現(xiàn)。與其它社區(qū)發(fā)現(xiàn)領(lǐng)域的經(jīng)典算法和近期提出的算法相比可知，本算法在社區(qū)發(fā)現(xiàn)的精確度和運(yùn)行時(shí)間上都有著更好的表現(xiàn)。但本算法目前沒(méi)有考慮網(wǎng)絡(luò)中社區(qū)的重疊性，通過(guò)識(shí)別社區(qū)是否重疊，然后將重疊社區(qū)分解成為非重疊社區(qū)以進(jìn)一步提高社區(qū)發(fā)現(xiàn)的精確度是今后研究的主要方向。