中文摘要
复杂系统可以抽象为复杂网络，其中节点表示实体，边表示实体间的关系。网
络中节点间往往存在聚集性，即功能相似的节点形成了连接相对紧密的功能模块，
也称为社区或簇。如社交网络中拥有相同兴趣或背景的个体形成一个社交圈；引文
网络中相互引用较多的文献组形成某一研究主题；生物网络中连接紧密的蛋白质组
形成功能团体来行使一定的生物功能等。图聚类方法可以发现网络中的社区结构，
在社交网络、引文网络、生物网络和基因调控网络等分析中有着重要作用。
研究人员基于模块度优化、标签传播、节点表示学习等思想提出了许多图聚类
方法，被成功应用于不同领域的复杂网络分析任务中。目前所处理的图结构数据复
杂性在不断增加，网络中社区结构的规模、社区内外部的连接模式、节点在社区结
构中的位置等都呈现了极大的不平衡性。这导致网络中不同节点的聚类难度存在显
著差异，位于类中心的节点通常与社区外节点连接较少，具有比较清晰的社区归
属，聚类难度相对较低；而位于类边缘的节点由于存在较多的外部连接，社区归属
不太清晰，导致其聚类难度偏高。如何有效判别网络中节点的聚类难度，为图聚类
过程提供指导，是提升图聚类算法性能的一个重要问题。本文对基于节点聚类难度
的图聚类算法开展研究，具体工作如下：
(1)提出了一种自监督节点聚类难度判别方法，并在此基础上设计了一种迭代
更新节点聚类难度的图聚类算法(GraphClusteringAlgorithmBasedonNode
ClusteringDifficultyDiscrimination,GCNCD)。该算法利用基聚类器的聚类结果一致
性判别节点的聚类难度，为聚类难度低的节点赋予伪标签；再利用伪标签监督信息
迭代降低其余节点的聚类难度，最终得到图聚类结果。算法GCNCD包括节点表示
模块、节点聚类难度判别模块、图聚类模块等3个主要模块。节点表示模块利用集
聚性和模块度约束节点表示，以得到类边界清晰的节点表示，从而为后续聚类任务
提供更具区分性的节点特征；聚类难度判别模块分别采用k-means和Softmax编码
器对节点进行聚类，根据聚类结果的一致性确定初始类结构并得到节点的初始聚类
难度，利用聚类难度低的节点伪标签信息，迭代更新网络中其余节点的聚类难度，
不断发现网络中聚类分配明确的节点；图聚类模块利用聚类难度低的节点所提供的
标签信息，采用标签传播算法得到最终的聚类结果。将所提算法GCNCD在6个引
文网络和3个生物数据集上与9种经典社区发现算法进行对比，结果表明GCNCD
I
在ACC、NMI、ARI和F1值等指标上表现良好。
(2)为消除基聚类器的选择对初始聚类难度判别的影响，给出了一种基于类分
布的节点聚类难度判别方法，并提出了一种利用节点类分布迭代更新聚类难度的图
聚类方法(GraphClusteringAlgorithmBasedonNodeClassDistribution,GCNC)。该算
法利用t-分布计算节点类分布，并用其初始化节点聚类难度；通过标签传播过程迭
代更新节点类分布和节点聚类难度，扩展易聚类节点范围，最终得到图聚类结果。
算法GCNC包括节点表示、聚类难度初始化、类分布及难度更新等3个模块，节点
表示模块通过引入模块度约束得到具有区分性的节点表示；聚类难度初始化模块利
用t-分布计算节点类分布，并初始化网络中易聚类节点，赋予其初始伪标签；类分
布及难度更新模块依据伪标签提供的自监督信息，通过迭代优化节点类分布来改善
聚类效果，在迭代的过程中不断选取高置信节点的标签来更新伪标签，优化模型以
得到最终的聚类结果。将所提算法GCNC在6个引文网络和3个生物数据集上与10
种聚类算法进行比较，结果表明了GCNC算法在ACC、NMI、ARI和F1值等指标
上表现良好。
关键词：图自监督机制；图聚类；图神经网络；标签传播；节点类分布
II