基于社区森林模型的分布式法重叠社区发现算法
DOI:
作者:
作者单位:

1.河北科技大学;2.陆军工程大学

作者简介:

通讯作者:

中图分类号:

基金项目:

国家文化和旅游科技创新工程项目(2020年度);河北省省级科技计划资助项目(20310802D,21310101D)


Author:
Affiliation:

1.Hebei University of science and technology;2.Army Engineering University

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    重叠社区发现是复杂网络挖掘领域中的重要基础工作,可以应用于社交网络、通讯网络、蛋白质相互作用网络、代谢路径网络、交通网络等多种网络的数据分析,从而服务于智慧交通、传染病防治、舆情分析、新药研制和人力资源管理等领域。传统的单机运算架构已经难于响应各类大规模复杂网络的分析和计算要求;人工智能领域的研究者提出将社区发现应用到网络表示学习领域,以丰富网络中节点和边的特征,但传统的重叠社区发现算法在设计时未能考虑来自网络表示学习任务的相关要求,只重点关注节点的社区划分,缺乏对社区的内部结构和外部边界的考虑,例如,没有涉及节点在社区内部的权重和属于多个社区的归属度排序等,因此不能提供网络中节点和社区更丰富的特征信息,导致对网络表示学习任务支持不足。针对传统的单机重叠社区发现算法已经不适于大规模复杂网络挖掘,以及不能支持网络表示学习任务的相关要求这两个问题,本文提出一种基于社区森林模型的分布式重叠社区发现算法(简称DCFM算法,Distributed Community Forest Model)。首先将网络数据集存储到分布式文件系统,继而将数据分块,使用分布式计算框架在每个数据分块上执行CFM算法;然后执行社区合并;最后汇总社区划分结果。使用真实的DBLP数据集将算法运行于Spark集群上,采用F均值和运行时间对算法进行评估。通过F均值实验得出结论:虽然DCFM算法的F均值稍逊于CFM算法,但其除了继承CFM算法的时间复杂度O(n+m)外,其运算时间随着节点的增加而接近线性下降,因此该算法在牺牲小部分F均值的同时,具备了大规模网络数据处理能力,这种分布式处理能力是当前工业界迫切需要的。通过运行时间实验得出结论:算法通过将大规模网络进行分块,然后分布式运行CFM算法,最后再根据重合率进行合并,充分利用了分布式集群的算力。综上所述,DCFM算法在大数据平台上分布式计算骨干度,进行社区划分、合并的策略是一种可行的大规模复杂网络挖掘方案,提高了社区发现的效率。

    Abstract:

    参考文献
    相似文献
    引证文献
引用本文
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2021-11-09
  • 最后修改日期:2021-12-17
  • 录用日期:2021-12-28
  • 在线发布日期:
  • 出版日期:
文章二维码