Mining Bursting Core in Large Temporal Graph

Download PDF

Abstract

Temporal graphs are ubiquitous. Mining communities that are bursting in a period of time is essential for seeking real emergency events in temporal graphs. Unfortunately, most previous studies on community mining in temporal networks ignore the bursting patterns of communities. In this paper, we study the problem of seeking bursting communities in a temporal graph. We propose a novel model, called the (𝑙,𝛿)-maximal bursting core, to represent a bursting community in a temporal graph. Specifically, an (𝑙,𝛿)-maximal bursting core is a temporal subgraph in which each node has an average degree no less than 𝛿 in a time segment with length no less than 𝑙 . To compute the (𝑙 , 𝛿 ) -maximal bursting core, we first develop a novel dynamic programming algorithm that can reduce timecomplexityofcalculatingthesegmentdensityfrom𝑂(|T|)2 to𝑂(|T|).Then,weproposeanefficientupdatingalgorithmwhich can update the segment density in 𝑂 (𝑙 ) time. In addition, we develop anefficientalgorithmtoenumerateall(𝑙,𝛿)-maximalburstingcores that are not dominated by the others in terms of 𝑙 and 𝛿 . The results of extensive experiments on 9 real-life datasets demonstrate the effectiveness, efficiency and scalability of our algorithms.