Bursty subgraphs in social networks

Data available through social media and content sharing platforms present opportunities for analysis and mining. In the context of social networks, it is interesting to formalize and locate bursts of activities amongst users, related to a particular event and to report sets of socially connected users participating in such bursts. Such collections present new opportunities for understanding social events, and render new ways of online marketing.

In this paper, we model social information using two conceptualized graph models. The first one (the action graph) provides a detailed model of all activities of all users while the second one (the holistic graph) provides an aggregate view on each user in the social media. We also propose two models to define the notion of "burst". The first model (intrinsic burst model) takes the intrinsic characteristics of each user into account to recognize the bursty behaviors; while the second model (social burst model) considers neighbors' influences when identifying bursts. We provide two linear algorithms to detect bursts based on the proposed models. These algorithms have been extensively evaluated on a month of full Twitter dataset certifying the practicality of our approach. A detailed qualitative study of our techniques is also presented.