基于因子图模型的动态图半监督聚类算法  

A Semi-supervised Clustering Algorithm Based on Factor Graph Model for Dynamic Graphs

作　　者：张建朋[1,2] 裴雨龙 刘聪 李邵梅 陈鸿昶[1] ZHANG Jian-Peng;PEI Yu-Long;LIU Cong;LI Shao-Mei;CHEN Hong-Chang(National Digital Switching System Engineering&Techno-logical R&D Center,Zhengzhou 450002,China;Eindhoven University of Technology,Eindhoven 5600 MB,the Netherlands;Department of Computer Science,Shandong University of Science and Technology,Qingdao 266590,China)

机构地区：[1]国家数字交换系统工程技术研究中心,郑州450002 [2]埃因霍温理工大学,荷兰埃因霍温5600MB [3]山东科技大学计算机学院,青岛266590

出　　处：《自动化学报》2020年第4期670-680,共11页Acta Automatica Sinica

基　　金：国家自然科学基金群体项目(61521003);国家重点研发计划项目(2016YFB0800101)资助。

摘　　要：针对动态图的聚类主要存在着两点不足:首先,现有的经典聚类算法大多从静态图分析的角度出发,无法对真实网络图持续演化的特性进行有效建模,亟待对动态图的聚类算法展开研究,通过对不同时刻图快照的聚类结构进行分析进而掌握图的动态演化情况.其次,真实网络中可以预先获取图中部分节点的聚类标签,如何将这些先验信息融入到动态图的聚类结构划分中,从而向图中的未标记节点分配聚类标签也是本文需要解决的问题.为此,本文提出进化因子图模型(Evolution factor graph model,EFGM)用于解决动态图节点的半监督聚类问题,所提EFGM不仅可以捕获动态图的节点属性和边邻接属性,还可以捕获节点的时间快照信息.本文对真实数据集进行实验验证,实验结果表明EFGM算法将动态图与先验信息融合到一个统一的进化因子图框架中,既使得聚类结果满足先验知识,又契合动态图的整体演化规律,有效验证了本文方法的有效性.There are two main deficiencies on clustering of dynamic graphs. Firstly, most of existing classical algorithms analyze such graphs from the perspective of static analysis. However, static analysis is not capable of modeling the continuous evolution of real-world networks. Therefore, it is a great need to research on clustering algorithms for dynamic graphs. Our goal is to capture the dynamic evolution characteristics by considering the clustering structure of multiple snapshots as a whole. Secondly, some clustering labels of some nodes in real-world graphs can be obtained in advance,thus how to integrate these priori information into clustering assignments of dynamic graphs and assign clustering labels to the unlabeled nodes of each snapshot should be resolved. In this paper, we propose an evolution factor graph model(EFGM) for the semi-supervised clustering of nodes in dynamic networks. EFGM is able to capture the node-attribute and edge-adjacency attribute of each node of the dynamic graphs, and also make full use of the snapshot information. We experiment with the real-world graphs and experimental results show that the EFGM integrates the prior knowledge and the dynamic graph into a unified framework(i. e., evolution factor graph model), which makes the clustering result satisfy the prior label information and conform to the overall evolution of dynamic graphs. It validates the effectiveness of the proposed approach.

关 键 词：半监督聚类 进化因子图模型 特征提取 动态图 

分 类 号：O157.5[理学—数学]