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

王 林，董小江

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

?

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

王 林，董小江

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

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

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

0 引言

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

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

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

1.1 節點相似度計算

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

(1)

(2)

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

(3)

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

1.2 AP聚類算法

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

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

(4)

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

a(i,k)←

(5)

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

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

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

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

(6)

(3)計算節點i對于節點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的點作為聚類中心點并進行下一次迭代，直到類簇中心不再發生變化或者已經完成了指定的迭代次數后停止計算，否則重復第(2)、(3)步。

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

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

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

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

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

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

(2)計算吸引度矩陣

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

圖3 Mapreduce模型上吸引度計算

(3)計算歸屬度矩陣

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

圖4 Mapreduce模型上歸屬度計算

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

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

2 實驗與分析

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

表1 實驗數據

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

表2 實驗結果對比

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

3 結論

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

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

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

[3] 王林，戴冠中.復雜網絡中的社區發現—理論與應用[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,等.復雜網絡聚類方法[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].計算機研究與發展,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-)，男，博士，教授，主要研究方向：復雜網絡、大數據理論與應用。

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