基于节点聚类复杂度的图聚类方法  

Graph Clustering Algorithm Based on Node Clustering Complexity

作　　者：郑文萍[1,2,3] 王富民 刘美麟 杨贵 ZHENG Wenping;WANG Fumin;LIU Meilin;YANG Gui(School of Computer and Information Technology,Shanxi University,Taiyuan 030006,China;Key Laboratory of Computation Intelligence and Chinese Information Processing of Ministry of Education,Shanxi University,Taiyuan 030006,China;Institute of Intelligent Information Processing,Shanxi University,Taiyuan 030006,China)

机构地区：[1]山西大学计算机与信息技术学院,太原030006 [2]计算智能与中文信息处理教育部重点实验室(山西大学),太原030006 [3]山西大学智能信息处理研究所,太原030006

出　　处：《计算机科学》2023年第11期77-87,共11页Computer Science

基　　金：国家自然科学基金(62072292);山西省1331工程项目。

摘　　要：图聚类可以发现网络中的社区结构,是复杂网络分析中的一项重要任务。针对不同节点的聚类难度各异的问题,提出了一种基于节点聚类复杂度的图聚类算法(Graph Clustering Algorithm Based on Node Clustering Complexity,GCNCC),用于判断节点的聚类复杂度,为聚类复杂度低的节点赋予伪标签,利用伪标签提供的监督信息降低其他节点的聚类复杂度,进而得到网络聚类结果。GCNCC包括节点表示、节点聚类复杂度判别和图聚类3个主要模块。节点表示模块得到保持网络集聚性的表示;节点聚类复杂度判别模块用于判断网络中的低聚类复杂度节点,并利用低聚类复杂度节点的伪标签信息来优化更新网络中其他节点的聚类复杂度;图聚类模块采用标签传播方法,将低聚类复杂度节点标签传播给高聚类复杂度节点,以得到聚类结果。在3个真实的引文网络和3个生物数据集上与9种经典算法进行对比,算法GCNCC在ACC,NMI,ARI和F1等方面均表现良好。Graph clustering is an important task in the analysis of complex networks,which can reveal the community structure within a network.However,clustering complexity of nodes varies throughout the network.To address this issue,a graph clustering algorithm based on node clustering complexity(GCNCC)is proposed.It calculates the clustering complexity of nodes and assigns pseudo-labels to nodes with low clustering complexity.Then it uses these pseudo-labels as supervised information to lower the clustering complexity of other nodes to obtain the community structure of the network.The GCNCC algorithm consists of three main modules:node representation,node clustering complexity assessment,and graph clustering.The node representation module represents nodes in a low-dimensional space to maintain the clustering of nodes,the node clustering complexity assessment module identifies low clustering complexity nodes,and assigns them pseudo-labels,which can be used to update the clustering complexity of other nodes.The graph clustering module uses label propagation to spread the pseudo-labels from nodes with low clustering complexity to those with high clustering complexity.Compared with 9 classic algorithms on 3 real citation networks and 3 biological datasets,the proposed GCNCC performed well in terms of ACC,NMI,ARI,and F1.

关 键 词：图聚类 节点聚类复杂度 网络嵌入 自监督 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]