基于采样的大规模图聚类分析算法

作     者：张建朋 陈鸿昶 王凯 祝凯捷 王亚文 ZHANG Jian-peng;CHEN Hong-chang;WANG Kai;ZHU Kai-jie;WANG Ya-wen

作者机构：国家数字交换系统工程技术研究中心河南郑州450000 荷兰埃因霍温理工大学计算机系荷兰北布拉邦省5600MB 

出 版 物：《电子学报》 (Acta Electronica Sinica)

年 卷 期：2019年第47卷第8期

页      面：1731-1737页

核心收录：

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 081104[工学-模式识别与智能系统] 08[工学] 0835[工学-软件工程] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

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

主　　题：大规模图 图采样 图聚类 整体推断 聚类代表点 扩张准则 

摘      要：针对当前聚类方法(例如经典的GN算法)计算复杂度过高、难以适用于大规模图的聚类问题,本文首先对大规模图的采样算法展开研究,提出了能够有效保持原始图聚类结构的图采样算法(Clustering-structure Representative Sampling,CRS),它能在采样图中产生高质量的聚类代表点,并根据相应的扩张准则进行采样扩张.此采样算法能够很好地保持原始图的内在聚类结构.其次,提出快速的整体样本聚类推断(Population Clustering Inference,PCI)算法,它利用采样子图的聚类标签对整体图的聚类结构进行推断.实验结果表明本文算法对大规模图数据具有较高的聚类质量和处理效率,能够很好地完成大规模图的聚类任务.