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

论文摘要

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

论文目录

• 1 引言
• 2 基于采样的大规模图数据聚类算法
•   2.1 相关概念及定义
•   2.2 聚类结构保持的采样算法
•     2.2.1 初始化聚类代表点
•     2.2.2 内部顶点优先的采样扩张
•   2.3 整体聚类推断算法
•   2.4 聚类算法整体描述
• 3 大规模网络数据集实验分析
•   3.1 实验数据
•     3.1.1 人工合成图
•     3.1.2 真实网络图
•   3.2 聚类评价指标
•   3.3 人工网络图上的聚类结果和分析
•   3.4 真实网络图上的聚类结果和分析
• 4 总结

文章来源

类型: 期刊论文

作者: 张建朋,陈鸿昶,王凯,祝凯捷,王亚文

关键词: 大规模图,图采样,图聚类,整体推断,聚类代表点,扩张准则

来源: 电子学报 2019年08期

年度: 2019

分类: 信息科技,基础科学

专业: 数学,计算机软件及计算机应用

单位: 国家数字交换系统工程技术研究中心,荷兰埃因霍温理工大学计算机系

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

分类号: TP311.13;O157.5

页码: 1731-1737

总页数: 7

文件大小: 1001K

下载量: 167