Research On Cycle Detection Algorithm In Temporal Network

Many problems in people’s daily production and life can be described by the network model.Using graph theory and complex network algorithms to mine the structural characteristics of the network and analyze the internal relationship of nodes has become an effective way of analysis.A temporal network is a kind of network with time scale characteristics,and its structure evolves with the change of time.It is of great practical significance to find the network structure information of cycles in temporal networks.For example,in the e-commerce trading network,the cycle can indicate the possible existence of malicious billbrushing behavior;in the financial trading network,mining the cycle is helpful to find the money laundering behavior of gangs.In this paper,we discuss the problem of cycle detection in temporal networks,design a data preprocessing technology based on the strongly connected component algorithm of graph algebra,and propose two improved cycle detection algorithms based on queue search and multiple breadth-first search(BFS),aiming at reducing the invalid access of edges in the process of cycle retrieval and improving the efficiency of cycle detection.The innovation of this paper mainly includes the following two aspects:(1)In a directed graph,since the cycles only exist in the strongly connected component of the graph,using the relationship between the strongly connected component and the breadthfirst search,this paper proposes a strongly connected component algorithm of graph algebra that combines the BFS with matrix algebra operation to preprocess the graph data.Starting from the initial node,we extract the breadth-first search information of the node from the adjacency matrix A of the forward graph and the adjacency matrix AT of the reverse graph at the same time,and after the two parts of information are summarized,we obtain the strongly connected compoent of the graph.Theoretically speaking,the time complexity of the algorithm is O(n2),but in actual practice it can be O(n+m),where n is the number of the nodes and m is the number of the edges.Compared with the algorithms of Tarjan and Kosaraju,the average performance improvement of our algorithm is about 76%.(2)In the constrained search of temporal cycles,we propose a queue-based search algorithm,which combines the ideas of depth-first search(DFS)with BFS.When searching the feasible path between two points,we take the initial point as the root node and use BFS to expand the search direction,and the DFS to expand the search depth until all the cycles meeting the conditions are output.In this way,our algorithm not only reduces the number of backtracking steps and saves time but also retains the missing side information.Then,based on the queue algorithm,a parallel search method is proposed,which is a cycle detection algorithm based on a multi-layer BFS.The algorithm is implemented on the forward graph G and the reverse graph GT simultaneously.Starting from the same initial point,we execute three layers of BFS on the forward graph according to the requirement of increasing time,and(1,2,3,…,L-3)layers of BFS with decreasing time on the reverse graph in turn.When the tail nodes of the obtained paths are consistent,a cycle with a length not exceeding L is output.The computational complexity of our algorithm is O(cdL),where d is the average degree of the graph,L is the length of the cycle,and c is the number of the cycles.Compared with the benchmark algorithm,our algorithm not only directly outputs the timing cycle of destination lengths but also improves the performance by 134 times.