面向时序图数据的快速环枚举算法
作者:
作者单位:

作者简介:

潘敏佳(1996-),女,硕士,CCF学生会员,主要研究领域为图数据挖掘.
李荣华(1985-),男,博士,副教授,博士生导师,CCF专业会员,主要研究领域为图数据管理,图数据挖掘,社交网络分析,图机器学习,图计算系统.
赵宇海(1975-),男,博士,教授,博士生导师,CCF高级会员,主要研究领域为数据库,数据挖掘,机器学习,软件工程,生物信息学.
王国仁(1966-),男,博士,教授,博士生导师,CCF杰出会员,主要研究领域为不确定数据管理,数据密集型计算,可视媒体数据管理与分析,非结构化数据管理,分布式查询处理与优化技术(主要包括传感器网络和P2P对等计算),生物信息学.

通讯作者:

李荣华,Email:lironghuabit@126.com

中图分类号:

基金项目:

国家自然科学基金(61772346,U1809206,61772124,61332006,61332014,61328202,U1401256)


Fast Temporal Cycle Enumeration Algorithm on Temporal Graphs
Author:
Affiliation:

Fund Project:

National Natural Science Foundation of China (61772346, U1809206, 61772124, 61332006, 61332014, 61328202, U1401256)

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

    时序图数据是一类边上带有时间戳信息的图数据.在时序图数据中,时序环是边满足时间戳递增约束的回路.时序环枚举在现实中有着很多应用,它可以帮助挖掘金融网络中的欺诈行为.此外,研究时序环的数量对于刻画不同时序图的特性也有重要作用.基于2018年由Rohit Kumar等人提出的时序环枚举算法(2SCENT算法),提出一种通过添加环路信息来削减搜索空间的新型时序环枚举算法.所提出的算法为一个两阶段的算法:1)首先,通过遍历原图获得所有可能会形成环路的节点,以及相应的时间和长度信息;2)然后,利用以上信息进行动态深度优先搜索,挖掘所有的满足约束条件的环.在4个不同的真实时序图数据集上进行了大规模的实验,并以2SCENT算法作为基准对算法进行了对比.实验结果表明,所提出的算法较之前最好的2SCENT算法要快50%以上.

    Abstract:

    Temporal graph is a type of graph where each edge is associated with a timestamp. In temporal graphs, a temporal cycle denotes a loop where the timestamps of the edges in the loop follow an increasing order. Temporal cycle enumeration has a number of real-life applications. For example, it can be applied to detect the fraud behavior in temporal financial networks. Additionally, the number of temporal cycles can be used to characterize the topological properties of temporal graphs. Based on the 2SCENT algorithm proposed by Rohit Kumar et al. in 2018, a new temporal cycle enumeration algorithm is proposed which uses additional cycle information to prune the search space. Specifically, the proposed algorithm is a two-stage algorithm. First, the algorithm traverses the temporal graph to identify all root nodes that probably form temporal cycles, as well as the corresponding time and length information of the cycles. Second, the algorithm performs a dynamic depth first search using the above information to find all valid temporal cycles. Extensive experiments are conducted on four real-life datasets, using 2SCENT as the baseline algorithm. The result shows that the proposed algorithm reduces the running time over the 2SCENT algorithm by 50 percent.

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

潘敏佳,李荣华,赵宇海,王国仁.面向时序图数据的快速环枚举算法.软件学报,2020,31(12):3823-3835

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

京公网安备 11040202500063号