Tracking Top-k Influential Users with Relative Errors

Tracking influential users in a dynamic social network is a fundamental step in fruitful applications, such as social recommendation, network topology optimization, and blocking rumour spreading. The major obstacle in mining top influential users is that estimating users' influence spreads is #P-hard under most influence propagation models. Previous studies along this line either seek heuristic solutions or may return meaningless results due to the lack of prior knowledge about users' influence in the dynamic network. In this paper, we tackle the problem of tracking top-k influential individuals in a dynamic social network. When a top-k query is issued, our algorithm returns a set S of more than k users. With high probability, our algorithm guarantees that S contains all real top-k influential users and there exists a relative error epsilon < 1 such that the least influential user in S has influence at least (1 - kappa)I-k, where I-k is the influence of the k-th most influential user and we can adjust epsilon via parameter settings. Controlling such a relative error enables us to obtain meaningful results even when we know nothing about the value of I-k or I-k changes over time in the dynamic network. In addition to the thorough theoretical results, our experimental results on large real networks clearly demonstrate the effectiveness and efficiency of our algorithm.