专利详情

专利名称	大规模社交网络社区的检测方法及装置
申请号	CN201410158112.X	专利类型	发明专利
公开（公告）号	CN103942308A	公开（授权）日	2014.07.23
申请（专利权）人	中国科学院信息工程研究所	发明（设计）人	康颖;王伟平;孟丹;木伟民
主分类号	G06F17/30(2006.01)I	IPC主分类号	G06F17/30(2006.01)I
专利有效期	大规模社交网络社区的检测方法及装置至大规模社交网络社区的检测方法及装置	法律状态	实质审查的生效
说明书摘要	本发明涉及一种大规模社交网络社区的检测方法及装置。方法包括：将输入的大规模社交网络建模成图G=(V,E)；通过并行排序算法将图G上的所有节点依节点度的大小关系作降序排列，并计算图G上所有节点的有效度之和DSum；以DSum/P为等分基准参考值，依负载均衡法将图G等分为P个子图；将P个子图通过MapReduce并行计算模型遍历寻找图G上的三角形，基于三角形拓扑结构对图G进行并行化多层粗化，获得最简粗化归约图G’；采用基于遗传学的社区发现算法，对最简粗化归约图G’做初始社区发现，生成社区发现结果；将社区发现结果逐层反粗化还原到图G并伴随作微调优处理，获得图G的社区结构。本发明能够精准而高效地实现大规模社交网络的社区发现和数据分析。