计算机应用

作者：曹春泽, 马德龙, 袁野

单位：1.东北大学 计算机科学与工程学院, 沈阳 110169；2.北京理工大学 计算机学院, 北京 100081

关键词：跨域,图流,三角计数,近似计算,采样

基金：国家自然科学基金资助项目(61932004)

现有的分布式三角计数算法假设所有计算节点位于同一地理位置，然而现实中它们可能位于跨洲际的多个数据中心中。跨域分布的数据中心使用广域网连接，具有网络带宽异质、通信费用高昂、分布不均等特点，而现有分布式算法无法适用于跨域环境。同时，现有研究较多采用随机采样、淘汰边等策略，忽略了三角形的形成具有时间局部性的特点。因此，研究了跨域环境中真实图流的三角计数问题并提出跨域三角计数（GTC）算法。首先针对现有边分发策略导致数据传输量过高的问题，提出一种跨域边分发策略，以结合通信的时间收益和数据收益建立收益公式，并使用点对点通信代替广播边；然后对于点对点通信在跨域环境中导致的三角形重复计数问题，提出终边计算规则，以确保无重复计数；最后基于时间加权采样算法提出时间加权三角计数算法，以利用三角形的时间局部性特点采样。在5个图流上把GTC与CoCoS （Conditional Counting and Sampling）、Tri-Fly进行对比的结果表明：GTC在通信数据量上比CoCoS减少了17%，比Tri-Fly减少了44%；在误差率上GTC比Tri-Fly减小了53%，略低于CoCoS；在算法运行时间上GTC比Tri-Fly减少了34%，略高于CoCoS。可见，GTC在保证较高准确率与较短算法运行时间的情况下，能有效减少通信数据量。

来源：2023年第7期

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

查看计算机应用杂志2023年第7期