Simple Cycle Enumeration Based On Temporal Graph

The rapid development of network and computer technology has enabled data and information to flow and propagate faster on a global scale,resulting in increasingly large temporal graphs formed by more frequently interactions among users.Therefore,there is a higher demand for algorithms to find cycles in temporal graphs.The problem of enumerating simple cycles in temporal graphs is a fundamental and important problem in graph theory,and it plays an important role in studying community development and anti-money laundering in the financial industry.In this paper,we analyze the advantages of algorithms that solve related problems by studying previous algorithms for solving this problem,and explore the possibility of transplanting them to this problem.We also explore how to use the characteristics of temporal graphs to solve problems in temporal graphs,and point out the pain points of previous algorithms for solving this problem.Based on the idea of pruning,this paper mainly uses an edge candidate set indexing structure to solve the "temporal" problem,and prunes the enumeration process through an algorithm that determines the reachability of the source in reverse.By applying these two methods,we can efficiently solve the problem.The biggest difference between a temporal graph and a regular directed graph is that each edge in the temporal graph has a timestamp,which means that there may be more interactions between two different source points,resulting in more edges.Therefore,removing invalid edges is crucial to improve the efficiency of the algorithm.How to use the temporal property for studying the characteristics of temporal graphs is also a major issue in studying temporal graphs,and utilizing this feature can bring breakthrough progress to solving the problem.This paper proposes the concept of edge-based algorithm research,and establishes a forward and reverse candidate set index for edges within a certain time complexity constraint to fix the neighbor relationship between edges and obtain the forward and reverse neighbor sets based on edges that meet the temporal requirements.This approach avoids redundant and meaningless temporal condition judgments during the enumeration process.Most of the previous methods for solving this problem were based on depth-first search,and how to prune the depth-first search method is also a key factor in improving the efficiency of the algorithm.Inspired by the algorithm for solving the s-t simple path enumeration problem,this paper proposes a reverse calculation algorithm for determining the reachability of the source point of an edge.Prior to enumeration,a modified breadth-first search method is used to determine the reachability of the source points of each edge based on whether the edge is likely to form a correct result,which provides a powerful pruning ability for the enumeration process.The overall time complexity of the algorithm is constrained to be related to the number of results,providing theoretical guarantees for efficient solution of the problem.Experimental comparisons were performed on six temporal graph datasets from the real world,and the results demonstrate the excellent performance of the algorithm in solving the simple cycle enumeration problem under temporal graphs.In addition,based on the excellent performance of the proposed algorithm,this paper conducted statistical analysis of the number of cycles of different lengths in different time windows on different datasets,and made analysis based on this.