基于BSP的社团挖掘研究

摘要

通联关系社团挖掘是犯罪组织或恐怖组织的发现手段,在计算上通常采用图算法来实现.但是随着通联关系数量的增多,图的规模越来越大,需要分析的节点超过了数百万级,边的数量达到数千万级别,依靠图算法和单服务器已经无法实现.本文简要介绍了一种基于消息传递的整体同步并行计算模型(BSP).在BSP模型中运算由一系列超步(SuperSteps)组成,每个超步又由并行计算、通信和同步三个部分组成.利用BSP计算模型,我们设计了一种对节点进行本地运算,处理器之间传递状态消息的迭代算法.实验数据表明该算法有效,且运算效率大大提高.