一种基于密度峰值优化的标签传播社团检测方法及装置

摘要

本发明属于复杂网络技术领域，公开一种基于密度峰值优化的标签传播社团检测方法及装置。本发明首先引入密度峰值来发现聚类中心，先确定社团的雏形，将复杂网络的社团个数和聚类中心固定下来，然后再采用标签传播算法来检测社团，提高了社团发现的准确性和鲁棒性，减少了迭代次数，加速了社团的形成。在基准网络和经典真实网络上的测试结果中发现，本发明和其它先进算法相比，本发明可以快速有效求解社团检测问题，在没有先验条件的情况下可以预测社团数量，发现的社团数量总是和实际社团数量保持一致，具有较好的稳定性和准确性。

说明书

技术领域

本发明属于复杂网络技术领域，尤其涉及一种基于密度峰值优化的标签传播社团检测方法及装置。

背景技术

社团结构是复杂网络中极为重要的属性。社团结构在分析社会网络中的交际关系、分析生物网络中组织和器官的作用关系、分析科学家协作网络中的引文关系中都起着至关重要的作用。因此，在过去的十几年里，从复杂网络中发现社团结构得到了广泛的研究。2002年，Girvan和Newman(M.Girvan,M.E.J.Newman.Community Structure in Socialand Biological Networks[J].Proceedings of the National Academy of Sciences ofthe United States of America,2002,99(12).)取得了开创性的工作，指出复杂网络普遍存在社团结构，并且提出模块度Q来衡量网络中社团的稳定程度。社团结构的定义虽然没有明确的相关研究得到一致确定，但通常认为一个社团就是一组节点，也可以称为一个群落或者一组模块。这些节点有着社团内部连接紧密，社团外部连接稀疏的特点。

基于标签传播的社团发现算法作为当前研究的热点之一，在社团检测中得到了广泛的应用。该算法是基于图的半监督学习方法，半监督学习的优势在于能通过少量的已标记样本来确定大量未标记的样本，从而提高学习过程中的有效性。标签传播的基本思路是从已经得到标记的节点的标签信息，利用节点之间的拓扑关系，预测未标记的节点的标签信息，最后完成图的划分，形成聚类结构。虽然该算法有实现简单、逻辑清晰、无需事前知道社团个数、时间复杂度接近线性等优点，但是划分结果不稳定、随机性强是这个算法的缺陷。在标签传播算法每次迭代过程中，节点归属哪个社团取决于其邻居节点累计权重最大的标签，因此当一个节点的最大邻居标签出现不止一个时，就会随机选择一个作为自己的标签。这种随机性会带来雪崩效应，即刚开始出现的一个小小的聚类结果错误会被不断的放大。并且节点标签的更新顺序也会对结果造成不小的影响，越重要的节点越早更新会加速收敛的过程。在标签传播算法中，初始标签的设置越接近核心点越能得到准确的聚类效果。

发明内容

本发明针对现有的标签传播算法中随机选择标签，社团划分结果不稳定的问题，提出一种基于密度峰值优化的标签传播社团检测方法及装置。

为了实现上述目的，本发明采用以下技术方案：

一种基于密度峰值优化的标签传播社团检测方法，包括：

步骤1：从复杂网络G＝(V,E)中构建邻接矩阵A；V为G的节点集，包含n个节点；E为G的边集，包含m条边；

步骤2：采用余弦相似性计算复杂网络中节点间的相似度矩阵S；

步骤3：基于节点间的相似度矩阵S计算复杂网络中节点的距离矩阵d；

步骤4：采用高斯核函数计算节点的局部密度并进行标准化，得到标准化后节点的局部密度ρ

步骤5：基于节点的距离矩阵d和标准化后节点的局部密度ρ

步骤6：基于标准化后节点的局部密度ρ

步骤7：采用高斯核函数的方法构建节点间的权重，并基于节点间的权重构建概率转移矩阵P；

步骤8：基于获取的K个核心点构建标签矩阵F；

步骤9：将标签矩阵F按照概率转移矩阵P中的节点间相似度进行传播，重置标签矩阵F，再将标签矩阵F进行传播、重置，迭代这个过程，直到F中的未标记的标签变化差值到达临界点，完成标签的划分。

进一步地，所述步骤3包括：

按照如下方式计算复杂网络中节点的距离矩阵d：

其中，d

进一步地于，所述步骤5包括：

按照如下方式计算复杂网络中节点与高密度节点间的距离：

其中，ρ

进一步地，所述步骤6包括：

计算每个节点处的乘积γ＝ρ

一种基于密度峰值优化的标签传播社团检测装置，包括：

第一构建模块，用于从复杂网络G＝(V,E)中构建邻接矩阵A；V为G的节点集，包含n个节点；E为G的边集，包含m条边；

第一计算模块，用于采用余弦相似性计算复杂网络中节点间的相似度矩阵S；

第二计算模块，用于基于节点间的相似度矩阵S计算复杂网络中节点的距离矩阵d；

第三计算模块，用于采用高斯核函数计算节点的局部密度并进行标准化，得到标准化后节点的局部密度ρ

第四计算模块，用于基于节点的距离矩阵d和标准化后节点的局部密度ρ

核心点得出模块，用于基于标准化后节点的局部密度ρ

第二构建模块，用于采用高斯核函数的方法构建节点间的权重，并基于节点间的权重构建概率转移矩阵P；

第三构建模块，用于基于获取的K个核心点构建标签矩阵F；

标签传播模块，用于将标签矩阵F按照概率转移矩阵P中的节点间相似度进行传播，重置标签矩阵F，再将标签矩阵F进行传播、重置，迭代这个过程，直到F中的未标记的标签变化差值到达临界点，完成标签的划分。

与现有技术相比，本发明具有的有益效果：

本发明在没有先验条件的情况下可以预测社团数量，避免了随机标签算法的划分不稳定、随机性强的缺陷，有效地提高了社团挖掘的准确性和算法的稳定性。此外因为构建了概率转移矩阵，减少了标签传播的迭代次数，使得本发明具有高效的运算效率，最后能够快速找到网络的社团结构。在基准网络和经典真实网络上的测试结果中发现，本发明和其它先进算法相比，本发明可以快速有效求解社团检测问题，在没有先验条件的情况下可以预测社团数量，发现的社团数量总是和实际社团数量保持一致，具有较好的稳定性和准确性。

附图说明

图1为本发明实施例一种基于密度峰值优化的标签传播社团检测方法的基本流程图；

图2为不同方法在LFR基准数据集上的NMI实验结果比较图；

图3为采用本发明方法对Football网络进行划分的可视化结果图；

图4为采用本发明方法对Karate网络进行划分的可视化结果图；

图5为采用本发明方法对Dolphins网络进行划分的可视化结果图。

具体实施方式

下面结合附图和具体的实施例对本发明做进一步的解释说明：

实施例1

如图1所示，一种基于密度峰值优化的标签传播社团检测方法，为表述方便，简称为DPLPA，包括：

步骤S101：从复杂网络G＝(V,E)中构建邻接矩阵A；V为G的节点集，包含n个节点；E为G的边集，包含m条边；

步骤S102：采用余弦相似性计算复杂网络中节点间的相似度矩阵S；

步骤S103：基于节点间的相似度矩阵S计算复杂网络中节点的距离矩阵d；

步骤S104：采用高斯核函数计算节点的局部密度并进行标准化，得到标准化后节点的局部密度ρ

步骤S105：基于节点的距离矩阵d和标准化后节点的局部密度ρ

步骤S106：基于标准化后节点的局部密度ρ

步骤S107：采用高斯核函数的方法构建节点间的权重，并基于节点间的权重构建概率转移矩阵P；

步骤S108：基于获取的K个核心点构建标签矩阵F；

步骤S109：将标签矩阵F按照概率转移矩阵P中的节点间相似度进行传播，重置标签矩阵F，再将标签矩阵F进行传播、重置，迭代这个过程，直到F中的未标记的标签变化差值到达临界点，完成标签的划分。

进一步地，所述步骤S103包括：

按照如下方式计算复杂网络中节点的距离矩阵d：

其中，d

进一步地于，所述步骤S105包括：

按照如下方式计算复杂网络中节点与高密度节点间的距离：

其中，ρ

进一步地，所述步骤S106包括：

计算每个节点处的乘积γ＝ρ

具体地，

设G＝(V,E)是无向无权的复杂网络。节点集V包含n个节点，边集E包含m条边，图G的邻接矩阵为A，其中如果节点i和节点j有连接的一条边，那么邻接矩阵A中的a

其中N(i)和N(j)分别代表节点i和节点j的邻居节点，|N(i)|表示节点i邻居节点的数目，因此分子式|N(i)∩N(j)|表示节点i和节点j共享的邻居数目，分母式

其中σ是一个小的正数，为了避免分母为0。

接下来，采用高斯核函数计算节点的局部密度，公式表示如下：

其中ρ

然后，定义节点与高密度节点间的距离公式：

其中，当节点i的局部密度最大时，它的距离是节点i与其它节点距离中的最大值。当节点i的局部密度不是最大时，它的距离是在局部密度稍大于节点i的节点与节点i的距离。

之后对δ

阈值d

最后，计算每个节点处的乘积γ＝ρ

标签传播算法是基于图的聚类算法，因此需要先构建一个图G。图的节点就是数据点，本发明采用高斯核函数的方法构建两个节点之间的权重：

其中d

接下来，通过节点之间的边传播已知的label。边的权重越大，表示两个节点越相似，那么label越容易传播过去。定义概率转移矩阵：

其中P

F＝[YL,YU] (13)

之后将标签矩阵F按照概率矩阵P中的节点间相似度来进行传播，公式表达为：

F＝PF (14)

当传播一遍后，因为已知的标签矩阵F中的YL在传播过程中发生了改变，但是YL是之前的预获取，是准确的标签不应该改变，所以需要重置标签矩阵F，公式为：

FL＝YL (15)

然后，再将标签矩阵F进行传播，重置，迭代这个过程，直到F中的未标记的标签变化差值到达临界点，这时DPLPA完成了标签的划分。

表1 DPLPA伪码

获得聚类后的标签矩阵F后，DPLPA会从F中将相同维的数值为1的节点聚在一起形成一个社团，将所有节点按维数划分完，聚类算法结束，复杂网络也完成了划分。

为评估DPLPA效果，本发明使用各种真实和合成的数据集来进行测试，同时和一些经典方法来进行比较，其中包括：Newman的快速贪婪发现算法(FN)(Newman M E J.Fastalgorithm for detecting community structure in networks.[J].Physicalreview.E,Statistical,nonlinear,and soft matter physics,2004,69(6Pt 2).)，Louvain算法(B G L)(Vincent D Blondel,Jean-Loup Guillaume,Renaud Lambiotte,Etienne Lefebvre.Fast unfolding of communities in large networks[J].Journalof Statistical Mechanics:Theory and Experiment,2008,2008(10).)，原始LPA算法(Raghavan Usha Nandini,Albert Réka,Kumara Soundar.Near linear time algorithmto detect community structures in large-scale networks.[J].Physical review.E,Statistical,nonlinear,and soft matter physics,2007,76(3Pt 2).)，改进标签传播算法(LPAm)(Barber M J,Clark J W.Detecting network communities by propagatinglabels under constraints[J].Physical Review E,2009,80(2):026129.)。实验的硬件环境如下：Inter(R)Core(TM)i7-7700M CPU、3.60GHz和8GB内存。编程语言采用Python3.764-bit。

本发明使用Newman提出的模块度函数Q作为实验的评价指标。模块度定义为：

其中E代表社团网络的总边数，A表示的是邻接矩阵，k

其中，当节点i和节点j在同一个社团时，θ(c

为了验证DPLPA的准确性，本发明还采用标准化互信息(NMI)来衡量两个聚类结果的相似程度，它是社团发现的重要衡量指标之一，基本可以客观地评价出一个社团划分与真实划分之间相比的准确度。NMI的值域为[0,1]，越高的值代表划分的社团越接近真实社团结果。NMI(A,B)定义为：

其中，A(B)表示社团发现算法A(B)，C为混淆矩阵，C

使用人工合成的网络对算法的有效性进行评测成为检验算法优劣的一种有效手段，其中最为常用的用于社团检测的基准测试网络是由Lancichineti Andrea提出LFRBenchmark。LFR基准网络是在GN基准网络上的扩展，具有较高的实用价值。LFR基准网络反映了群落分布的异质性和节点度的幂律分布，其中一些重要的参数描述如下：n表示网络节点数，k表示节点的平均度，max k表示节点的最大度，min c表示社团大小的最小值，max c表示社团大小的最大值，τ1和τ2分别表示节点度和社团大小的幂律分布的负指数，μ等于网络中社团之间相连接的边数与总边数的比值，用来表示网络中社团明显程度，μ值越小社团的结构越明显。图2是算法在LFR基准数据集上的NMI实验结果比较。

LFR实验设置的参数为：n＝1000，k＝15，maxk＝40，minc＝20，maxc＝50，τ1＝2，τ2＝1，μ的范围是从0.1到0.8。从图2可以看出当μ较小，即复杂网络的社团结构较明显时，除FN算法外，其余算法结果的NMI值都很高，但随着μ的增大，社团结构的越来越复杂，FN算法和LPA算法的NMI值都开始显著下降，剩下的算法都是在μ值为0.6时开始下降，但是DPLAP算法相较BGLL和LPAm算法下降的相对缓慢并且最后NMI值较高，表明DPLPA算法在进行社团探索的准确率较高，在高复杂度的社团探索中有更好的稳定性。

为了进一步的比较算法的优劣，本发明还在多个真实存在的社团网络中进行了算法测试。这些网络大小不同但都具有代表性，涉及各个领域。具体细节如表2所示，其中n代表节点，m代表边数，k代表已经明确的社团数。

表2 真实网络的具体描述

其中，Karate是美国一所大学空手道俱乐部的成员关系数据集，根据俱乐部成员之间的交往情况所构建，常用于社会网络的分析。Dolphins是对62只宽嘴海豚的生活习性所构造的成员网络，经常在一起的海豚对应于节点之间的一条边。Polbook是通过美国Amazon上销售的政治书所构建的社团网络，每一个节点代表一本书，如果两本书被同一个顾客购买，那么它们之间在对应的节点上有一条边。Football是美国大学足球赛程所构建的网络，节点代表参赛队伍，如果它们之间有比赛，那么节点之间就会有一条边。不同算法在不同网络上的运算结果如表3所示。

表3 真实网络中不同算法的Q值比较

为了更好的比较DPLPA算法对数据集的聚类效果，本发明通过Football数据集做详细的说明。其中Football数据集的实际分组情况如表4所示，DPLPA算法的聚类效果如图3所示。

表4 足球数据集网络的实际分组情况

从表3可以看出，虽然本发明的方法的Q值在一些数据集中不是最好的，但是DPLPA算法的划分结果和实际的社团分布是完全一样的，这可以从表4、图3看出。这主要是因为在标签传播的过程中，概率转移矩阵很好地抑制了传播过程的随机性，使得节点的每次更新都尽可能的向着同一个社团节点的标签进行更新，使得社团划分的结果更稳定、更接近真实社团情况。不同算法在不同网络上的K值比较如表5所示。

表5 真实网络中不同算法的K值比较

此外从表5发现DPLPA算法可以检测社团的真实数量，与实际K值相比是完全一致的。这主要是因为DPLPA算法在最开始就通过网络的拓扑结构开始计算节点的局部密度和距离，并且通过决策图的方式来选择K值的数量。因此不需要提供K值，DPLPA算法具有检测K值的优点。

为了更好的显示实验结果，本发明将Karate网络和Dolphins网络作为案例研究，对检测的社团进行了可视化。相同社团的节点以相同的颜色进行划分。图4是对Karate网络进行DPLPA算法划分的可视化结果。图5是对Dolphins网络进行DPLPA算法划分的可视化结果。

从图4可以看出，节点1和节点34的局部密度最高，从图5可以看出，节点15和节点18的局部密度最高，并且这些节点都有较高的节点距离，因此DPLPA算法选取这些节点为K是非常合理，划分的结果与实际社团的划分结果也保持完全一致。因此DPLPA算法是可以在真实社团进行高质量社团检测。

综上，本发明在没有先验条件的情况下可以预测社团数量，避免了随机标签算法的划分不稳定、随机性强的缺陷，有效地提高了社团挖掘的准确性和算法的稳定性。此外因为构建了概率转移矩阵，减少了标签传播的迭代次数，使得本发明具有高效的运算效率，最后能够快速找到网络的社团结构。在基准网络和经典真实网络上的测试结果中发现，本发明和其它先进算法相比，本发明可以快速有效求解社团检测问题，在没有先验条件的情况下可以预测社团数量，发现的社团数量总是和实际社团数量保持一致，具有较好的稳定性和准确性。

实施例2

本发明还公开一种基于密度峰值优化的标签传播社团检测装置，包括：

第一构建模块，用于从复杂网络G＝(V,E)中构建邻接矩阵A；V为G的节点集，包含n个节点；E为G的边集，包含m条边；

第一计算模块，用于采用余弦相似性计算复杂网络中节点间的相似度矩阵S；

第二计算模块，用于基于节点间的相似度矩阵S计算复杂网络中节点的距离矩阵d；

第三计算模块，用于采用高斯核函数计算节点的局部密度并进行标准化，得到标准化后节点的局部密度ρ

第四计算模块，用于基于节点的距离矩阵d和标准化后节点的局部密度ρ

核心点得出模块，用于基于标准化后节点的局部密度ρ

第二构建模块，用于采用高斯核函数的方法构建节点间的权重，并基于节点间的权重构建概率转移矩阵P；

第三构建模块，用于基于获取的K个核心点构建标签矩阵F；

标签传播模块，用于将标签矩阵F按照概率转移矩阵P中的节点间相似度进行传播，重置标签矩阵F，再将标签矩阵F进行传播、重置，迭代这个过程，直到F中的未标记的标签变化差值到达临界点，完成标签的划分。

进一步地，所述第二计算模块具体用于：

按照如下方式计算复杂网络中节点的距离矩阵d：

其中，d

进一步地于，所述第四计算模块具体用于：

按照如下方式计算复杂网络中节点间的距离：

其中，ρ

进一步地，所述核心点得出模块具体用于：

计算每个节点处的乘积γ＝ρ

以上所示仅是本发明的优选实施方式，应当指出，对于本技术领域的普通技术人员来说，在不脱离本发明原理的前提下，还可以做出若干改进和润饰，这些改进和润饰也应视为本发明的保护范围。