DYTC:Dynamic Graph Triangle Counting on GPU

Triangle counting is a critical problem in graph theory and network analysis, with widespread applications in social network analysis, network science, and bioinformatics. Dynamic graphs are extensively utilized in various domains and are prevalent in real-world scenarios. Over time, dynamic graphs necessitate frequent updates, where vertices and edges are inserted, deleted, or modified. However, existing dynamic graph analysis methods often focus solely on the data structure of dynamic graphs, neglecting the algorithms for dynamic graph processing. Current triangle counting methods are typically designed for static graphs and are not suited for continuously updated dynamic graphs. In this paper, we propose an incremental triangle counting algorithm tailored for dynamic graphs, which only requires recomputing the affected subgraph caused by updated edges, rather than the entire graph. Consequently, in comparison to the previous algorithm, our algorithm is capable of attaining a maximum speedup of \(7993 \times\).