计算机应用研究

作者：姜丽丽,李叶飞,豆龙龙,陈智麒,钱柱中,

单位：1.江苏方天电力科技有限公司,南京210000；2.南京大学计算机科学与技术系,南京210023；

关键词：4-clique计数问题,概率化算法,图模式挖掘,大数据处理,近似算法,

基金：国家自然科学基金面上项目(61872175)；江苏省自然科学基金面上项目(BK20181252)；；

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

来源：2020年第12期

《计算机应用研究》期刊编辑部

查看计算机应用研究杂志2020年第12期