[发明专利]基于重叠点识别的网络重叠社团检测方法

摘要

本发明公开了一种基于重叠点识别的网络重叠社团检测方法，其特征在于：第一步使用GN算法对网络进行社团划分，得到网络非重叠社团集合，并据此得出网络社团边界点集合，计算该集合中边界点的关联社团连接率，选取其中大于检测阈值的节点构建网络社团候选重叠点集合；第二步使用基于节点质量函数的重叠点判定规则识别重叠点，得到网络重叠社团集合；第三步计算第二步得到的重叠社团之间的社团重叠率，合并达到重叠阈值的社团。本发明在对网络进行重叠社团划分过程中综合考虑网络的全局特征和局部特征，增强了网络社团划分的合理性。

主权项

一种基于重叠点识别的网络重叠社团检测方法，其特征在于，包括如下步骤：第一步，网络社团候选重叠点集合构建：首先，对网络进行社团划分，得到网络的非重叠社团集合；其次，搜索连接两个社团之间的边，社团之间边的顶点即社团的边界点，并据此求解出每个社团的初始边界点集合，对网络中各社团的初始边界点集合求并集，得到网络社团的初始边界点集合；再次，根据节点到关联社团的连接数与该节点在网络中度的比值，计算社团初始边界点集合中每个节点到其关联社团的连接率，并将连接率达到检测阈值的边界点加入初始候选重叠点集合；第二步，社团重叠点识别：提出基于节点质量函数重叠点判定规则，判定候选重叠点集合中的节点与节点潜在隶属社团的隶属关系，识别出重叠点，并将重叠点加入到满足重叠点判定规则的隶属社团中；将新产生的边界点到其关联社团的连接率达到检测阈值的节点加入候选重叠点集合；递归执行第二步，直到候选重叠点集合不包含满足重叠点判定规则的节点为止，得到网络的重叠社团集合；第三步，网络重叠社团合并：对于第二步得到的网络重叠社团集合，计算每两个社团间的社团节点重叠率，将重叠率达到合并阈值的社团进行合并，从而得到最终的网络重叠社团划分结果。