一种基于中心节点图卷积网络的无监督社区发现方法

摘要

本发明公开了一种基于中心节点图卷积网络的无监督社区发现方法，构建检测模型CN‑GCN，采用“中心‑扩展”算法在确定中心节点的基础上，扩展拥有更多共同邻居和具有类似社区成员身份的节点，形成中心节点簇；利用中心节点簇训练GCN模型，用训练好的GCN模型对整个网络节点进行聚类或社区发现。本发明的社区中心节点簇可以容纳拥有更多共同邻居和具有类似社区成员身份的节点，这些节点具有类似属性，进而提高社区子图的模块性；本发明结合社区中心节点的CN‑GCN模型可以提高节点领域的划分能力。

说明书

技术领域

本发明涉及图卷积网络GCN无监督社区发现领域，具体是一种基于中心节点的GCN无监督社区发现方法。

背景技术

复杂网络如生物网络、通信网络和社会网络，分别是生物系统、通信系统和相互作用系统的抽象表示，网络既是一种表示形式，也是一种深入了解复杂系统的分析工具。复杂网络最重要的特性之一是其社区结构，近年来，网络社区检测是复杂网络领域的的研究热点。网络社区被定义为一组内部紧密连接的节点，在网络中扮演着非常重要的角色。社区检测的目标是根据网络拓扑、节点相似性等，将网络中的每个节点分配给一个社区，可以帮助揭示和理解复杂系统的重要隐藏属性。

图卷积网络(Graph Convolutional Networks,GCN)，由于其在图节点有监督和半监督分类方面的成功，近年来引起了广泛的关注，并用于社区检测。如文献MRFasGCN，是一种基于GCN的半监督社区检测方法，在GCN框架中纳入了社区的马尔可夫随机场(MarkovRandom field,MRF)建模，取得不错的效果。JIN 2020，在MRFasGCN 中引入以社区为中心的双解码器，以无监督的方式分别重建网络结构和节点属性，实现在输入空间中的社区检测。除了网络拓扑特性，社区中心节点相似性度量在图聚类算法起着重要作用。ISCD+，Chen等算法根据社区内节点间的连通能力定义节点间的相似性，基于此进行有效的社区发现。分析现有方法，在社区检测中虽然引入GCN取得不错的效果，但是没有考虑社区中心节点和中心节点簇在社区监测问题中的重要性。在当前复杂网络的研究中，对网络中心节点和中心节点簇的发现结果进行合理度量，可以提高节点领域的划分能力，从而提高社区检测能力。

发明内容

本发明要解决的技术问题在于，针对现有技术中存在的不足，本发明提供一种基于中心节点的GCN无监督社区发现方法。

本发明解决其技术问题所采用的技术方案是：构造一种基于中心节点的GCN无监督社区发现方法，包括：

步骤1，构建网络G＝(V,E),其中，V和E分别表示节点和边的集合；顶点属性X,令X∈R

步骤2，计算G的节点相似性矩阵S

步骤3，根据节点相似性矩阵和节点权重矩阵计算初始簇中心 ch；

步骤4，用初始簇训练图卷积网络模型,

步骤5，用训练好的图卷积网络模型对图G进行划分,得到当前簇发现结果Ω0.计算当前簇发现结果的目标函数值F(Ω0)；

步骤6，输出图聚类结果Ω＝{V1,V2,…,Vm}，作为无监督网络社区。

其中，计算G的节点相似性矩阵S

S

其中，S

给定网络G＝(V,E)及S

其中，根据节点相似性矩阵和节点权重矩阵计算初始簇中心ch，根据公式(1)(2)计算：

对第h个簇，选择

其中，用初始簇训练图卷积网络模型，

与现有技术相比，本发明提出了一种基于中心节点图卷积网络的无监督社区发现方法，构建检测模型CN-GCN，采用“中心-扩展”算法在确定中心节点的基础上，扩展拥有更多共同邻居和具有类似社区成员身份的节点，形成中心节点簇；利用中心节点簇训练GCN模型，用训练好的GCN模型对整个网络节点进行聚类或社区发现。本发明的社区中心节点簇可以容纳拥有更多共同邻居和具有类似社区成员身份的节点，这些节点具有类似属性，进而提高社区子图的模块性；本发明结合社区中心节点的CN-GCN模型可以提高节点领域的划分能力。

附图说明

下面将结合附图及实施例对本发明作进一步说明，附图中：

图1是本发明提供的一种基于中心节点的GCN无监督社区发现方法的流程示意图。

图2是本发明提供的一种基于中心节点的GCN无监督社区发现方法的整体框架示意图。

图3是本发明提供的一种基于中心节点的GCN无监督社区发现方法在数据集Karate上与经典5种算法对比结果示意图。

图4是本发明提供的一种基于中心节点的GCN无监督社区发现方法在数据集dolphins上与经典5种算法对比结果示意图。

图5是本发明提供的一种基于中心节点的GCN无监督社区发现方法在数据集polbooks上与经典5种算法对比结果示意图。

图6是本发明提供的一种基于中心节点的GCN无监督社区发现方法在数据集football上与经典5种算法对比结果示意图。

图7是本发明提供的一种基于中心节点的GCN无监督社区发现方法在数据集polblogs上与经典5种算法对比结果示意图。

具体实施方式

为了对本发明的技术特征、目的和效果有更加清楚的理解，现对照附图详细说明本发明的具体实施方式。

如图1和图2所示，本发明设计了一种基于中心节点的GCN无监督社区发现方法，首先采用“中心-扩展”算法在确定中心节点的基础上，扩展拥有更多共同邻居和具有类似社区成员身份的节点，形成中心节点簇。然后,用这些中心节点簇训练GCN模型，用训练好的GCN模型对整个网络节点进行聚类或社区发现。具体步骤包括：

步骤1，构建网络G＝(V,E),其中，V和E分别表示节点和边的集合；顶点属性X,令X∈R

步骤2，计算G的节点相似性矩阵S

步骤3，根据节点相似性矩阵和节点权重矩阵计算初始簇中心 ch；

步骤4，用初始簇训练图卷积网络模型,

步骤5，用训练好的图卷积网络模型对图G进行划分,得到当前簇发现结果Ω0.计算当前簇发现结果的目标函数值F(Ω0)；

步骤6，输出图聚类结果Ω＝{V1,V2,…,Vm}，作为无监督网络社区。

其中，计算G的节点相似性矩阵S

S

其中，S

给定网络G＝(V,E)及S

其中，根据节点相似性矩阵和节点权重矩阵计算初始簇中心ch，根据公式(1)(2)计算：

对第h个簇，选择

其中，用初始簇训练图卷积网络模型，

本发明的社区发现方法，应用在真实数据集空手道俱乐部 (Zachary's KarateClub)、海豚社交网络(Dolphins Social Network)、2004 年美国政治博客网络Polblogs、美国政治相关书籍Polbooks和2000 赛季大学生美式大学生足球网络(American CollegeFootball Network) 五个带标签数据集进行实验，对CN-GCN模型进行评测，并与与经典的5种算法Fluid-C、EM、LPA、BGLL、GN来对本发明提出的 CN-GCN方法进行评测.实验结果如图3、4、5、6、7所示。选用标准互信息(NMI)、调整兰德系数(ARI)和模块性对聚类结果进行评价，划分结果与原始划分的吻合程度越高，NMI、ARI和模块性的值越高。

从模块性来看，本发明方法比EM高20％，略低于其它四种方法； BGLL方法的模块性较高，但针对Football这个数据集，本发明 CN-GCN的模块性与BGLL的模块性能基本持平。这是因为参赛队被分成8-12个小组的会议，在实验中取12个社区数，社区数的个数增多使得中心节点个数增加，从而提高CN-GCN的效果。从实验结果如图3和图4，可以得到本发明方法在NMI、ARI效果均高于其他五种典型方法，这进一步验证了它相对于现有方法的有效性。这也证实了结合中心节点的图卷积网络CN-GCN方法有效提高聚类效果。

本发明算法在大多数情况下性能均优于比较算法.其中，Fluid-C 和LPA代表了CD算法中的最新技术。LPA建议的标签传播过程只使用网络结构来指导其进程，不需要外部参数设置。每个节点根据其近邻的社区对其所属的社区做出自己的决定。这些局部决策导致了特定网络中社区结构的出现。Fluid-C能够识别出高质量的社区，接近目前最先进的最佳选择。Fluid-C在NMI性能方面的主要限制是，由于瓶颈边缘的影响，它不能完全恢复混合参数较小的图上的ground truth共同体。然而，本文提出CN-GCN方法在5个数据集的NMI、 ARI性能上平均高于Fluid-C算法，从而说明了CN-GCN算法的有效性。本文提出可扩展的中心节点选取策略(即“中心-扩展”算法)，提高图卷积网络模型训练性能。

上面结合附图对本发明的实施例进行了描述，但是本发明并不局限于上述的具体实施方式，上述的具体实施方式仅仅是示意性的，而不是限制性的，本领域的普通技术人员在本发明的启示下，在不脱离本发明宗旨和权利要求所保护的范围情况下，还可做出很多形式，这些均属于本发明的保护之内。