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

Clc Number:

Fund Project:

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

  • Article
  • |
  • Figures
  • |
  • Metrics
  • |
  • Reference
  • |
  • Related
  • |
  • Cited by
  • |
  • Materials
  • |
  • Comments
    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.

    Reference
    Related
    Cited by
Get Citation

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

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:July 18,2019
  • Revised:September 10,2019
  • Adopted:
  • Online: December 03,2020
  • Published: December 06,2020
You are the firstVisitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063