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)

  • Article
  • | |
  • Metrics
  • |
  • Reference [24]
  • |
  • Related
  • | | |
  • 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
    [1] Dong CY, Shin D, Joo S, Nam Y, Cho KH. Identification of feedback loops in neural networks based on multi-step granger causality. Bioinformatics, 2012,28(16):2146-2153.
    [2] Hoffmann F, Krasle D. Fraud detection using network analysis. 2015. EP Patent App. EP20,140,003,010.
    [3] Holme P, Saramäki J. Temporal networks. Physics Reports, 2012,519(3):97-125.
    [4] Wang YS, Yuan Y, Liu M. Survey of query processing and mining techniques over large temporal graph database. Journal of Computer Research and Development, 2018,55(9):1889-1902(in Chinese with English abstract).
    [5] Jiang ZH. Minging frequent evolution pattern on temporal network. Modern Computer, 2019,638(2):15-19(in Chinese with English abstract).
    [6] Wu AB, Yuan Y, Qiao BY, Wang YS, Ma YL, Wang GR. The influence maximization problem based on large-scale temporal graph. Chinese Journal of Computers, 2019:1-18(in Chinese with English abstract).
    [7] Kovanen L, Karsai M, Kaski K, Kertész J, Saramäki J. Temporal motifs in time-dependent networks. Journal of Statistical Mechanics:Theory and Experiment, 2011(11):P11005, 2011.
    [8] Paranjape A, Benson AR, Leskovec J. Motifs in temporal networks. In:Proc. of the 10th ACM Int'l Conf. on Web Search and Data Mining. ACM, 2017. 601-610.
    [9] Rao VVB, Murti VGK. Enumeration of all circuits of a graph. Proc. of the IEEE, 1969,57(4):700-701.
    [10] Ponstein J. Self-Avoiding paths and the adjacency matrix of a graph. SIAM Journal on Applied Mathematics, 1966,14(3):600-609.
    [11] Mateti P, Deo N. On algorithms for enumerating all circuits of a graph. SIAM Journal on Computing, 1976,5(1):90-99.
    [12] Tiernan JC. An efficient search algorithm to find the elementary circuits of a graph. Communications of the ACM, 1970,13(12):722-726.
    [13] Weinblatt H. A new search algorithm for finding the simple cycles of a finite directed graph. Journal of the ACM (JACM), 1972, 19(1):43-56.
    [14] Johnson DB. Finding all the elementary circuits of a directed graph. SIAM Journal on Computing, 1975,4(1):77-84.
    [15] Birmelé E, Ferreira R, Grossi R, et al. Optimal listing of cycles and st-paths in undirected graphs. In:Proc. of the 24th Annual ACM-SIAM Symp. on Discrete Algorithms. Society for Industrial and Applied Mathematics, 2013. 1884-1896.
    [16] Qiu X, Cen W, Qian Z, et al. Real-Time constrained cycle detection in large dynamic graphs. Proc. of the VLDB Endowment, 2018, 11(12):1876-1888.
    [17] Kumar R, Calders T. Finding simple temporal cycles in an interaction network. In:Proc. of the Workshop on Large-Scale Time Dependent Graphs (TD-LSG 2017), Co-Located with the European Conf. on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML PKDD 2017). Skopje, 2017. 3-6.
    [18] Kumar R, Calders T. 2SCENT:An efficient algorithm for enumerating all simple temporal cycles. Proc. of the VLDB Endowment, 2018,11(11):1441-1453.
    [19] Bloom BH. Space/Time trade-offs in hash coding with allowable errors. Communications of the ACM, 1970,13(7):422-426.
    [20] Leskovec J, Krevl A. SNAP datasets:Stanford large network dataset collection. 2014. https://snap.stanford.edu/data
    附中文参考文献:
    [4] 王一舒,袁野,刘萌.大规模时序图数据的查询处理与挖掘技术综述.计算机研究与发展,2018,55(9):1889-1902.
    [5] 蒋志恒.时序网络的频繁演化模式挖掘.现代计算机(专业版),2019,638(2):17-21.
    [6] 吴安彪,袁野,乔百友,王一舒,马玉亮,王国仁.大规模时序图影响力最大化的算法研究.计算机学报,2019:1-18.
    Related
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

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

Copy
Share
Article Metrics
  • Abstract:1444
  • PDF: 4278
  • HTML: 2221
  • Cited by: 0
History
  • Received:July 18,2019
  • Revised:September 10,2019
  • Online: December 03,2020
  • Published: December 06,2020
You are the first2033286Visitors
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