Research on Periodic Triangle Enumeration Algorithm for Temporal Graphs

Abstract

Real-world graphs are usually temporal graphs, and their edges are associated with timestamps. With the development of algorithms on graph data mining and the increase of needs in real-world, data mining algorithms for temporal graphs have started to become a hot topic. Periodicity is a very important feature in temporal data. Patterns that occur periodically in real world usually indicate important features. In data mining algorithms for static graphs, triangle enumeration is a fundamental and important problem. In this paper, a new triangle model is proposed based on the temporal graph, the periodic triangle. In this paper, periodic data mining is combined with triangle enumeration algorithms in graphs, and an efficient algorithm for periodic triangle enumeration in temporal graphs is proposed. This algorithm contains three components: the first one is an efficient multi-level pruning algorithm which can delete vertices and edges which are not in any periodic triangle at low cost; the second one is a maximal periodic enumeration algorithm that can avoid enumeration on overlapping communities in time axis; the third one is an efficient periodic triangle enumeration algorithm that prunes unnecessary vertices and edges while enumeration. Experiments show that the algorithm proposed in this paper can enumerate periodic triangles in graphs efficiently.

Keywords

• temporal graph; periodicity; triangle enumeration