一种基于局部拓展的并行重叠社区发现算法

摘要：

处理海量级数据的有效途径之一是将算法分解为一系列互不依赖的任务,然后利用开源工具并行地执行算法.而在重叠社区发现算法中,基于局部拓展的方法在拓展阶段往往仅需要局部社区及其相应的邻居结点的信息,因而具备可并行执行的可能性.提出了一种可并行化执行的局部拓展算法,并借助开源工具Spark将其实现.算法分为4个阶段.首先,挑选出一组不相关的中心结点并使用其对应的局部网络作为种子;其次,通过删除本身连接不是很紧密的局部网络来过滤选出的种子;然后,采用一种批量式的拓展策略来拓展种子,即一次向局部社区中添加一批邻居结点或从社区中删除一批结点;最后,融合相似的社区.在人工生成的网络以及真实世界中的网络上的实验结果显示,所提算法既准确又高效.

关键词：复杂网络、重叠社区发现、局部拓展、并行化算法、Spark

所属期刊栏目：43

分类号：TP181(自动化基础理论)

资助基金：国家自然科学基金项目61271374

在线出版日期：2016-10-17（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：61-65