计算机工程与应用 ›› 2017, Vol. 53 ›› Issue (4): 106-112.DOI: 10.3778/j.issn.1002-8331.1507-0239

• 大数据与云计算 • 上一篇    下一篇

基于MapReduce的无线城市社团发现算法研究

王永贵1,张  燕1,杨东东2   

  1. 1.辽宁工程技术大学 软件学院,辽宁 葫芦岛 125105
    2.中国科学技术大学 软件学院,合肥 230001
  • 出版日期:2017-02-15 发布日期:2017-05-11

Research on algorithm of community discovery of wireless city based on MapReduce

WANG Yonggui1, ZHANG Yan1, YANG Dongdong2   

  1. 1.College of Software, Liaoning Technical University, Huludao, Liaoning 125105, China
    2.College of Software, University of Science and Technology of China, Hefei 230001, China
  • Online:2017-02-15 Published:2017-05-11

摘要: 对于无线城市数据中社团发现问题,针对已有的团搜索(CS)算法运行过程生成大量重复团、生成结果冗余、算法时间复杂度较高等问题,从优化边存储、预先进行边处理、搜索建团入手,用特殊的二叉树结构存储、权重[K]选择排序、深度优先遍历构建T-CS算法。针对海量数据溢出问题,结合MapReduce模型,提出了MP-T-CS算法。实验证明,MP-T-CS算法不仅可以解决运行过程大量重复团问题,时间代价大大降低,对海量数据的处理能力大大提升,生成团的代表性大大提高。

关键词: 社团发现, 团搜索, 二叉树, 深度遍历, [K]选择排序, MapReduce

Abstract:  For the problem of the community discovery of wireless city, during operation existing algorithm of Clique Search(CS) generates a large number of repeat groups, a redundant result and high calculation complexity and other issues. From the side storage optimization, edge treatment in advance, search generating groups, using a special binary tree storage, weights [K] selection sort, depth-first traversal algorithm to build T-CS algorithm. For massive data overflow problems, combined with MapReduce model, proposing a MP-T-CS algorithm. Experiments show that, MP-T-CS algorithm can not only solve the problem during the operation generating a large number of repeat groups, time is also greatly reduced, the cost of massive data processing capability has been greatly improved and the representativenessof groups result is greatly improved.

Key words: community discovey, group search, Binary Tree, depth traversal, [K] selection sort, MapReduce