Tracking Triadic Cardinality Distributions for Burst Detection in High-Speed Multigraph Streams

In everyday life, we often observe unusually frequent interactions among people before or during important events, e.g., people send/receive more greetings to/from their friends on holidays than regular days. We also observe that some videos or hashtags suddenly go viral through people's sharin...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2017-08
Main Authors: Zhao, Junzhou, Wang, Pinghui, Lui, John C S, Towsley, Don, Guan, Xiaohong
Format: Article
Language:English
Subjects:
Bursts
Empirical analysis
Immunization
Maximum likelihood estimates
Sampling methods
Social networks
Spamming
Tracking
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In everyday life, we often observe unusually frequent interactions among people before or during important events, e.g., people send/receive more greetings to/from their friends on holidays than regular days. We also observe that some videos or hashtags suddenly go viral through people's sharing on online social networks (OSNs). Do these seemingly different phenomena share a common structure? All these phenomena are associated with sudden surges of user interactions 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 some properly defined networks. This finding motivates us to propose a new and robust method to detect bursts on 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, in a network. We show 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 more reliably detect bursts than simply counting interactions on OSNs. To avoid handling massive activity data generated by OSN users during the triadic tracking, we design an efficient "sample-estimate" framework to provide maximum likelihood estimate on the triadic cardinality distribution. We propose several sampling methods, and provide insights about their performance difference, through both theoretical analysis and empirical experiments on real world networks.
ISSN:2331-8422