Tracking triadic cardinality distributions for burst detection in social activity streams

In everyday life, we often observe unusually frequent interactions among people before or during important events, i.e., people receive/send more greetings from/to their friends on Christmas Day than regular days. We also observe that some videos suddenly go viral through people's sharing in online social networks (OSNs). Do these seemingly different phenomena share a common structure? All these phenomena are associated with sudden surges of user activities in networks, which we call "bursts" in this work. We uncover that the emergence of a burst is accompanied with the formation of triangles in networks. This finding motivates us to propose a new and robust method to detect bursts in OSNs. We first introduce a new measure, "triadic cardinality distribution", corresponding to the fractions of nodes with different numbers of triangles, i.e., triadic cardinalities, within a network. We demonstrate that this distribution not only changes when a burst occurs, but it also has a robustness property that it is immunized against common spamming social-bot attacks. Hence, by tracking triadic cardinality distributions, we can reliably detect bursts in OSNs. To avoid handling massive activity data generated by OSN users during the triadic tracking, we design an efficient "sample-estimate" solution to provide maximum likelihood estimate on the triadic cardinality distribution from sampled data. Extensive experiments conducted on real data demonstrate the usefulness of this triadic cardinality distribution and effectiveness of our sample-estimate solution.