社团挖掘的并行化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。