一种基于元社区一致性的集成社区检测方法及系统

摘要

本发明提供了一种基于元社区一致性的集成社区检测方法及系统，包括：对原网络进行社区划分，基于不同社区之间的相似性，构建一个多部图；对所述多部图进行重划分，获取元社区；基于网络节点在所述元社区中的隶属关系，构建元共识网络；基于所述元共识网络获取所述原网络的社区结构，完成集成社区检测。相较于现有的集成社区检测方法本发明构建元共识图的过程中使用了一种基于三元闭包的采样方法，能够优先减少计算代价，考虑了局部拓扑特性的社区相似性度量，使得检测结果更为准确。

说明书

技术领域

本发明属于集成社区检测领域，尤其涉及一种基于元社区一致性的集成社区检测方法及系统。

背景技术

在集成社区检测的研究中，比较经典的有LF consensus方法。该方法对多次社区划分中节点成对出现在同一社区的频率做统计，以此构建“共识图”，而后在共识图上运行社区检测算法，并对此过程进行循环迭代。近期提出的MeDOC是另一种集成方法

发明内容

为解决上述技术问题，本发明提出了一种基于元社区一致性的集成社区检测方法及系统。

一方面为实现上述目的，本发明提供了一种基于元社区一致性的集成社区检测方法，包括：

对原网络进行社区划分，基于不同社区之间的相似性，构建一个多部图；

对所述多部图进行重划分，获取元社区；

基于网络节点在所述元社区中的隶属关系，构建元共识网络；

基于所述元共识网络获取所述原网络的社区结构，完成集成社区检测。

可选地，根据社区检测算法对所述原网络进行社区划分；

所述社区检测算法包括：基于模块度的方法、基于信息论的方法、标签传播方法和基于物理模型的方法。

可选地，获取所述不同社区之间的相似性包括：

对所述不同社区之间绘制连边；

对所述连边根据相似性度量进行加权，获取所述不同社区之间的相似性。

可选地，所述相似性度量为：

其中，SQ()为基于模块性的相似度，C

可选地，对所述多部图进行重划分的方式为：选用RAlgo算法。

可选地，所述隶属关系为：所述网络节点隶属于所述多部图后，又隶属于所述元社区。

可选地，构建所述元共识网络包括：

基于所述隶属关系，统计网络节点对在所述元社区中共同出现的次数，构建元共识矩阵；

对所述元共识矩阵寻找三元闭包进行采样，获得所述元共识网络。

可选地，对所述元共识矩阵寻找三元闭包进行采样包括：

在所述元共识矩阵中，计算互为邻居的节点对被划分到同一社区的频率；

预设频率阈值，对所述频率小于所述频率阈值的进行过滤，获取过滤后的所述元共识矩阵；

对过滤后的所述元共识矩阵中的每个节点选择一对邻居，完成所述元共识矩阵采样。

另一方面为实现上述目的，本发明还提供了一种基于元社区一致性的集成社区检测系统，包括：第一构建模块、重划分模块、第二构建模块和输出模块；

所述第一构建模块用于对原网络进行社区划分，基于不同社区之间的相似性，构建一个多部图；

所述重划分模块用于对所述多部图进行重划分，获取元社区；

所述第二构建模块用于基于网络节点在所述元社区中的隶属关系，构建元共识网络；

所述输出模块用于基于所述元共识网络获取所述原网络的社区结构，完成集成社区检测。

与现有技术相比，本发明具有如下优点和技术效果：

本发明首先将M个基算法的K次运行结果进行集成，根据集成构建一个多部图；而后通过对多部图的重划分得到元社区；通过节点对在元社区中的共现关系构建元共识网络；最后通过对元共识网络的重划分得出社区结构。构建元共识图的过程中使用了一种基于三元闭包的采样方法，以减少计算代价。提出了一种考虑了局部拓扑特性的社区相似性度量，使得结果更为准确。

附图说明

构成本申请的一部分的附图用来提供对本申请的进一步理解，本申请的示意性实施例及其说明用于解释本申请，并不构成对本申请的不当限定。在附图中：

图1为本发明实施例1的一种基于元社区一致性的集成社区检测方法流程示意图；

图2为本发明实施例1的MeCon具体工作流示意图；

图3为本发明实施例2的一种基于元社区一致性的集成社区检测系统示意图。

具体实施方式

需要说明的是，在不冲突的情况下，本申请中的实施例及实施例中的特征可以相互组合。下面将参考附图并结合实施例来详细说明本申请。

需要说明的是，在附图的流程图示出的步骤可以在诸如一组计算机可执行指令的计算机系统中执行，并且，虽然在流程图中示出了逻辑顺序，但是在某些情况下，可以以不同于此处的顺序执行所示出或描述的步骤。

实施例1

本发明提供了一种基于元社区一致性的集成社区检测方法，包括：

对原网络进行社区划分，基于不同社区之间的相似性，构建一个多部图；

对多部图进行重划分，获取元社区；

基于网络节点在元社区中的隶属关系，构建元共识网络；

基于元共识网络获取原网络的社区结构，完成集成社区检测。

进一步地，根据社区检测算法对原网络进行社区划分；

社区检测算法包括：基于模块度的方法、基于信息论的方法、标签传播方法和基于物理模型的方法。

进一步地，获取不同社区之间的相似性包括：

对不同社区之间绘制连边；

对连边根据相似性度量进行加权，获取不同社区之间的相似性。

进一步地，相似性度量为：

其中，SQ()为基于模块性的相似度，C

进一步地，对多部图进行重划分的方式为：选用RAlgo算法。

进一步地，

隶属关系为：网络节点隶属于多部图后，又隶属于元社区。

进一步地，构建元共识网络包括：

基于隶属关系，统计所有网络节点对在元社区中共同出现的次数，构建元共识矩阵；

对元共识矩阵寻找三元闭包进行采样，获得元共识网络。

进一步地，对元共识矩阵寻找三元闭包进行采样包括：

在元共识矩阵中，计算互为邻居的节点对被划分到同一社区的频率；

预设频率阈值，对频率小于频率阈值的进行过滤，获取过滤后的元共识矩阵；

对过滤后的元共识矩阵中的每个节点选择一对邻居，完成元共识矩阵采样。

如图1所示，本实施例提供了一种基于元社区一致性的集成社区检测方法(简称MeCon)，具体包括：

(1)构建多部网络。对于输入网络G，MeCon将基算法族

其中，基算法族

(2)对于多部图的重划分。此步中，在多部网络GP上运行社区检测算法RAlgo，输出由L个社区组成的社区结构

(3)构建元共识网络。在步骤1中，获得集成

(i)仅对在G中互为邻居的节点对i和j计算

(ii)阈值过滤。设置阈值τ，将小于τ值的矩阵项置零。此步骤可以移除弱连接以过滤确定性不高的共现关系。通过这一步，有可能会产生一些孤立节点。如果某个节点真的断开了连接，通过恢复其权重最高的一条连边来将它连回图中，以便让图始终处于连通状态。

(iii)随机选择输入网络G中的m(网络的边数)个节点，为其中的每个节点随机选择一对邻居，分别为节点j和k；如果矩阵项

(4)最终得出社区结构。对元共识网络

关于上述提到的社区间的相似性S，本实施例提出一种基于模块度的社区相似性度量SQ。一个划分的模块度可按下式计算：

从单个节点的角度看，模块度实际上定义了一种节点相似性的度量，节点i和j之间的相似度可以写成：

直接将上式作为节点的相似性度量存在以下问题：由于邻接矩阵中有

依据上式，社区C

本实施例为输入MeCon的划分设计了一个筛选过程，从基算法生成的MK个基本划分中，筛选S个作为MeCon的输入。筛选的标准同时将划分的质量以及划分之间的差异性作为依据，可计算如下：

其中Q和NMI分别指模块度和归一化互信息，P

利用穷举法求解Score的最大值计算复杂度过高，本实施例根据贪心策略求解：先将集成中的所有划分依据Q降序排序，将Q最大的划分加入候选集，然后逐渐向候选集中添加划分，每一次都添加使下式最大的那个划分，直到选出S个划分为止。

其中

在本实施例中还提供一个简单的实例来表述MeCon算法的具体工作流程。如图2所示，虚线代表算法划分出的社区边界。假设基算法在第一步中生成了三个不同的社区结构，对于每个社区进行分组编号，划分1中的两个社区分别标为C

MeCon算法的第二步是在得出的三部图上运行标准社区检测算法，输出的社区结构即为“元社区”。可以看到，三部图中的节点C

时间复杂度分析

MeCon算法中计算成本较高的主要有两个过程：在第一步中构建多部图的过程和在第三步中构建元共识矩阵的过程。这两个过程的时间复杂度可估计如下：

(1)对于前者来说，最坏的情况是：一个划分中的每个节点都连接到另一个划分的每个节点上。当基算法的数量为M，每个算法运行次数为K，每个划分的平均大小为

(2)对于后者来说，由于利用了三元闭包采样的过程来代替对每一对顶点进行计算，时间复杂度降低至近似线性的O(m)，m为输入网络的边数。

MeCon算法的平均时间复杂度受实验中的实际参数影响。如人工网络的实验中，参数会影响

实施例2

如图3所示，本实施例提供了一种基于元社区一致性的集成社区检测系统，包括：第一构建模块、重划分模块、第二构建模块和输出模块；

第一构建模块用于对原网络进行社区划分，基于不同社区之间的相似性，构建一个多部图；

重划分模块用于对多部图进行重划分，获取元社区；

第二构建模块用于基于网络节点在元社区中的隶属关系，构建元共识网络；

输出模块用于基于元共识网络获取原网络的社区结构，完成集成社区检测。

实施例3

社团检测算法旨于划分复杂网络的社团结构，获得高质量的社团划分结构，根据划分的社团结构可以实现众多实际应用。好友推荐，商品推荐，短视频推荐等是当前的大数据时代最为热点的应用方向，本实施例以好友推荐作为示例，介绍社团检测算法在好友推荐中的应用流程:

MeCon算法首先将M个基算法的K次运行结果进行集成，根据集成构建一个多部图；而后通过对多部图的重划分得到元社区；通过节点对在元社区中的共现关系构建元共识网络；最后通过对元共识网络的重划分得出社区结构。构建元共识图的过程中使用了一种基于三元闭包的采样方法，以减少计算代价。提出了一种考虑了局部拓扑特性的社区相似性度量，使得结果更为准确。将MeCon算法在好友推荐中进行应用的流程如下：

1.MeCon算法的输入数据为邻接矩阵，对应复杂网络的结构信息，因此在进行信息采集时，需要获取用户的好友信息，用户的好友信息量化获得复杂网络的邻接矩阵。

2.根据获得的复杂网络执行MeCon算法。首先根据集成构建多部图，其中多部图中不同部分之间的边权值代表社区相似度，可直接以Jaccard相似度计算，也可利用本文提出的相似度计算；而后对多部图进行重划分得到元社区；再然后根据元社区构建元共识网络；最后划分元共识网络得到社团划分结果。

3.根据社团划分结果，每个用户具有划分结果的集合，与用户当前好友的集合进行对比，取两集合的差集作为用户好友推荐的内容。MeCon算法简化了好友推荐的步骤。

以上，仅为本申请较佳的具体实施方式，但本申请的保护范围并不局限于此，任何熟悉本技术领域的技术人员在本申请揭露的技术范围内，可轻易想到的变化或替换，都应涵盖在本申请的保护范围之内。因此，本申请的保护范围应该以权利要求的保护范围为准。