公开(公告)号：CN103942308B

公开(公告)日：2017-04-05

申请号：CN201410158112.X

申请日：2014-04-18

Applicant: 中国科学院信息工程研究所

Inventor： 康颖 ,  王伟平 ,  孟丹 ,  木伟民

IPC: G06F17/30

Abstract: 本发明涉及一种大规模社交网络社区的检测方法及装置。方法包括：将输入的大规模社交网络建模成图G=(V,E)；通过并行排序算法将图G上的所有节点依节点度的大小关系作降序排列，并计算图G上所有节点的有效度之和DSum；以DSum/P为等分基准参考值，依负载均衡法将图G等分为P个子图；将P个子图通过MapReduce并行计算模型遍历寻找图G上的三角形，基于三角形拓扑结构对图G进行并行化多层粗化，获得最简粗化归约图G’；采用基于遗传学的社区发现算法，对最简粗化归约图G’做初始社区发现，生成社区发现结果；将社区发现结果逐层反粗化还原到图G并伴随作微调优处理，获得图G的社区结构。本发明能够精准而高效地实现大规模社交网络的社区发现和数据分析。

公开(公告)号：CN103942308A

公开(公告)日：2014-07-23

申请号：CN201410158112.X

申请日：2014-04-18

Applicant: 中国科学院信息工程研究所

Inventor： 康颖 ,  王伟平 ,  孟丹 ,  木伟民

IPC: G06F17/30

CPC classification number: G06F17/30964

Abstract: 本发明涉及一种大规模社交网络社区的检测方法及装置。方法包括：将输入的大规模社交网络建模成图G=(V,E)；通过并行排序算法将图G上的所有节点依节点度的大小关系作降序排列，并计算图G上所有节点的有效度之和DSum；以DSum/P为等分基准参考值，依负载均衡法将图G等分为P个子图；将P个子图通过MapReduce并行计算模型遍历寻找图G上的三角形，基于三角形拓扑结构对图G进行并行化多层粗化，获得最简粗化归约图G’；采用基于遗传学的社区发现算法，对最简粗化归约图G’做初始社区发现，生成社区发现结果；将社区发现结果逐层反粗化还原到图G并伴随作微调优处理，获得图G的社区结构。本发明能够精准而高效地实现大规模社交网络的社区发现和数据分析。