基于Spark的并行增量动态社团发现算法
发布时间：2018-07-17 05:42
【摘要】：动态社团发现是研究网络演化的关键步骤。在数据量迅猛增长的情况下,社团发现的单机算法效率较低。该文提出了一种基于Spark的并行增量动态社团发现算法(parallel incremental dynamic community detection algorithm based on Spark,PIDCDS),为了在GraphX并行图计算平台上通过最大化持久力发现社团,该算法对节点的持久力计算公式进行了有效修正。PIDCDS计算每个时间片中增量节点的持久力指标,更新其社团归属,在保证一定的社团划分准确性的基础上减少计算量。通过与FacetNet动态社团发现算法做比较,该算法能够获得更好的稳定性,同时能发现更真实的社团划分。对比不同规模网络在PIDCDS上的运行时间,发现该时间随着网络节点和边数的增加缓慢增长,性能较高,并且增加执行器核数将在一定程度上加速算法的执行。
[Abstract]:Dynamic community discovery is a key step in the study of network evolution. In the case of rapid growth of data volume, the efficiency of single machine algorithm discovered by community is low. In this paper, a parallel incremental dynamic community discovery algorithm (parallel incremental dynamic community detection algorithm based on Sparkan PIDCDS based on Spark is proposed. The algorithm effectively modifies the calculation formula of the persistence of nodes. PIDCDS calculates the persistence index of the incremental nodes in each time slice, updates their community ownership, and reduces the amount of computation on the basis of ensuring the accuracy of community division. Compared with FacetNet dynamic community discovery algorithm, this algorithm can obtain better stability and find more real community partition. By comparing the running time of different scale networks on PIDCDS, it is found that the time increases slowly with the increase of network nodes and edges, and the performance of PIDCDS is higher, and the execution of the algorithm will be accelerated to a certain extent by increasing the number of executor kernels.
【作者单位】： 北京邮电大学智能通信软件与多媒体北京市重点实验室;北京邮电大学计算机学院;
【基金】：国家“九七三”重点基础研究发展计划(2013CB329606) 北京市共建项目专项资助
【分类号】：TP301.6
[Abstract]:Dynamic community discovery is a key step in the study of network evolution. In the case of rapid growth of data volume, the efficiency of single machine algorithm discovered by community is low. In this paper, a parallel incremental dynamic community discovery algorithm (parallel incremental dynamic community detection algorithm based on Sparkan PIDCDS based on Spark is proposed. The algorithm effectively modifies the calculation formula of the persistence of nodes. PIDCDS calculates the persistence index of the incremental nodes in each time slice, updates their community ownership, and reduces the amount of computation on the basis of ensuring the accuracy of community division. Compared with FacetNet dynamic community discovery algorithm, this algorithm can obtain better stability and find more real community partition. By comparing the running time of different scale networks on PIDCDS, it is found that the time increases slowly with the increase of network nodes and edges, and the performance of PIDCDS is higher, and the execution of the algorithm will be accelerated to a certain extent by increasing the number of executor kernels.
【作者单位】： 北京邮电大学智能通信软件与多媒体北京市重点实验室;北京邮电大学计算机学院;
【基金】：国家“九七三”重点基础研究发展计划(2013CB329606) 北京市共建项目专项资助
【分类号】：TP301.6
【相似文献】
相关期刊论文 前10条
1 任庆生,叶中行,曾进;进化算法的收敛速度[J];上海交通大学学报;1999年06期
2 唐浩;;蚁群算法的研究与展望[J];牡丹江教育学院学报;2009年06期
3 邓小波;曹聪聪;龙伦海;康耀红;;蚁群算法搜索熵研究[J];海南大学学报(自然科学版);2007年04期
4 张康;顾幸生;;全局组搜索优化算法及其应用研究[J];青岛科技大学学报(自然科学版);2012年05期
5 李东晓;蒋珉;柴干;;蚁群算法优化及其在高速公路紧急救援中的应用[J];计算机技术与发展;2010年11期
6 李德胜;张才仙;陈淑铭;;选择策略对进化算法性能的影响[J];科技资讯;2007年11期
7 韩明红;邓家y，
本文编号：2129263
本文链接：https://www.wllwen.com/kejilunwen/ruanjiangongchenglunwen/2129263.html
