软件学报

作者：翁同峰，周旭，李肯立，胡逸騉

单位：翁同峰，湖南大学 信息科学与工程学院, 湖南 长沙 410082;School of Computing, National University of Singapore, Singapore 117417, Singapore11,周旭，湖南大学 信息科学与工程学院, 湖南 长沙 410082;国家超级计算长沙中心, 湖南 长沙 41008202,李肯立，湖南大学 信息科学与工程学院, 湖南 长沙 410082;国家超级计算长沙中心, 湖南 长沙 41008203,胡逸騉，湖南大学 信息科学与工程学院, 湖南 长沙 410082;国家超级计算长沙中心, 湖南 长沙 41008204

关键词：大规模图;分布式算法;核分解;图计算

基金：国家自然科学基金(62172146, 62102143); 湖南省自然科学基金(2023JJ10016, 2022JJ30009, 2023JJ30083); 湖南省教育厅科学研究重点项目(22A0592)

随着互联网信息技术的发展, 社交网络、计算机网络及生物信息网络等领域涌现海量大规模图数据. 鉴于传统图数据管理技术在处理大规模图时存在存储及性能方面的局限, 大规模图的分布式处理技术已成为图数据库领域的研究热点, 并得到工业界和学术界的广泛关注. 图的核分解用于计算图中所有顶点的核值, 有助于挖掘重要图结构信息, 在社区搜索、蛋白质结构分析和网络结构可视化等诸多应用中发挥着关键作用. 当前以顶点为中心计算模式的分布式核分解算法中采用一种广播的消息传递机制, 一方面, 存在大量的冗余通信及计算开销; 另一方面, 处理大规模图核分解过程中易产生内存溢出问题. 为此, 分别提出基于全局激活和层次剥离计算框架, 并提出分布式核分解新算法, 通过引入基于顶点核值局部性特点的消息剪枝策略和以计算节点为中心的计算新模式, 保证算法有效性的同时提升其性能. 在国家超级计算长沙中心分布式集群上, 分别针对大规模真实和合成数据集, 算法总耗时性能提升比例为37%–98%, 验证所提模型和算法的有效性和高效性.

来源：2024年第12期

《软件学报》期刊编辑部

查看软件学报杂志2024年第12期