![](https://csdnimg.cn/release/download_crawler_static/18270489/bg1.jpg)
收稿日期:20190312;修回日期:20190428 基金项目:国家重点研发计划资助项目(2016YFB1000600);中国科学院战略性先导科
技专项资肋项目(XDA06010307)
作者简介:刘东江(1988),男(通信作者),内蒙古人,博士,主要研究方向为数据挖掘、机器学习(ldongjiang@yeah.net);黎建辉(1973),男,湖北
人,研究员,博导,博士,主要研究方向为数据密集型计算、数据密集型存储.
基于 Spark的并行社区发现算法
刘东江
1,2
,黎建辉
1
(1.中国科学院 计算机网络信息中心,北京 100190;2.中国科学院大学,北京 100190)
摘 要:针对大规模图数据顶点聚类进行研究,提出了一种基于 Spark的并行社区发现算法,其在基于极值优
化的串行社区发现算法的基础上设计而成。此外还针对该串行算法在簇调整时因选择顶点数量过少而影响算
法运行效率的问题,提出了一种多个顶点选择方法。该方法会计算一个阈值并发现所有适应度值小于该阈值的
顶点,作为被选择的顶点;由于阈值是基于所有顶点的适应度值计算出来的,为了避免非常大的适应度值对阈值
造成的影响该方法会限制被选择顶点的数量,若被选择的顶点过多,算法只保留其中的一部分。同时,还提出了
一种顶点过滤方法,其可以有效减少图数据的数据量。实验表明,提出算法的运行时间明显短于比较的其他基
于 Spark的并行化社区发现算法,可以发现其运行速度相对较快。
关键词:社区发现;Spark;并行算法;图聚类;图数据
中图分类号:TP391 文献标志码:A 文章编号:10013695(2020)08003225506
doi:10.19734/j.issn.10013695.2019.03.0053
ParallelizedcommunitydetectionalgorithmbasedonSpark
LiuDongjiang
1,2
,LiJianhui
1
(1.ComputerNetworkInformationCenter,ChineseAcademyofSciences,Beijing100190,China;2.UniversityofChineseAcademyofSci
ences,Beijing100190,China)
Abstract:ThispaperfocusedongraphclusteringandproposedaparallelizedcommunitydetectionalgorithmbasedonSpark.
Thisalgorithmwasbasedonsequencecommunitydetectionalgorithmusingextremaloptimization.Thesequencealgorithmtried
tochooseonevertexeachtimewhenadjusttheclusters.Soitwouldtakelongtimetoadjusttheclusters.Forthisreason
,the
proposedalgorithmadoptedanewmultiverticesselectionmethod.Thismethodtriedtocalculateathresholdvalueandfound
alltheverticeswhosefitnessvaluewassmallerthanthethresholdvalue.Thentheproposedalgorithmalsoneededtochangethe
categoryofthesevertices
;besides,astheproposedmethodtokethefitnessvaluesofalltheverticesintoconsiderationwhen
triedtocalculatethethreshold,itneededtoselectlimitednumberofverticesinordertoavoidtheinfluenceofextremelylarge
fitnessvalues.Soiftheproposedmethodselectedgreatamountofvertices,itwouldonlykeeppartofthem.Atthesametime,
theproposedalgorithmalsoadoptedanewverticesfilteringmethod.Thismethodcouldreducethevolumeofgraphdataeffi
ciently.Theresultsshowthatproposedalgorithmtakesshortertimethanotherparallelizedalgorithmsforcomparison.Itmeans
thattheproposedalgorithmrunsrelativelyfaster.
Keywords:communitydetection;Spark;parallelizedalgorithm;graphclustering;graphdata
0 引言
社区发现算法是图数据挖掘的一个重要组成部分。该类
算法的主要任务是对图数据的顶点进行聚类,通过聚类所有顶
点会被划分到多个不同簇中并且要求簇内顶点之间的连接要
尽可能紧密,而簇间顶点连接要尽量稀疏。
Newman等人
[1]
提
出了一种度量社区发现算法聚类效果的方法,该方法已获得了
广泛应用,在其中需要为聚类结果计算一个 modularity值,该
值的计算方法为
modularity=
∑
i
(e
ii
-a
2
i
),a
i
=
∑
j
e
ij
(1)
其中:e
ii
表示簇 i内边的数量与图当中边总数的比值;e
ij
表示簇
i和 j之间边的数量与图当中边总数的比值;聚类结果的 modu
larity值越大说明算法的聚类效果越好。
社区发现算法被应用于许多领域当中,并且近些年出现了
大量相关的研究工作。GN算法
[1]
是其中一个非常具有代表
性的算法,该算法需要为每条边计算一个 betweenness值,之后
基于该值来对图进行划分。目前,已经有许多针对 GN算法进
行改进的算法被提出
[2~4]
;除此之外还有一类算法是通过优化
某个度量值来对图数据中顶点进行聚类的,这些度量值包括簇
系数
[5]
、循环系数
[6]
等。modularity值
[1]
是专门判定社区发现
算法聚类效果好坏的,有些算法是通过对
modularity值进行优
化来获取好的聚类结果的
[7~10]
。另外,谱的性质也经常被应
用在针对图数据的划分当中
[11~13]
,利用该方法可以有效增加
顶点之间的区分度,从而提高社区发现算法的聚类效果。与此
同时采用标签扩散的方法同样可以很好地对图数据的顶点进
行聚类
[14,15]
,还有一些社区发现算法是针对特殊图模型的,其
中包括不断变化的动态图模型
[16]
、稀疏网络
[17]
、具有方向性
和动态性的图
[18]
等。重叠社区发现也是一个非常重要的研究
领域,重叠社区发现算法
[19~21]
主要是寻找图数据中的一些特
殊顶点,这些顶点可能同时处于两个或多个不同的簇之中,将
所有这样的顶点聚合起来就构成了重叠社区。
目前,已经有许多串行化的社区发现算法被提出,虽然利
用这些算法对图数据进行聚类可以获得很好的结果,但是单机
的运行环境使得这些算法在对大规模图数据进行聚类时面临
第 37卷第 8期
2020年 8月
计 算 机 应 用 研 究
ApplicationResearchofComputers
Vol37No8
Aug.2020