面向大规模二部图的分布式Tip分解算法

来源：软件学报杂志2022年第3期北京时间：

作者：周旭，翁同峰，杨志邦，李博仁，张吉，李肯立

单位：周旭，湖南大学 信息科学与工程学院, 湖南 长沙 41008211,翁同峰，湖南大学 信息科学与工程学院, 湖南 长沙 41008202,杨志邦，湖南大学 信息科学与工程学院, 湖南 长沙 41008203,李博仁，湖南大学 信息科学与工程学院, 湖南 长沙 41008204,张吉，之江实验室, 浙江 杭州 31110005,李肯立，湖南大学 信息科学与工程学院, 湖南 长沙 410082;国家超级计算长沙中心, 湖南 长沙 41008206

摘要：Tip分解作为图数据管理领域的热点研究问题，已被广泛应用于文档聚类和垃圾邮件组检测等实际场景中.随着图数据规模的爆炸式增长，单机内存已无法满足其存储需求，亟需研究分布式环境下Tip分解技术.现有分布式图计算系统的通信模式无法适用于二部图，为此，首先提出一种基于中继的通信模式，以实现分布式环境下处理二部图时消息的有效传递；其次，提出分布式butterfly计数算法（DBC）和tip分解算法（DTD），特别地，为解决处理大规模二部图时DBC面临的内存溢出问题，提出了一种可控的并行顶点激活策略；最后，引入基于顶点优先级的消息剪枝策略和消息有效性剪枝策略，通过减少冗余通信和计算开销，进一步提高算法效率.实验平台部署于国家超算中心高性能分布式集群上，在多个真实数据集上的实验结果验证了所提算法的有效性和高效性.

关键词：二部图;butterfly计数;分布式系统;tip分解

基金资助：国家自然科学基金（61772182，61802032，69189338，62172146，62172157）；之江实验室开放课题（2021KD0AB02）；国防科技大学信息系统工程重点实验室基金