Discovering Frequency Bursting Patterns in Temporal Graphs

A frequency bursting pattern (FBP) in temporal graphs represents some interaction behavior that accumulates its frequency at the fastest rate. Mining FBPs is essential to early warning of emergencies. However, existing studies on frequency-based pattern mining in graphs do not consider the temporal information and bursting features of a subgraph pattern. As a result, they may not provide effective and efficient mining algorithms for FBP discovery. In this paper, we study the problem of discovering top-k FBPs in temporal graphs. We present a novel model, referred to as maximal (m, θ)-bursting pattern, to describe FBPs in a temporal graph, which is a subgraph with a size larger than m that accumulates its frequency at the fastest rate during a time interval of length no less than θ. A naive solution for top-k FBPs discovery is to use the best-first search algorithm, where the burstiness threshold changes as more patterns are mined. However, this method will result in huge search space since we need to check every possible time interval for a candidate pattern in the temporal graph. To tackle this problem, we devise an online top-k framework in which k candidate results are maintained from the initial timestamp to the end in the temporal graph. Under the new framework, we further conceive two optimization strategies by exploiting incremental subgraph matching and Evolutionary Game Theory to boost the performance. Extensive experiment results on five real temporal graphs show that our algorithm has higher efficiency, effectiveness and scalability.