基于結構與屬性的社區劃分方法

萬新貴,李玲娟

(南京郵電大學 計算機學院,江蘇 南京 210003)

基于結構與屬性的社區劃分方法

萬新貴,李玲娟

(南京郵電大學 計算機學院,江蘇 南京 210003)

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

社區劃分；度；K-means；中心點；歐氏距離

0 引 言

在社會網絡研究[1-3]中關心的兩個方面是聯系和結構。目前基于結構角度的社區劃分研究比較充分，但是單純基于結構的劃分(稱為硬劃分)對社區內對象的潛在關系(比如興趣的異同等)表現不夠。而這種潛在關系的發現(稱為軟劃分)對預測社會網絡社區的變化趨勢有著重要的參考價值。

數據挖掘(Data Mining)[4]一般是指從大量的數據中通過算法搜索隱藏于其中信息的過程。……