本发明公开了一种基于重叠点识别的网络重叠社团检测方法，其特征在于：第一步使用GN算法对网络进行社团划分，得到网络非重叠社团集合，并据此得出网络社团边界点集合，计算该集合中边界点的关联社团连接率，选取其中大于检测阈值的节点构建网络社团候选重叠点集合；第二步使用基于节点质量函数的重叠点判定规则识别重叠点，得到网络重叠社团集合；第三步计算第二步得到的重叠社团之间的社团重叠率，合并达到重叠阈值的社团。本发明在对网络进行重叠社团划分过程中综合考虑网络的全局特征和局部特征，增强了网络社团划分的合理性。
1.一种基于重叠点识别的网络重叠社团检测方法，其特征在于，包括如下步骤：第一步，网络社团候选重叠点集合构建：首先，对网络进行社团划分，得到网络的非重叠社团集合；其次，搜索连接两个社团之间的边，社团之间边的顶点即社团的边界点，并据此求解出每个社团的初始边界点集合，对网络中各社团的初始边界点集合求并集，得到网络社团的初始边界点集合；再次，根据节点到关联社团的连接数与该节点在网络中度的比值，计算社团初始边界点集合中每个节点到其关联社团的连接率，并将连接率达到检测阈值的边界点加入初始候选重叠点集合；
该第一步中，对网络进行社团划分时，设网络为G(V,E)，V表示节点集合，E表示边的集合；使用GN算法对G(V,E)进行社团划分，得到网络初始的非重叠社团集合P＝{C1,C2,...,Ci,...,Ck}，其中， 1≤i,j≤k且i≠j， k表示社团个数，Ci表示G(V,E)的第i个社团；计算P中每个社团的密度δ(Ci)，得到社团密度记录集合 δ(Ci)计算如下：|Ci|表示社团中节点个数， 表示G(V,E)中以Ci中节点为节点集合的子图的边数，所述社团Ci的边界点集合为：
对P中每个社团的边界点集合求并集，得到网络的社团初始边界点集合B：其中t表示边界点个数，border(Ci)为社团Ci的边界点集合，bj表示第j个边界点；
对社团初始边界点集合B进行筛选，计算集合B中边界点bj到其关联社团集合Rj中每个关联社团 的社团连接率rjl；其中，边界点bj的关联社团集合Rj为：边界点bj到关联社团 的社团连接率rjl计算如下：
表示bj到社团 的连接数，deg(bj)表示bj在网络G(V,E)中的度；若rjl大于等于检测阈值φ，则将 标记为节点bj的潜在隶属社团，记为 并将该节点加入到候选重叠点集合CONS中；
第二步，社团重叠点识别：提出基于节点质量函数重叠点判定规则，判定候选重叠点集合中的节点与节点潜在隶属社团的隶属关系，识别出重叠点，并将重叠点加入到满足重叠点判定规则的隶属社团中；将新产生的边界点到其关联社团的连接率达到检测阈值的节点加入候选重叠点集合；递归执行第二步，直到候选重叠点集合不包含满足重叠点判定规则的节点为止，得到网络的重叠社团集合；
(1)对第一步得到的CONS中每个节点vcand，计算加入该节点后其关联社团集合 中的潜在隶属社团 的密度 节点关于 的质量 节点网络质量MassG(vcand)及 的平均质量
其中，加入vcand后潜在隶属社团 的密度 计算如下：
表示vcand到社团 的连接数；节点vcand关于其潜在隶属社团的质量函数 计算如下：
节点vcand关于整个网络的质量函数MassG(vcand)计算如下：MassG(vcand)＝deg(vcand)*δ(G) (8)deg(vcand)表示节点vcand在网络中的度，δ(G)为网络G(V,E)的密度函数，计算如下：|V|表示网络节点个数，|E|表示网络中边数；同理，社团 的节点平均质量计算如下：表示社团 中节点个数；
(2)若在CONS中存在满足重叠点判定规则的节点，选取其中 与MassG(vcand)之比最大的节点加入到 中，执行步骤(3)；否则执行步骤(5)；其中，基于节点质量函数的重叠点判定规则如下：若在CONS中节点vcand满足以下条件之一：
1)节点vcand关于 的质量 大于其关于整个网络的质量MassG(vcand)，
2)节点vcand关于 的质量 大于 内节点的平均质量
同时在 加入该节点后， 的社团密度 大于网络的密度
δ(G)，则vcand为重叠点，并且认为其隶属于社团
(3)将节点vcand加入到社团 中，调整CONS中节点vcand与 的隶属关系，将在节点vcand的关联社团集合 中标记为隶属社团，同时更新D中社团 的密度，计算新产生的边界点中到其关联社团连接率，将连接率达到检测阈值φ的节点加入到CONS中，并将该关联社团标记为节点潜在隶属社团，执行步骤(4)；
(4)计算社团 中的已有重叠点voverlap关于社团 的质量及其网络质量MassG(voverlap)；若存在不符合重叠点判定规则的节点，则选取其中与MassG(voverlap)之比最小的节点从 中删除，调整CONS中该节点与的隶属关系，将 在该节点的关联社团集合中标记为潜在隶属社团，同时更新D中社团 的密度，执行步骤(4)；否则执行步骤(1)；
(5)CONS中已不存在满足重叠点判定规则的节点，重叠点检测过程结束，得到重叠社团集合C＝{C′1,C′2,...,C′i,...,C′k}，其中，其中k表示社团个数，C′i表示G(V,E)的第i个社团；
第三步，网络重叠社团合并：对于第二步得到的网络重叠社团集合，计算每两个社团间的社团节点重叠率，将重叠率达到合并阈值的社团进行合并，从而得到最终的网络重叠社团划分结果。
2.如权利要求1所述的基于重叠点识别的网络重叠社团检测方法，其特征在于，所述重叠社团合并包括：(1)任意两个重叠社团C′i和C′j的重叠率 计算如下：|C′i|表示C′i节点的个数，|C′i∩C′j|表示C′i和C′j重叠点个数；
(2)计算重叠社团集合C中任意两个社团之间的重叠率，合并重叠率达到合并阈值 的社团，并从C中删除被合并的社团；最终得到合并后的重叠社团集合Cmerged＝{C″1,C″2,...,C″i,...,C″s}，其中s表示合并后的社团个数，C″i表示第i个社团。
基于重叠点识别的网络重叠社团检测方法
技术领域
[0001] 本发明涉及在复杂网络领域对网络进行重叠社团划分的方法，具体涉及一种采用重叠点识别算法进而对网络进行重叠社团划分。
背景技术
[0002] 真实世界中事物间的关系可以表示为网络，如人类关系网络、流行疾病传播网、生物网络等。这些网络中节点可以自然地聚集成一些节点簇，同一个簇的节点之间体现出了相似性，这种相似性在人类关系网络可能表示社团内个体具有共同的兴趣，在生物网络则可能表示社团内生物属于相同物种，网络的这种拓扑结构称为社团结构。社团结构作为网络的重要拓扑特性之一，在最近几年得到了学者们的广泛研究。已有对社团结构的研究大多关注于将网络划分为互不相交的社团集合；然而，现实的网络中的一些节点通常可以属于多个社团，例如人类关系网中一个人可能属于多个兴趣团体，因此社团之间是存在重叠现象的。针对网络重叠社团的发现方法，申请人通过查新，检索到1篇与本发明密切相关的发明专利：
[0003] 一种复杂网络社团的发现方法，专利申请号：CN201010613184.0；该专利提出一种复杂网络社团的发现方法，该方法包括：步骤一：建立所需分析网络的邻接矩阵；步骤二：确定初始划分点的值；步骤三：计算网络中各节点的度；步骤四：选取节点的度数最高的K个节点作为初始划分点；步骤五：选取具体需要的划分点；步骤六：根据步骤五得到的最后的划分点，由计算机给出最后的社团发现结果。
[0004] 上述网络社团发现方法的专利技术方案中，网络中的节点依据是否与所述的划分点相连被划分成不同的社团，因此该方法只考虑了网络的局部特征，忽略了网络全局特征对网络社团拓扑特性的影响；其次，该方法没有考虑社团之间的重叠现象。
发明内容
[0005] 本发明的目的在于提出一种基于重叠点识别的网络重叠社团划分方法，该方法综合考虑了网络的局部和全局特征，并将社团之间重叠率达到合并阈值的社团进行合并，得到网络的重叠社团结构，进而揭示网络结构和功能之间的联系，例如在研究人类关系网络时，认为同一社团内的人具有相同的兴趣，处于社团之间重叠部分的人属于多个兴趣团体。
[0006] 为达到以上目的，本发明是采取如下技术方案予以实现的：
[0007] 一种基于重叠点识别的网络重叠社团检测方法，其特征在于，包括如下步骤：
[0008] （1）网络社团候选重叠点集合构建：首先，使用GN算法对网络进行社团划分，得到网络的非重叠社团集合，其次，搜索连接两个社团之间的边，社团之间边的顶点即社团的边界点，并据此求解出每个社团的初始边界点集合，对网络中各社团的初始边界点集合求并集，得到网络的社团初始边界点集合；再次，根据节点到关联社团的连接数与该节点在网络中度的比值；计算社团初始边界点集合中每个节点到其关联社团的连接率，并将连接率达到检测阈值的边界点加入初始候选重叠点集合；
[0009] （2）社团重叠点识别：提出基于节点质量函数重叠点判定规则，判定候选重叠点集合中的节点与节点潜在隶属社团（即边界点的关联社团中，社团连接率达到检测阈值的社团）的隶属关系，识别出重叠点，并将重叠点加入到满足重叠点判定规则的隶属社团中；将新产生的边界点到其关联社团的连接率达到检测阈值的节点加入候选重叠点集合；递归执行步骤（2），直到候选重叠点集合不包含满足重叠点判定规则的节点为止，得到网络的重叠社团集合
[0010] （3）网络重叠社团合并：对于步骤（2）得到的网络社团集合，计算每两个社团间的社团节点重叠率，将重叠率达到合并阈值的社团进行合并，从而得到最终的网络重叠社团划分结果。
[0011] 上述方法中，所述网络社团候选重叠点集合构建包括：
[0012] （1）设网络为G(V,E)，V表示节点集合，E表示边的集合；使用GN算法对G(V,E)进行社团划分，得到网络初始的非重叠社团集合P＝{C1,C2,...,Ci,...,Ck}，其中，1≤i,j≤k且i≠j， k表示社团个数，Ci表示G(V,E)的第i个
社团；计算P中每个社团的密度δ(Ci)，得到社团密度记录集合
δ(Ci)计算如下：
[0013]
[0014] |Ci|表示社团中节点个数， 表示G(V,E)中以Ci中节点为节点集合的子图的边数，E
[0015] （2）社团之间的边的顶点是社团的边界点，社团Ci的边界点集合为：
[0016]
[0017] 对P中每个社团的边界点集合求并集，得到网络的社团初始边界点集合，计算如下：
[0018]
[0019] t表示边界点个数，border(Ci)为社团Ci的边界点集合，bj表示第j个边界点；
[0020] （3）对社团初始边界点集合B进行筛选，计算集合B中边界点bj到其关联社团集合Rj中每个关联社团 的社团连接率rjl；其中，边界点bj的关联社团集合Rj为：
[0021]
[0022] 边界点bj到关联社团 的社团连接率rjl计算如下：
[0023]
[0024] 表示bj到社团 的连接数，deg(bj)表示bj在网络G(V,E)中的度；若rjl大于等于检测阈值φ（缺省值为0.25），则将 标记为节点bj的潜在隶属社团，记为 并将该节点加入到候选重叠点集合（Candidate Overlapping Node Set，CONS）中。
[0025] 所述社团重叠点识别包括：
[0026] （1）对所述网络社团候选重叠点集合构建过程中得到的CONS中的每个节点vcand，计算加入该节点后其关联社团集合 中的潜在隶属社团 的密度节点关于 的质量 节点网络质量MassG(vcand)及 的平均质量
[0027] 其中，加入vcand后潜在隶属社团 的密度 的计算如下：
[0028]
[0029] 表示vcand到社团 的连接数；节点vcand关于其潜在隶属社团的质量函数 的计算如下：
[0030]
[0031] 节点vcand关于整个网络的质量函数MassG(vcand)计算如下：
[0032] MassG(vcand)＝deg(vcand)*δ(G) (8)
[0033] deg(vcand)表示节点vcand在网络中的度，δ(G)为网络G(V,E)的密度函数，计算如下：
[0034]
[0035] |V|表示网络节点个数，|E|表示网络中边数；同理，社团 的节点平均质量的计算如下：
[0036]
[0037] 表示社团 中节点个数；
[0038] （2）若CONS中存在满足重叠点判定规则的节点，选取其中 与MassG(vcand)之比最大的节点加入到 中，执行步骤（3）；否则执行步骤（5）；其中，基于节点质量函数的重叠点判定规则如下：若CONS中节点vcand满足以下条件之一：
[0039] 1）节点vcand关于 的质量 大于其关于整个网络的质量MassG(vcand)，
[0040] 2）节点vcand关于 的质量 大于 内节点的平均质量
[0041] 同时在 加入该节点后， 的社团密度 大于网络的密度δ(G)，则vcand为重叠点，并且认为其隶属于社团
[0042] （3）将节点vcand加入到社团 中，调整CONS中节点vcand与 的隶属关系，将 在节点vcand的关联社团集合 中标记为隶属社团，同时更新D中社团的密度，计算新产生的边界点中到其关联社团连接率，将连接率达到检测阈值φ的节点加入到CONS中，并将该关联社团标记为节点潜在隶属社团，执行步骤（4）；
[0043] （4）计算社团 中的已有重叠点voverlap关于社团 的质量及其网络质量MassG(voverlap)；若存在不符合重叠点判定规则的节点，则选取其中 与MassG(voverlap)之比最小的节点从 中删除，调整CONS中该
节点与 的隶属关系，将 在该节点的关联社团集合中标记为潜在隶属社团，同时更新D中社团 的密度，执行步骤（4）；否则执行步骤（1）；
[0044] （5）CONS中已不存在满足重叠点判定规则的节点，重叠点检测过程结束，得到重叠社团集合C＝{C'1,C'2,...,C'i,...,C'k}，其中，其中k表示社团个数，C'i表示G(V,E)的第i个社团。
[0045] 所述重叠社团合并包括：
[0046] （1）任意两个重叠社团C'i和C'j的重叠率 计算如下：
[0047]
[0048] |C'i|表示C'i节点的个数，|C'i∩C'j|表示C'i和C'j重叠点个数；
[0049] （2）计算重叠社团集合C中任意两个社团之间的重叠率，合并重叠率达到合并阈值 （缺省值为0.8）的社团，并从C中删除被合并的社团；最终得到合并后的重叠社团集合Cmerged＝{C″1,C″2,...,C″i,...,C″s}，其中s表示合并后的社团个数，C″i表示第i个社团。
[0050] 与现有技术相比，本发明的优点是：在对网络进行重叠社团划分过程中综合考虑网络的全局特征和局部特征，增强了网络社团划分的合理性；其中，全局特征体现在GN算法的模块度评价函数依赖网络的全局属性，以及重叠点判定规则中考虑了节点网络质量，局部特征体现在社团连接率以及节点关于关联社团的质量函数的计算中。
附图说明
[0051] 图1是本发明网络社团候选重叠点集合构建流程图。
[0052] 图2是图1所构建重叠点集合的一个具体网络社团边界点的实例图。
[0053] 图3是本发明社团重叠点识别算法流程图。
[0054] 图4是本发明重叠社团合并流程图。
具体实施方式
[0055] 以下结合附图及实施例对本发明作进一步的详细说明。
[0056] 基于重叠点识别的网络重叠社团划分方法，如图1所示，网络社团候选重叠点集合构建过程的具体流程如下：
[0057] （1）设网络为G(V,E)，V表示节点集合，E表示边的集合；使用GN算法（由Girvan和Newman提出的一种分裂式社团发现算法，执行过程中不断地计算网络中边的边介数；每次从网络中删除边介数最大的边，直到社团模块度不再增大）对G(V,E)进行社团划分，得到网络初始的非重叠社团集合P＝{C1,C2,...,Ci,...,Ck}，其中， 1≤i,j≤k且i≠j， k表示社团个数，Ci表示G(V,E)的第i个社团；计算P中每个社团的密度δ(Ci)，得到社团密度记录集合 δ(Ci)计算如下：
[0058]
[0059] |Ci|表示社团中节点个数， 表示G(V,E)中以Ci中节点为节点集合的子图的边数，
[0060] （2）社团之间的边的顶点是社团的边界点，社团Ci的边界点集合为：
[0061]
[0062] 如图2所示，eij为社团Ci与Cj之间的边，bi1为社团Ci的边界点，bj1、bj2及bj3为社团Cj的边界点；因此，通过在网络中搜索出社团之间的边，可以求解出P中各社团的边界点集合，然后对每个社团的边界点集合求并集，得到网络的社团初始边界点集合；计算如下：
[0063]
[0064] t表示边界点个数，border(Ci)为社团Ci的边界点集合，bj表示第j个边界点；
[0065] （3）遍历集合B，计算当前边界点bj到其关联社团（即所属社团除外，与边界点有连接的社团）集合Rj中每个关联社团 的社团连接率rjl（即节点到关联社团的连接数与该节点在网络中度的比值）；其中，边界点bj的关联社团集合Rj为：
[0066]
[0067] 边界点bj到关联社团 的社团连接率rjl计算如下：
[0068]
[0069] 表示bj到社团 的连接数，deg(bj)表示bj在网络G(V,E)中的度；若rjl大于等于0.25，则将 标记为节点bj的潜在隶属社团，记为 并将该节点加入到候选重叠点集合（Candidate Overlapping Node Set，CONS）中。
[0070] 如图3所示，社团重叠点识别的具体流程如下：
[0071] （1）对所述网络社团候选重叠点集合构建过程中得到的CONS中的每个节点vcand，计算加入该节点后其关联社团集合 中的潜在隶属社团 的密度节点关于 的质量 节点网络质量MassG(vcand)及 的平均质量
[0072] 其中，加入vcand后潜在隶属社团 的密度 的计算如下：
[0073]
[0074] 表示vcand到社团 的连接数；节点vcand关于其潜在隶属社团的质量函数 的计算如下：
[0075]
[0076] 节点vcand关于整个网络的质量函数MassG(vcand)计算如下：
[0077] MassG(vcand)＝deg(vcand)*δ(G) (8)
[0078] deg(vcand)表示节点vcand在网络中的度，δ(G)为网络G(V,E)的密度函数，计算如下：
[0079]
[0080] |V|表示网络节点个数，|E|表示网络中边数；同理，社团 的节点平均质量的计算如下：
[0081]
[0082] 表示社团 中节点个数；
[0083] （2）若CONS中存在满足重叠点判定规则的节点，选取其中 与MassG(vcand)之比最大的节点加入到 中，执行步骤（3）；否则执行步骤（5）；其中，基于节点质量函数的重叠点判定规则如下：若CONS中节点vcand满足以下条件之一：
[0084] 1）节点vcand关于 的质量 大于其关于整个网络的质量MassG(vcand)，
[0085] 2）节点vcand关于 的质量 大于 内节点的平均质量
[0086] 同时在 加入该节点后， 的社团密度 大于网络的密度δ(G)，则vcand为重叠点，并且认为其隶属于社团
[0087] （3）将节点vcand加入到社团 中，调整CONS中节点vcand与 的隶属关系，将 在节点vcand的关联社团集合 中标记为隶属社团，同时更新D中社团的密度，计算新产生的边界点中到其关联社团连接率，将连接率大于等于0.25的节点加入到CONS中，并将该关联社团标记为节点潜在隶属社团，执行步骤（4）；
[0088] （4）计算社团 中的已有重叠点voverlap关于社团 的质量及其网络质量MassG(voverlap)；若存在不符合重叠点判定规则的节点，则选取其中 与MassG(voverlap)之比最小的节点从 中删除，调整CONS中该
节点与 的隶属关系，将 在该节点的关联社团集合中标记为潜在隶属社团，同时更新D中社团 的密度，执行步骤（4）；否则执行步骤（1）；
[0089] （5）CONS中已不存在满足重叠点判定规则的节点，重叠点检测过程结束，得到重叠社团集合C＝{C'1,C'2,...,C'i,...,C'k}，其中，其中k表示社团个数，C'i表示G(V,E)的第i个社团。
[0090] 如图4所示，重叠社团合并的具体流程如下：
[0091] （1）计算重叠社团集合C中任意两个社团之间的重叠率 计算方式如下：
[0092]
[0093] |C′i|表示C'i节点的个数，|C'i∩C'j|表示C'i和C'j重叠点个数；
[0094] （2）合并重叠率大于0.8的社团，并从C中删除被合并的社团；最终得到合并后的重叠社团集合Cmerged＝{C″1,C″2,...,C″i,...,C″s '}，其中s表示合并后的社团个数，C″i表示第i个社团。
