社團挖掘的并行化AP聚類方法

王 林，董小江

(西安理工大學 自動化與信息工程學院，陜西 西安 710048)

?

社團挖掘的并行化AP聚類方法

王 林，董小江

(西安理工大學 自動化與信息工程學院，陜西 西安 710048)

采用AP聚類算法進行復雜網(wǎng)絡社團挖掘，提高了社團挖掘的精度，但在處理海量數(shù)據(jù)時算法速率明顯下降，其中一個重要原因是單臺計算機的計算性能無法滿足海量數(shù)據(jù)的計算需求。為了提高社團挖掘AP聚類在處理海量數(shù)據(jù)時的速率，設計出一種在Hadoop框架下進行的社團挖掘的并行化AP聚類方法；將傳統(tǒng)單機模式下的社團挖掘AP聚類算法在分布式平臺上分布進行并行化。實驗表明，社團挖掘的并行化AP聚類方法在社團挖掘精度不下降的情況下提高了海量數(shù)據(jù)的社團挖掘速率。

社團挖掘；AP聚類；并行化；MapReduce

0 引言

社團結構是復雜網(wǎng)絡最重要的特征之一，具有同社團節(jié)點相互連接緊密、異社團節(jié)點相互連接稀疏的特點[1]。檢測復雜網(wǎng)絡中的社團結構有助于了解復雜網(wǎng)絡的拓撲結構、理解復雜網(wǎng)絡的功能、發(fā)現(xiàn)復雜網(wǎng)絡中的隱藏規(guī)律以及開發(fā)利用復雜網(wǎng)絡[2]。目前，復雜網(wǎng)絡的社團挖掘取得了一定的研究成果，經(jīng)典的社團挖掘方法有：基于模塊度的方法[3]、標簽傳播算法[4]、聚類算法[5]。其中聚類算法由于簡單易用得到了廣泛的應用，它通過節(jié)點之間的相似度將社團檢測問題轉化為聚類問題[6]。仿射傳播(AP)聚類[7]算法通過引入吸引度和歸屬度在節(jié)點間傳遞信息來確定類簇中心節(jié)點，然后將所有節(jié)點依次劃分到其對應的簇中心節(jié)點，從而實現(xiàn)了無需預先設定社團的個數(shù)，只需要輸入相似度矩陣和真實的參數(shù)P值，就能得到準確的聚類結果。相比于k-means等其他聚類算法，AP聚類的錯誤率大幅降低，并且AP聚類對輸入相似度矩陣的對稱性和三角不等式?jīng)]有要求，從而使得AP聚類可廣泛適用于各種場合[8]。

文獻[9]中將AP聚類成功運用到社交網(wǎng)絡的社團檢測，在人工網(wǎng)絡和現(xiàn)實網(wǎng)絡中進行試驗均表明基于AP聚類的社團檢測算法在社團檢測的準確率和效率上均優(yōu)于傳統(tǒng)的社團檢測方法。文獻[10]中將AP聚類成功地運用在社交網(wǎng)絡和蛋白質作用網(wǎng)的社團檢測，應用表明，相比其他聚類和GN算法，AP聚類的速度最快。文獻[11]將AP聚類應用在模擬網(wǎng)絡上與標簽傳播算法和CNM算法相比較，社團挖掘的AP聚類算法能夠發(fā)現(xiàn)更高質量的社團結構。隨著數(shù)據(jù)量的日益劇增，由于單臺計算機的CPU和內存性能的限制使得現(xiàn)有的算法已經(jīng)無法應對海量數(shù)據(jù)。而算法的并行化是解決此問題的一種新的途徑，Hadoop是一種新的分布式計算框架，通過Hadoop可以將多臺普通的計算機組成一個強大的分布式計算系統(tǒng)，讓現(xiàn)有的算法并行地在Hadoop系統(tǒng)上運行可以解決單臺計算機的CPU和內存不足的問題；文獻[12]中，在大規(guī)模數(shù)據(jù)量的情況下在Hadoop平臺上并行實現(xiàn)了k-means聚類和AP聚類，將聚類算法并行化提高了聚類的運算速率。文獻[13]中將改進的AP聚類成功應用在Hadoop平臺上，相比于文獻[12]，文獻[13]在運用AP聚類之前對數(shù)據(jù)進行了稀疏化處理，進一步提高了運算速度和算法的準確率。本文在前人對復雜網(wǎng)絡社團挖掘算法研究的基礎上，將社團挖掘的AP聚類算法與Hadoop平臺相結合，提出了社團挖掘的并行化AP聚類方法。實驗表明該方法相比傳統(tǒng)AP聚類算法速度有明顯提高。

1 社團挖掘的并行化AP聚類方法

1.1 節(jié)點相似度計算

節(jié)點相似度在復雜網(wǎng)絡中是一個重要的節(jié)點屬性，關于節(jié)點相似度的研究已經(jīng)有了很多的測量方法。在復雜網(wǎng)絡中，兩個節(jié)點的鄰居節(jié)點越多，則認為這兩個節(jié)點的相似度越大，反之則越小。用Ni表示復雜網(wǎng)絡中節(jié)點i的相鄰節(jié)點，用Nj表示復雜網(wǎng)絡中節(jié)點j的相鄰節(jié)點，則節(jié)點i和節(jié)點j的相似度表示為：

(1)

(2)

相似度的最大值為1(當Ni=Nj時)。但是上述方法并沒有考慮兩個節(jié)點直接相連的情況，本文在Jaccard矩陣的基礎上改進了相似度計算方法，考慮到AP聚類需要負的相似度值，所以對Jaccard做了如下改進：

(3)

其中e(i,j)=0表示節(jié)點i和j之間直接相連，e(i,j)=1表示節(jié)點i和j之間沒有直接相連。

1.2 AP聚類算法

AP聚類算法是一種基于信息傳播的聚類算法，其目的是找到最優(yōu)的類代表點集合(一個類代表點對應為實際數(shù)據(jù)集中的一個數(shù)據(jù)點，exemplar)，使得所有數(shù)據(jù)點到最近的類代表點的相似度之和最大。AP聚類引入了兩個類型的信息吸引度矩陣r(i,k)和歸屬度矩陣a(i,k)，然后通過不斷更新歸屬度矩陣和吸引度矩陣來確定聚類中心。更新規(guī)則如下：

用歸屬度矩陣a(i,k)和相似度矩陣s(i,k)來更新吸引度矩陣r(i,k)：

(4)

用吸引度矩陣更新歸屬度矩陣：

a(i,k)←

(5)

s(i,k′)代表節(jié)點i和節(jié)點k′的相似度，相似度由公式(3)計算得出；當i和k′相同時，s(i,i)由輸入的偏向參數(shù)p(i)設置(p(i)<0)，p(i)越大，節(jié)點i成為聚類中心點的可能性越大。為了減少震蕩，在計算過程中引入阻尼系數(shù)λ；

整個AP聚類的算法流程如下：

(1)初始化，給歸屬度a(i,k)全部賦值為0，輸入相似矩陣s，設置所有p(i)(即s(i,i))為s(i,k′)值的中位數(shù)；

(2)計算節(jié)點k對于節(jié)點i的吸引度，按照如下公式：

(6)

(3)計算節(jié)點i對于節(jié)點k的歸屬度，計算公式如下：

at(i,k)=(1-λ)(min{0,r(k,k)+

(7)

(8)

(4)求a(i,k)+r(i,k)，a(k,k)+r(k,k)>0的點作為聚類中心點并進行下一次迭代，直到類簇中心不再發(fā)生變化或者已經(jīng)完成了指定的迭代次數(shù)后停止計算，否則重復第(2)、(3)步。

1.3 社團挖掘AP聚類的并行化

分析社團挖掘AP算法的實現(xiàn)流程并結合MapReduce的并行模式設計方法，由于社團挖掘AP算法計算過程中相似度計算、歸屬度計算、吸引度計算等具有前后相關的數(shù)據(jù)依賴關系，本文將AP計算過程中的每步分別采用MapReduce框架并行化實現(xiàn)，各步驟之間仍然串行執(zhí)行，社團挖掘AP聚類并行化的計算步驟如圖1所示。

圖1 社團挖掘AP聚類方法的執(zhí)行流程圖

(1)相似度計算在MapReduce上的實現(xiàn)

公式(3)給出了相似度計算方法，相似度的計算只與節(jié)點的鄰接節(jié)點矩陣有關。在map端輸入節(jié)點和節(jié)點鄰接矩陣的鍵值對，由Map函數(shù)進行組合輸出<(i,j),(N(i),N(j))>。然后由公式(3)在Hadoop集群上用Reduce函數(shù)計算每對節(jié)點的相似度，總共將m2對節(jié)點分配到n個集群中；m是數(shù)據(jù)節(jié)點的個數(shù)，n代表集群中計算節(jié)點的數(shù)目,如圖2所示。

圖2 MapReduce模型上的相似度計算

(2)計算吸引度矩陣

初始狀態(tài)時，吸引度矩陣和歸屬度矩陣都為零，由公式(6)在MapReduce下計算吸引度矩陣Ri；Map函數(shù)將初始的相似度Si和歸屬度ai組合成鍵值對，Reduce函數(shù)按照公式(6)計算吸引度矩陣，具體流程如圖3所示。

圖3 Mapreduce模型上吸引度計算

(3)計算歸屬度矩陣

由公式(7)、(8)可知計算歸屬度a(i,k)時需要知道其他節(jié)點相對于節(jié)點k的吸引度矩陣；Map函數(shù)將輸入的{r,r(i,k)}鍵值對按照k重新排列輸出新的鍵值對，然后Reduce函數(shù)按照公式(7)、(8)計算相應的歸屬度，具體流程如圖4所示。

圖4 Mapreduce模型上歸屬度計算

(4)計算聚類簇的中心節(jié)點

計算聚類簇中心節(jié)點時將r(k,k)+a(k,k)>0的點選為聚類中心點，在map階段分別把r(k,k)和a(k,k)的值按照節(jié)點順序組合起來，在reduce階段由a(k,k)+r(k,k)>0計算出聚類簇的中心節(jié)點。

2 實驗與分析

實驗平臺為Hadoop集群,基于Hadoop 1.20.2，集群系統(tǒng)由4臺PC組成，其中1 臺PC作Master節(jié)點，3臺PC作為Slave節(jié)點。操作系統(tǒng)采用Ubuntu 10.04；模擬生成了1組隨機網(wǎng)絡數(shù)據(jù)集。實驗數(shù)據(jù)如表1所示。規(guī)模數(shù)據(jù)集包括3個數(shù)據(jù)，用于傳統(tǒng)AP聚類算法在一臺PC 機上的運行效率與社團挖掘AP聚類的并行化方法在多臺PC機上的運行性能進行對比。

表1 實驗數(shù)據(jù)

在相同配置條件下，采用相同規(guī)模的數(shù)據(jù)集，分別對傳統(tǒng)社團挖掘AP聚類和社團挖掘AP聚類的并行化方法進行對比實驗，實驗結果如表2所示。

表2 實驗結果對比

隨著輸入數(shù)據(jù)規(guī)模的不斷增大，傳統(tǒng)AP聚類算法和本文提出的算法消耗的計算機內存資源逐漸增多，計算時間也逐漸增加。當節(jié)點個數(shù)增加到10 000個時，單臺PC因為內存不足無法完成計算任務；而本文提出的方法在僅由4臺PC組成的Hadoop集群上可以滿足10 000個節(jié)點的數(shù)據(jù)計算需求，并且相對于單臺PC的計算效率有了大幅的提高。

3 結論

本文對社團挖掘的AP聚類算法進行并行化，充分利用MapReduce的特性進行社團檢測，并且能夠對復雜網(wǎng)絡進行快速有效的分析處理，在集群規(guī)模適當?shù)那闆r下能夠減少社團挖掘所需時間。通過對比測試處理數(shù)據(jù)規(guī)模增長時系統(tǒng)的處理能力和對同一作業(yè)計算機硬件資源增加時系統(tǒng)的處理能力，證明了該方法提高了社團挖掘的速率和應對大規(guī)模數(shù)據(jù)的能力。

[1] FORTUNATO S. Community detection in graphs[J]. Physics Reports， 2010，486: 75-174.

[2] 汪小帆,李翔,陳關榮.復雜網(wǎng)絡理論及其應用[M].北京:清華大學出版社,2006.

[3] 王林，戴冠中.復雜網(wǎng)絡中的社區(qū)發(fā)現(xiàn)—理論與應用[J].科技導報,2005,23(8):62-66.

[4] Zhu Xiaojin,GHAHRAMANI Z.Learning from labeled and unlabeleddata with label propagation.CMU--CALD-02-107[R]．Pittsburghers：Carnegie Mellon University，2002.

[5] NEWMAN M. Modularity and community structure in networks[J]. Proceedings of National Academy of Sciences,2006,103(23):8577-8582.

[6] 楊博,劉大有,Liu Jiming,等.復雜網(wǎng)絡聚類方法[J].軟件學報,2009,20(1): 54-66.

[7] FREY B J, DUECK D. Clustering by passing messages between data[J]. Points Scinence,2007,315(5814):972-6.

[8] Guo Guojun.KWOK-PONG M.Subspace clustering using affinity propagation[J].Pattern Recognition,2015,48:1455-1464.

[9] Liu Zhiyuan, Li Peng, Zheng Yabin, et al.Community detection by affinity propagation[C]. International Joint Conference on Computational Sciences & Optimization, 2011: 182-186.

[10] Jia Caiyan, Jiang Yawen, Yu Jian, et al. Affinity propagation on identifying[C]. Communities in Social and Biological Networks.KSEM, 2010: 597-602.

[11] 孫貴賓,周勇. 基于結構相似度仿射傳播的社團檢測算法[J].計算機應用，2015，35(3):633-637.

[12] Wang Kaijun, Zhang Junying, Li Dan, et al. Adaptive affinity propagation clustering[J]. Acta Automatica Sinica, 2007, 33(12): 1242-1246.

[13] 魯偉明,杜晨陽,魏寶剛,等.基于MapReduce的分布式近鄰傳播聚類算法[J].計算機研究與發(fā)展,2012,49(8):1762-1772.

Detection community by parallelization AP clustering

Wang Lin, Dong Xiaojiang

(School of Automation and Information Engineering, Xi’an University of Technology, Xi’an 710048, China)

The accuracy of community detection can be improved by AP clustering algorithm. However, the rate of the algorithm decreases dramatically when used in dealing with massive data. One of the main reasons is that the computational performance of a single computer cannot meet the demand of massive data. To improve the rate of AP clustering method used in massive data processing, a parallel AP clustering method for community mining based on Hadoop framework was proposed in this paper, in which, the AP clustering algorithm that was used in traditional single machine for community mining was parallelized on a distributed platform. Experiment results indicated that the rate of community detection in massive data was improved with no decline of accuracy.

community detection; AP clustering; parallelization; MapReduce

TN929.12

A

10.19358/j.issn.1674- 7720.2017.12.005

王林，董小江.社團挖掘的并行化AP聚類方法[J].微型機與應用，2017,36(12)：16-18.

2016-12-29)

王林(1963-)，男，博士，教授，主要研究方向：復雜網(wǎng)絡、大數(shù)據(jù)理論與應用。

董小江(1990-)，通信作者，男，碩士，主要研究方向：復雜網(wǎng)絡、社團檢測，大數(shù)據(jù)。E-mail：dxj2007131@126.com。