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

• 作者: 张建朋 王亚文 王凯 祝凯捷 陈鸿昶
• 来源期刊: 电子学报
• 学科: 工学
• 关键词: 大规模图 图采样 图聚类 整体推断 聚类代表点 扩张准则
• 年，卷（期）: 2019,（8）
• 所属期刊栏目: 学术论文
• 页码范围: 1731-1737
• 页数: 7页
• 分类号: TP181
• 字数: 5803字
• 语种: 中文
• DOI: 10.3969/j.issn.0372-2112.2019.08.017

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	陈鸿昶		61	354	10.0	16.0
2	王凯		15	34	4.0	5.0
3	王亚文		11	24	3.0	4.0