面向大数据的图模式挖掘概率算法

• 作者: 姜丽丽 李叶飞 豆龙龙 钱柱中 陈智麒
• 来源期刊: 计算机应用研究
• 关键词: 4-clique计数问题 概率化算法 图模式挖掘 大数据处理 近似算法
• 年，卷（期）: 2020,（12）
• 所属期刊栏目: 算法研究探讨
• 页码范围: 3545-3551
• 页数: 7页
• 分类号: TP316.4
• 语种: 中文
• DOI: 10.19734/j.issn.1001-3695.2019.09.0539

摘要

在当今大数据时代,MapReduce等大数据处理框架处理数据能力有限,其在处理有关图的数据时常常显得缓慢低效,典型如3-clique计数问题,故需要探究一种高效的算法处理这类clique计数问题.由于在前人文献中对3-clique计数问题已有深入探讨,故针对该问题的扩展版本(4-clique计数问题)进行探究.在一个启发式的想法下提出了基于邻边采样的概率采样算法,利用切诺夫不等式证明该算法在近似条件下只需要一定数量的采样器作为相对误差的性能保证.通过实验评估对比发现,相对于传统精确算法,概率采样算法虽然在结果上损失了少量的精度,但在算法运行时间和空间占用上具有巨大的优势.最后得出其在实际应用中具有巨大实践价值的结论.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	钱柱中		19	312	8.0	17.0
2	姜丽丽		1	0	0.0	0.0
3	李叶飞		3	2	1.0	1.0
4	豆龙龙		1	0	0.0	0.0
5	陈智麒		1	0	0.0	0.0