大规模社交网络社区的检测方法及装置

摘要

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

主权项

一种大规模社交网络社区的检测方法，其特征在于，包括：步骤一，将输入的大规模社交网络建模成图G＝(V,E)，其中，V为节点集合，E为边集合；图G上任一节点v表示大规模社交网络中的个人或组织，v∈V，度d(v)表示与节点v相邻的节点数目，集合N(v)表示与节点v相邻的节点集合，边e表示节点之间的特定属性关系，e∈E；步骤二，通过并行排序算法将图G上的所有节点依节点度的大小关系作降序排列，并计算图G上所有节点的有效度之和DSum，其中，节点v的有效度是指其相邻节点集合N(v)中度大于d(v)的所有节点数目；步骤三，以DSum/P为等分基准参考值，将图G上的所有节点按照节点度降序的轮转分配法则循环分配到MapReduce并行计算模型中P个Map任务上，即依负载均衡法将图G等分为P个子图，P为自然数；步骤四，将所述P个子图通过所述MapReduce并行计算模型遍历寻找图G上的三角形，然后基于三角形拓扑结构对图G进行并行化多层粗化，获得最简粗化归约图G’；将所述P个子图通过MapReduce并行计算模型，在每个子图部分以节点度升序的方式遍历寻找该子图上的三角形拓扑结构，每当遇到一个三角形，将该三角形内部三个顶点向其中度最大的节点收缩融合形成一个复合节点，连边融合，而垂悬点向内点融合，直至整个图G遍历完成形成第一粗化归约图G1，然后在第一粗化归约图G1的基础上继续执行步骤三和步骤四进行下一层粗化归约，如此循环迭代直至最终生成的粗化归约图规模小于或等于预设的规模阈值，则终止粗化；步骤五，采用基于遗传学的社区发现算法，对所述最简粗化归约图G’做初始社区发现，生成社区发现结果，其中，对所述最简粗化归约图G’做初始社区发现是指将图G’上的节点依链接关系聚合生成一个个的簇，使得簇内节点联系紧密，簇间节点联系稀疏；步骤六，将所述社区发现结果逐层反粗化还原到所述图G并伴随作微调优处理，从而获得图G的社区结构，也即所述输入大规模社交网络的社区结构。