Abstract: Triangle Counting,calculating global and local triangle counts,is an important work in data mining,whose number is widely used in important role identification,recommendation systems,community discovery,spam and fraud detection etc.In the graphs presented as a stream of edges,edges are temporal,and there are a large of duplicate edges in real-world graphs.For full use of the time information in the graph and mining the network knowledge,this work studied the problem of estimating global and local triangle counts on a multigraph stream with sliding windows,that simultaneously studied multiple windows by window mechanism to obtain more information in implicit time relationships.A triangle counting algorithm based on FLINK window ope-ration and a triangle increment counting algorithm based on sliding window are proposed.Like the existing edge sampling work,the edge set is used to store window history data for accurately calculating global and local triangle counts on a multigraph stream with sliding windows in one-pass.The triangle counting algorithm based on FLINK window operator uses the window mechanism provided by FLINK.While the triangle increment counting algorithm based on sliding window realizes window counting by calculating slide-in and slide-out data through the window,reducing a large number of repeated calculations of coincident edges between adjacent windows,seamlessly processing multiple time windows,and for duplicate data in slide-in and slide-out,uses a deduplication mechanism to further reduce the calculation.The theory has been proven that both the algorithms can accurately count the triangles in the sliding window,and the effects of window size,sliding distance,data distribution and data flow rate on window processing time were analyzed through experiments.Compared with the TRIEST algorithm,when the window is small,the triangle counting algorithm based on FLINK window operation and the triangle increment counting algorithm based on sliding window have faster speed.When the window is large,the accuracy of the calculation result is guaranteed.

Key words: Accurate stream algorithm, FLINK, Graph stream mining, Sliding window, Triangle counting