基于結(jié)構(gòu)與屬性的社區(qū)劃分方法

萬(wàn)新貴,李玲娟

(南京郵電大學(xué) 計(jì)算機(jī)學(xué)院,江蘇 南京 210003)

基于結(jié)構(gòu)與屬性的社區(qū)劃分方法

萬(wàn)新貴,李玲娟

(南京郵電大學(xué) 計(jì)算機(jī)學(xué)院,江蘇 南京 210003)

目前通行的社區(qū)劃分方法大多基于結(jié)構(gòu)，但單純基于結(jié)構(gòu)的劃分不能挖掘出社區(qū)對(duì)象的潛在關(guān)系，因而不能發(fā)現(xiàn)社區(qū)的變化趨勢(shì)。為此，提出了基于結(jié)構(gòu)的社區(qū)劃分算法(Community Division based on Structure,CDS)。該算法利用度和節(jié)點(diǎn)歐氏距離對(duì)社會(huì)網(wǎng)絡(luò)進(jìn)行結(jié)構(gòu)劃分；同時(shí)針對(duì)經(jīng)典K-means算法在社區(qū)劃分中所存在的隨機(jī)選取初始中心點(diǎn)以及k值選取不合理所導(dǎo)致的聚類結(jié)果不佳問(wèn)題，提出了一種基于社區(qū)結(jié)構(gòu)的非人為設(shè)定k值的K-means算法—NPCluster(Non Presetting Cluster)算法。該算法基于由CDS算法所提到的社區(qū)結(jié)構(gòu)，依次選取度最大的節(jié)點(diǎn)作為聚類中心點(diǎn)，以小于平均特征歐氏距離為基準(zhǔn)合并簇集，反復(fù)迭代直至聚類完成。理論分析和對(duì)比實(shí)驗(yàn)結(jié)果表明，CDS算法能夠有效劃分出社區(qū)結(jié)構(gòu)；相對(duì)于K-means算法，NPCluster算法在已劃分的社區(qū)結(jié)構(gòu)上具有更高的聚類精度和更好的時(shí)效性；結(jié)構(gòu)與屬性相結(jié)合的社區(qū)劃分方法是有效可行的。

社區(qū)劃分；度；K-means；中心點(diǎn)；歐氏距離

0 引 言

在社會(huì)網(wǎng)絡(luò)研究[1-3]中關(guān)心的兩個(gè)方面是聯(lián)系和結(jié)構(gòu)。目前基于結(jié)構(gòu)角度的社區(qū)劃分研究比較充分，但是單純基于結(jié)構(gòu)的劃分(稱為硬劃分)對(duì)社區(qū)內(nèi)對(duì)象的潛在關(guān)系(比如興趣的異同等)表現(xiàn)不夠。而這種潛在關(guān)系的發(fā)現(xiàn)(稱為軟劃分)對(duì)預(yù)測(cè)社會(huì)網(wǎng)絡(luò)社區(qū)的變化趨勢(shì)有著重要的參考價(jià)值。

數(shù)據(jù)挖掘(Data Mining)[4]一般是指從大量的數(shù)據(jù)中通過(guò)算法搜索隱藏于其中信息的過(guò)程。聚類挖掘[5]是數(shù)據(jù)挖掘的算法之一，它將大量的數(shù)據(jù)劃分為性質(zhì)相同的子類，以便于了解數(shù)據(jù)的分布情況，挖掘結(jié)果具有簇內(nèi)高相似性和簇間低相似性，聚類挖掘的性質(zhì)相當(dāng)符合社會(huì)網(wǎng)絡(luò)社區(qū)的特點(diǎn)。

聚類挖掘算法[6]主要分為四大類：基于劃分的聚類算法、基于層次的聚類算法、基于密度的聚類算法以及基于網(wǎng)格的聚類算法。不同類別的聚類算法適用于不同的應(yīng)用場(chǎng)景。K-means算法[7]作為聚類算法中經(jīng)典的劃分算法，其最大優(yōu)勢(shì)在于簡(jiǎn)潔和快速，在實(shí)踐中應(yīng)用廣泛。該算法簡(jiǎn)單，易于理解和可擴(kuò)展，并且很容易修改以便處理不同的數(shù)據(jù)，例如無(wú)監(jiān)督性學(xué)習(xí)或流數(shù)據(jù)。但K-means算法仍有值得改進(jìn)的地方，隨機(jī)選擇中心點(diǎn)以及人為設(shè)定k值是K-means算法最大的缺陷，針對(duì)這些缺陷，提出了許多改進(jìn)算法[8-12]。

為了將軟劃分與硬劃分進(jìn)行有效結(jié)合，設(shè)計(jì)了社區(qū)結(jié)構(gòu)建立算法(Community Division based on Structure，CDS)。該算法利用節(jié)點(diǎn)度與節(jié)點(diǎn)歐氏距離實(shí)現(xiàn)了社區(qū)中心的選擇，完成了社區(qū)結(jié)構(gòu)的建立；并基于CDS算法，提出一種非人為預(yù)先設(shè)定k值的聚類算法—NPCluster(Non Presetting ClusterK-means)。該算法的原理與CDS算法類似，同樣基于節(jié)點(diǎn)度設(shè)置聚類中心，避免了k值的不合理設(shè)置導(dǎo)致的聚類結(jié)果不理想；基于特征歐氏距離進(jìn)行聚類，實(shí)現(xiàn)多維數(shù)據(jù)集的類別劃分。兩種算法總體實(shí)現(xiàn)了社會(huì)網(wǎng)絡(luò)的硬劃分與軟劃分的結(jié)合。

1 相關(guān)工作

1.1 基本定義

定義1(特征歐氏距離)：數(shù)據(jù)集中每個(gè)數(shù)據(jù)點(diǎn)可以定義為Xi=(Xi1,Xi2,…,Xid)，d為數(shù)據(jù)點(diǎn)的維度，即特征的個(gè)數(shù)，則特征歐幾里得距離的計(jì)算公式為：

(1)

D值越小，代表兩個(gè)數(shù)據(jù)點(diǎn)的特征相似度越大，從而可以將這兩個(gè)數(shù)據(jù)點(diǎn)劃分到一個(gè)簇集中。

定義2(節(jié)點(diǎn)歐氏距離)：假設(shè)有M個(gè)節(jié)點(diǎn)，可以把節(jié)點(diǎn)集定義為X=(X1,X2,…,Xm)，Xij表示節(jié)點(diǎn)Xi到Xj的最短距離(跳數(shù))，則節(jié)點(diǎn)歐氏距離定義為：

(2)

D值越小，代表兩個(gè)節(jié)點(diǎn)的相似度越大，從而可以將這兩個(gè)節(jié)點(diǎn)劃入同一個(gè)社區(qū)結(jié)構(gòu)中。

定義3(歐氏距離矩陣及平均歐氏距離)：在數(shù)據(jù)集中，數(shù)據(jù)點(diǎn)兩兩之間的特征歐氏距離形成特征歐氏距離矩陣；在無(wú)向圖中的定義與在數(shù)據(jù)集中的定義大致相同，以下特征歐氏距離與節(jié)點(diǎn)歐氏距離統(tǒng)稱歐氏距離。

平均歐氏距離是由歐氏距離矩陣決定的，將歐氏距離矩陣求和再除以數(shù)據(jù)點(diǎn)數(shù)，得到平均歐氏距離。隨著迭代過(guò)程的進(jìn)行，數(shù)據(jù)點(diǎn)逐漸減少，歐氏距離矩陣將隨數(shù)據(jù)點(diǎn)的變動(dòng)進(jìn)行更新，平均歐氏距離也會(huì)隨之改變。

定義4(度及度的計(jì)算)：在無(wú)向圖中，每個(gè)節(jié)點(diǎn)連邊的條數(shù)就是該節(jié)點(diǎn)的度數(shù)。

度的計(jì)算是根據(jù)節(jié)點(diǎn)的關(guān)系矩陣R來(lái)確定的，點(diǎn)Xi與Xj之間有邊，則rij=1，反之rij=0。按行讀取矩陣R，將i行中的值相加，即得到點(diǎn)Xi的度。

1.2 社區(qū)劃分

現(xiàn)實(shí)世界中，社會(huì)網(wǎng)絡(luò)[1,13]以各種關(guān)系網(wǎng)絡(luò)存在于多個(gè)領(lǐng)域，社會(huì)網(wǎng)絡(luò)分析已經(jīng)成為數(shù)據(jù)挖掘中的一個(gè)研究熱點(diǎn)，而社區(qū)劃分則是社會(huì)網(wǎng)絡(luò)分析中的一項(xiàng)重要內(nèi)容。社區(qū)發(fā)現(xiàn)的研究已取得了很多成果，使用聚類算法進(jìn)行社區(qū)劃分的研究比較普遍。

大多數(shù)實(shí)際網(wǎng)絡(luò)都有一個(gè)共同的性質(zhì)，即社區(qū)結(jié)構(gòu)。整個(gè)網(wǎng)絡(luò)就是由若干個(gè)“社區(qū)”或“組”構(gòu)成的，而這些社區(qū)則具有社區(qū)內(nèi)部高內(nèi)聚、社區(qū)之間低內(nèi)聚的特性，所以揭示網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)對(duì)于深入了解網(wǎng)絡(luò)結(jié)構(gòu)與分析網(wǎng)絡(luò)特性是很重要的。

在社區(qū)劃分的研究中，社區(qū)劃分的算法所要?jiǎng)澐值木W(wǎng)絡(luò)大致分為兩類：比較常見(jiàn)的網(wǎng)絡(luò)(僅包含正聯(lián)系的網(wǎng)絡(luò))和符號(hào)社會(huì)網(wǎng)絡(luò)(網(wǎng)絡(luò)中既包含正向聯(lián)系的邊，也包含負(fù)向聯(lián)系的邊)。

社區(qū)劃分算法有很多種，比較經(jīng)典的三種是[14]：Kernighan-Lin算法、基于Laplace圖特征值的譜二分法和GN算法。

1.3K-means算法

K-means算法是一種基于樣本間相似性度量的間接聚類方法，屬于非監(jiān)督學(xué)習(xí)方法。此算法以k為參數(shù)，將n個(gè)對(duì)象分為k個(gè)簇，以使簇內(nèi)相似度較高，而簇間相似度較低。

K-means算法描述如下：

算法1：K-means算法。

輸入：數(shù)據(jù)集，k值；

輸出：簇集。

(1)適當(dāng)選擇k個(gè)類的初始中心；

(2)在第m次迭代中，對(duì)任意一個(gè)樣本，求其到k的歐氏距離，將該樣本歸到距離最短的中心所在的類；

(3)利用均值更新該類的中心值；

(4)對(duì)于所有的k個(gè)聚類中心，如果利用步驟2和步驟3迭代更新后，值保持不變，則迭代結(jié)束，否則繼續(xù)迭代。

K-means算法需要人為確定k值的大小，并且算法隨機(jī)選取初始簇心，對(duì)初始簇心非常敏感，因此針對(duì)K-means算法的改進(jìn)主要從這兩方面入手。

2 CDS算法

2.1 算法基本思想

基于硬劃分方法產(chǎn)生的社區(qū)結(jié)構(gòu)是進(jìn)行軟劃分的基礎(chǔ)。因此，首先設(shè)計(jì)一種建立社區(qū)結(jié)構(gòu)的算法-CDS算法。該算法的基本思想是：首先計(jì)算各節(jié)點(diǎn)的度值，選取度值最大的節(jié)點(diǎn)作為中心節(jié)點(diǎn)；然后計(jì)算所有節(jié)點(diǎn)之間的歐氏距離，形成節(jié)點(diǎn)歐氏距離矩陣，計(jì)算得出平均節(jié)點(diǎn)歐氏距離；將除中心節(jié)點(diǎn)以外的節(jié)點(diǎn)與中心節(jié)點(diǎn)的節(jié)點(diǎn)歐氏距離進(jìn)行比對(duì)，當(dāng)節(jié)點(diǎn)歐氏距離小于平均節(jié)點(diǎn)歐氏距離時(shí)，將此節(jié)點(diǎn)納入該中心節(jié)點(diǎn)所在的社區(qū)，算法迭代至所有節(jié)點(diǎn)都被納入社區(qū)。

以節(jié)點(diǎn)度的大小作為中心點(diǎn)的選擇依據(jù)，符合社會(huì)網(wǎng)絡(luò)中度越大凝聚力越強(qiáng)的物理意義；以平均節(jié)點(diǎn)歐氏距離作為聚類的標(biāo)準(zhǔn)符合社會(huì)網(wǎng)絡(luò)中，距離同一節(jié)點(diǎn)的跳數(shù)越接近，節(jié)點(diǎn)之間越接近的物理意義。

2.2 算法流程與描述

CDS算法的主體流程如圖1所示。

圖1 CDS算法流程圖

CDS算法具體描述如下：

算法2：社區(qū)結(jié)構(gòu)建立算法。

輸入：一個(gè)無(wú)向無(wú)權(quán)網(wǎng)絡(luò)G=，V是節(jié)點(diǎn)集合，E是邊的集合；

輸出：網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)。

(1)計(jì)算所有節(jié)點(diǎn)的度degree；

(2)找出現(xiàn)有節(jié)點(diǎn)中degree最大的節(jié)點(diǎn)，設(shè)置為中心節(jié)點(diǎn)k；

(3)計(jì)算所有節(jié)點(diǎn)的節(jié)點(diǎn)歐氏距離矩陣；

(4)計(jì)算節(jié)點(diǎn)集中節(jié)點(diǎn)的平均歐氏距離AveD，將之設(shè)定為臨界值T；

(5)將各個(gè)非中心節(jié)點(diǎn)與中心節(jié)點(diǎn)的歐氏距離與T進(jìn)行比較，若小于T，則將該點(diǎn)加入社區(qū)結(jié)構(gòu)，在節(jié)點(diǎn)集中刪除該點(diǎn)；

(6)重復(fù)步驟4和5，當(dāng)節(jié)點(diǎn)集中沒(méi)有節(jié)點(diǎn)時(shí)，社區(qū)劃分完成。

3 NPCluster算法

3.1 NPCluster算法思想

K-means算法的k值需事先確定，自主設(shè)定k值并不能保證合理性。假設(shè)被聚類的數(shù)據(jù)集中的數(shù)據(jù)點(diǎn)之間已經(jīng)非?？拷恍枰M(jìn)一步分類，但是由于人為設(shè)定的k值，數(shù)據(jù)集被聚集為k類。顯然上述算法得到的結(jié)果是不合理的。針對(duì)這種情況，提出一種基于已建立的社區(qū)結(jié)構(gòu)的非人為預(yù)先設(shè)定k值的聚類算法-NPCluster算法。

在一個(gè)數(shù)據(jù)集(社區(qū))中，某個(gè)數(shù)據(jù)點(diǎn)(節(jié)點(diǎn))的度直接反映了這個(gè)點(diǎn)在該社區(qū)中的結(jié)構(gòu)地位，即度越大，這個(gè)點(diǎn)越靠近所在社區(qū)的中心。若根據(jù)度來(lái)選擇聚類中心，即可避免人為確定k值和隨機(jī)選擇聚類中心點(diǎn)。兩個(gè)數(shù)據(jù)點(diǎn)之間的距離一般用特征歐氏距離表示，特征歐氏距離越小，表示這兩個(gè)點(diǎn)越靠近。如果用數(shù)據(jù)點(diǎn)的多維特征作為數(shù)據(jù)點(diǎn)歐氏距離計(jì)算的基礎(chǔ)，那么有理由相信，特征歐氏距離越小，兩者的整體特征越接近。所以，以度作為中心點(diǎn)的選擇，以特征歐氏距離作為聚類閾值的算法思想是可行的，并且同時(shí)兼顧了社會(huì)網(wǎng)絡(luò)的結(jié)構(gòu)和內(nèi)在關(guān)系兩個(gè)方面。

NPCluster算法的基本思想是：首先計(jì)算數(shù)據(jù)點(diǎn)的特征歐氏距離矩陣，求得平均特征歐氏距離；然后選取度最大的數(shù)據(jù)點(diǎn)作為聚類中心點(diǎn)，將剩余數(shù)據(jù)點(diǎn)與中心點(diǎn)的特征歐氏距離與平均特征歐氏距離進(jìn)行比對(duì)，若小于平均特征歐氏距離，則將該點(diǎn)劃入中心點(diǎn)所在簇；迭代直至所有數(shù)據(jù)點(diǎn)都被劃分，最后一個(gè)簇內(nèi)的數(shù)據(jù)點(diǎn)在特定情況下可以視為孤立點(diǎn)。

該算法結(jié)合了數(shù)據(jù)點(diǎn)的結(jié)構(gòu)關(guān)系和特征關(guān)系，基于這種聚類的社區(qū)劃分是一種軟硬劃分的結(jié)合，聚類結(jié)果更符合社區(qū)的物理意義，也有其特殊的應(yīng)用價(jià)值。由于NPCluster算法必須基于已建立的社區(qū)結(jié)構(gòu)，所以算法的聚類結(jié)果會(huì)受到社區(qū)結(jié)構(gòu)的影響，并且該算法不適用于一般無(wú)結(jié)構(gòu)的數(shù)據(jù)集，僅適用于社會(huì)網(wǎng)絡(luò)。

3.2 NPCluster算法流程與描述

NPCluster算法的主體流程如圖2所示。

NPCluster算法的具體描述如下：

算法3：NPCluster算法。

輸入：數(shù)據(jù)集；

輸出：簇集。

(1)計(jì)算所有數(shù)據(jù)點(diǎn)的度degree；

(2)選取現(xiàn)有數(shù)據(jù)點(diǎn)中度值最大的數(shù)據(jù)點(diǎn)，設(shè)置為簇心k；

(3)計(jì)算所有數(shù)據(jù)點(diǎn)的特征歐氏距離矩陣；

(4)求出數(shù)據(jù)集中所有數(shù)據(jù)點(diǎn)的平均特征歐氏距離AveD，將之設(shè)定為臨界值T；

(5)將各非中心點(diǎn)與中心點(diǎn)的特征歐氏距離逐一與T進(jìn)行比較，若小于T，則將該點(diǎn)加入該簇，并將該點(diǎn)從數(shù)據(jù)集中刪除；

(6)重復(fù)步驟3～5，當(dāng)數(shù)據(jù)集中沒(méi)有數(shù)據(jù)點(diǎn)時(shí)，聚類結(jié)束。

圖2 NPCluster算法流程圖

實(shí)現(xiàn)該算法的程序中涉及到的方法主要有：

(1)caldistance(String file)方法：根據(jù)多維特征計(jì)算所有數(shù)據(jù)點(diǎn)之間的特征歐氏距離，形成特征歐氏距離矩陣；

(2)avgdistance(double[][] a)方法：根據(jù)已得出的歐氏距離矩陣與數(shù)據(jù)點(diǎn)的數(shù)量，計(jì)算所有數(shù)據(jù)點(diǎn)的平均特征歐氏距離；

(3)Caldegree(String file)方法：根據(jù)度矩陣計(jì)算所有數(shù)據(jù)點(diǎn)的度；

(4)findmaxdegree(Mapm1)方法：根據(jù)已得出的數(shù)據(jù)點(diǎn)的度找出度最大的數(shù)據(jù)點(diǎn)。

通過(guò)這些方法，更易于理解NPCluster算法的核心思想。

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

4.1 CDS算法驗(yàn)證

考慮到NPCluster算法基于已建立的社區(qū)結(jié)構(gòu)，所以在NPCluster算法與K-means算法的對(duì)比實(shí)驗(yàn)前，需先驗(yàn)證CDS算法的正確性，以確保整體算法在無(wú)結(jié)構(gòu)數(shù)據(jù)集上仍然具備有效性。

CDS算法驗(yàn)證數(shù)據(jù)采用來(lái)自空手道俱樂(lè)部中的一個(gè)社區(qū)進(jìn)行實(shí)驗(yàn)，社區(qū)結(jié)構(gòu)圖如圖3所示，具體社區(qū)結(jié)構(gòu)如表1所示。

圖3 空手道社區(qū)結(jié)構(gòu)圖

社區(qū)數(shù)字社區(qū)110,15,16,19,21,23,24,25,26,27,28,29,30,31,32,33,34社區(qū)21,2,3,4,5,6,7,8,9,11,12,13,14,17,18,20,22

由圖3可以看出，實(shí)驗(yàn)數(shù)據(jù)基于結(jié)構(gòu)共分為兩個(gè)社區(qū)，圖中數(shù)字代表社區(qū)中的各節(jié)點(diǎn)。

CDS算法社區(qū)結(jié)構(gòu)劃分結(jié)果如圖4所示。

圖4 空手道社區(qū)結(jié)構(gòu)劃分圖

由圖4與表1的對(duì)比可以看出，節(jié)點(diǎn)10被劃分錯(cuò)誤，節(jié)點(diǎn)29和31被同時(shí)劃分到兩個(gè)社區(qū)中，經(jīng)過(guò)計(jì)算得到CDS算法社區(qū)結(jié)構(gòu)劃分的正確率達(dá)到97.06%，實(shí)驗(yàn)結(jié)果表明CDS算法是有效的。

4.2 NPCluster算法性能驗(yàn)證

NPCluster算法與K-means算法的對(duì)比實(shí)驗(yàn)采用校內(nèi)網(wǎng)離散型數(shù)據(jù)集，該數(shù)據(jù)集共7 000條6維數(shù)據(jù)。使用CDS算法進(jìn)行社區(qū)結(jié)構(gòu)劃分得到3個(gè)社區(qū)，選取人數(shù)最多的社區(qū)2作為對(duì)比數(shù)據(jù)集。社區(qū)2共4 500條數(shù)據(jù)，按興趣團(tuán)體共分為3大類。

4.2.1 精確度測(cè)試及分析

NPCluster算法與K-means算法的精確度測(cè)試結(jié)果如圖5所示。其中為確保實(shí)驗(yàn)不受人為因素影響，將K-means算法的k值設(shè)置為3，與已知類別數(shù)目相同。

圖5 算法精確度測(cè)試結(jié)果

從圖5可以看出，NPCluster算法聚類的正確率明顯高于K-means算法，并且NPCluster算法聚類得出的最后一個(gè)簇的成員可以看作一個(gè)孤立點(diǎn)。

由此可以得出，NPCluster算法相對(duì)于基本K-means算法而言有著明顯優(yōu)勢(shì)，既不用人為給定k值，又能找出數(shù)據(jù)集中的孤立點(diǎn)，且算法精確度更高。

4.2.2 效率測(cè)試及分析

NPCluster算法效率測(cè)試結(jié)果如圖6所示。

圖6 算法效率測(cè)試結(jié)果

由圖6可以得出，NPCluster算法效率要高于K-means算法。這是因?yàn)镵-means算法在迭代選取中心點(diǎn)時(shí)消耗的時(shí)間較多，而NPCluster算法只需要比較特征歐氏距離即可。考慮到NPCluster算法是基于社區(qū)結(jié)構(gòu)的，社區(qū)結(jié)構(gòu)的建立過(guò)程也有時(shí)間消耗，由于算法原理相似，CDS算法的時(shí)間消耗與NPCluster算法相當(dāng)。因此，最終對(duì)比結(jié)果表明，基于社區(qū)結(jié)構(gòu)的NPCluster算法的效率與K-means算法基本持平。

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

為了研究社會(huì)網(wǎng)絡(luò)中的社區(qū)劃分，并進(jìn)一步挖掘社區(qū)對(duì)象的潛在關(guān)系，重點(diǎn)研究了基于結(jié)構(gòu)與屬性的社區(qū)劃分方法。提出了基于結(jié)構(gòu)的社區(qū)劃分算法—CDS，以節(jié)點(diǎn)度和節(jié)點(diǎn)歐氏距離為社區(qū)結(jié)構(gòu)劃分準(zhǔn)則，對(duì)社會(huì)網(wǎng)絡(luò)進(jìn)行結(jié)構(gòu)劃分，形成社區(qū)結(jié)構(gòu)?；谏鲜錾鐓^(qū)結(jié)構(gòu)，提出了一種非人為設(shè)定k值的聚類算法—NPCluster。該算法以節(jié)點(diǎn)度作為聚類中心選取依據(jù)，以多維特征的平均歐氏距離作為聚類閾值，聚類成功的點(diǎn)在數(shù)據(jù)集中被刪除，經(jīng)過(guò)多次迭代，直至數(shù)據(jù)集中不存在點(diǎn)，聚類結(jié)束，所產(chǎn)生的簇即對(duì)應(yīng)于社區(qū)興趣團(tuán)體。由于NPCluster算法是基于社區(qū)結(jié)構(gòu)來(lái)劃分興趣團(tuán)體的，所以數(shù)據(jù)點(diǎn)之間基于特征的緊密性呈現(xiàn)會(huì)受到社區(qū)結(jié)構(gòu)的影響。實(shí)驗(yàn)結(jié)果表明，CDS算法能夠以較高的準(zhǔn)確度劃分社區(qū)結(jié)構(gòu)；NPCluster算法在聚類效果上優(yōu)于基本K-means算法，總體算法執(zhí)行效率與K-means算法相當(dāng)。

NPCluster算法具備無(wú)需人為干擾的特性，在社會(huì)網(wǎng)絡(luò)數(shù)據(jù)集上具備較好的適應(yīng)性，能夠發(fā)現(xiàn)結(jié)構(gòu)社區(qū)下的興趣團(tuán)體劃分，以及社會(huì)網(wǎng)絡(luò)軟硬結(jié)合的社區(qū)劃分。

[1] 宗乾進(jìn),袁勤儉,沈洪洲.國(guó)外社交網(wǎng)絡(luò)研究熱點(diǎn)與前沿[J].圖書情報(bào)知識(shí),2012(6):68-75.

[2] 王 亮.基于局部聚類的復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法研究[D].大連:大連理工大學(xué)，2011.

[3] 張 鑫,劉秉權(quán),王曉龍.復(fù)雜網(wǎng)絡(luò)中社區(qū)發(fā)現(xiàn)方法的研究[J].計(jì)算機(jī)工程與應(yīng)用,2015,51(24):1-7.

[4] Wu X,Zhu X,Wu G Q,et al.Data mining with big data[J].IEEE Transactions on Knowledge and Data Engineering,2014,26(1):97-107.

[5] 周 濤,陸惠玲.數(shù)據(jù)挖掘中聚類算法研究進(jìn)展[J].計(jì)算機(jī)工程與應(yīng)用,2012,48(12):100-111.

[6] Verma M,Srivastava M,Chack N,et al.A comparative study of various clustering algorithms in data mining[J].International Journal of Engineering Research and Applications,2012,2(3):1379-1384.

[7] Krishna K,Murty M N.Genetic K-means algorithm[J].IEEE Transactions on Systems,Man,and Cybernetics,Part B (Cybernetics),1999,29(3):433-439.

[8] Celebi M E,Kingravi H A,Vela P A.A comparative study of efficient initialization methods for the k-means clustering algorithm[J].Expert Systems with Applications,2013,40(1):200-210.

[9] 王玉雷,李玲娟.一種密度和劃分結(jié)合的聚類算法[J].計(jì)算機(jī)技術(shù)與發(fā)展,2015,25(9):53-56.

[10] 尹成祥,張宏軍,張 睿,等.一種改進(jìn)的K-Means算法[J].計(jì)算機(jī)技術(shù)與發(fā)展,2014,24(10):30-33.

[11] 劉莉莉,曹寶香.基于差分進(jìn)化算法的K-Means算法改進(jìn)[J].計(jì)算機(jī)技術(shù)與發(fā)展,2015,25(10):88-92.

[12] 趙京勝,孫夢(mèng)丹,張 麗.一種有效的K-means初始中心優(yōu)化算法[J].信息技術(shù)與信息化,2016(5):77-79.

[13] 朱 琪,于濟(jì)坤,王明德,等.社會(huì)網(wǎng)絡(luò)數(shù)據(jù)的可視化[J].吉林大學(xué)學(xué)報(bào):信息科學(xué)版,2015,33(5):584-587.

[14] 時(shí)京晶.三種經(jīng)典復(fù)雜網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)劃分算法研究[J].電腦與信息技術(shù),2011,19(4):42-43.

Community Division Method with Structure and Attribute

WAN Xin-gui,LI Ling-juan

(School of Computer,Nanjing University of Posts and Telecommunications,Nanjing 210003,China)

Most of the current methods of community division are based on structure,but the structure-based division cannot excavate the potential relationship of community objects,which is not to find the tendencies of community variations.Therefore a community-based partitioning algorithm (Community Division based on Structure,CDS) has been designed which applies degree and node-Euclidean distance to divide social network.Simultaneously,an algorithm by nonhuman (artificial) settingk-value—NPCluster algorithm (Non Presetting Cluster)—based on the community structure has been proposed,which is based on the community structures divided by CDS algorithm and has improved the unsatisfactory clustering outcomes caused by the inappropriateness of random selection of initial centers and that ofKvalue.Thus the maximum degree nodes are chosen as a cluster center in turn and the data are merged and clustered until the average feature-Euclidean distance is less than a given threshold.Theoretical analyses and experimental results show that the proposed CDS algorithm can effectively divide the community structures;compared withK-means algorithm,NPCluster algorithm has higher clustering quality and better clustering timeliness on the divided community;the community division method based on structure and attribute is practical and effective.

community division;degree;K-means;center;Euclidean distance

2016-08-04

2016-11-10 網(wǎng)絡(luò)出版時(shí)間：2017-06-05

國(guó)家自然科學(xué)基金資助項(xiàng)目(61302158，61571238)

萬(wàn)新貴(1991-)，女，碩士研究生，CCF會(huì)員(E200041361G)，研究方向?yàn)榱鲾?shù)據(jù)挖掘；李玲娟，教授，CCF會(huì)員(E200015276M)，研究方向?yàn)閿?shù)據(jù)挖掘、信息安全、分布式計(jì)算。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170605.1508.050.html

TP301

A

1673-629X(2017)08-0097-05

10.3969/j.issn.1673-629X.2017.08.020