Tracking Influencers in Decaying Social Activity Streams With Theoretical Guarantees

Influence maximization (IM) is the fundamental problem in many real world applications such as viral marketing, political campaign, and network monitoring. Although extensively studied, most studies on IM assume that social influence is static and they cannot handle the dynamic influence challenge in reality, i.e., a user’s influence is varying over time. To address this challenge, we formulate a novel influencer tracking problem over a social activity stream. In order to keep the solutions up-to-date and forget outdated data in the stream smoothly, we propose a probabilistic-decaying social activity stream (PDSAS) model that enforces each social activity in the stream participating in the analysis with a probability decaying over time. Built on the PDSAS model, we propose a family of streaming optimization algorithms to solve the influencer tracking problem. SIEVE PAIT can identify influencers from a special kind of probabilistic addition-only social activity streams with high efficiency, and guarantees an$(1/2-\epsilon)$approximation ratio. BASIC IT leverages SIEVE PAIT as a building block to identify influencers from general PDSASs, and also guarantees an$(1/2-\epsilon)$approximation ratio. HIST IT improves the efficiency of BASIC IT, and still guarantees an$(1/4-\epsilon)$approximation ratio. Experiments on real data show that our methods can find high quality solutions with much less computational costs than baselines.