高精度滑动窗口模型下的图流三角形近似计数算法
CSTR:
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

TP391

基金项目:

国家自然科学基金(61932001, U20A20174); 香港研资局优配研究金 (14205520)


Approximate Streaming Graph Triangle Counting Algorithm Based on Sliding Window Model with High Accuracy
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    近年来, 图流分析在研究领域和工业领域都变得愈发重要. 图流是从数据源持续高速到达的边序列, 这些边组成了一个不断变化的动态图. 在图流上可以进行多种不同的分析, 而三角形计数是其中最基础的操作之一. 由于图流数据规模大, 更新速度高, 在图流上进行精确三角形计数效率较低, 而且并不必要. 因为大部分三角形计数应用都允许一定的误差, 所以, 图流上的近似三角形计数一直都是研究热点之一. 研究基于采样的滑动窗口模型下的图流近似三角形计数. 滑动窗口模型只关注最近到达的图流数据, 较早的图流数据被认定为过期. 它被广泛应用于不同的工业场景和研究工作中. 将一种“采样前计数”的方法与该问题场景下最新的算法结合, 并提出一套策略以应对由于边过期产生的困难. 使用真实数据集展开广泛的实验以测试提出的CBS算法. 实验结果表明, CBS相比目前最好的工作, 估算误差降低了70%以上.

    Abstract:

    In recent years, streaming graph analysis has gained increasing importance in both research and industry. A streaming graph is a continuous sequence of edges received from a data source at a high speed. Those edges form a dynamic graph that is continuously changing. Various analyses can be performed on streaming graphs. Among them, triangle counting is one of the most basic operations. However, the large volume and high update speed of streaming graphs make it inefficient to count triangles accurately on them. It is also unnecessary, as most applications for triangle counting can tolerate small errors. Therefore, approximate triangle counting in streaming graphs has been a hot research topic. This study focuses on sample-based approximate triangle counting in streaming graphs with a sliding window model. Sliding window models focus on the most recent edges in a streaming graph and consider older edges as expired. They are widely applied in various industrial scenarios and research. This study combines a count-before-sample strategy with the state-of-the-art approximate triangle counting algorithm and designs a set of novel strategies to deal with the difficulty brought by edge expiration. Extensive experiments are conducted on real-world datasets to evaluate the proposed algorithm. Results prove that the algorithm decreases the estimation error of the state-of-the-art method by more than 70%.

    参考文献
    相似文献
    引证文献
引用本文

苟向阳,邹磊,于旭.高精度滑动窗口模型下的图流三角形近似计数算法.软件学报,,():1-24

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2024-01-30
  • 最后修改日期:2024-05-05
  • 录用日期:
  • 在线发布日期: 2024-12-31
  • 出版日期:
文章二维码
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号