Budget-Efficient Viral Video Distribution Over Online Social Networks: Mining Topic-Aware Influential Users

Marketing over online social networks (OSNs) has become an essential tool for spreading product information in a "word of mouth" way. In particular, campaigns normally adopt a pragmatic approach of seeding videos with a selected list of influential users, hoping to create a viral distribution to reach as many users as possible. In this paper, we propose a multitopicaware influence maximization framework to identify a fixed number of influential users and assign video clips of specific topics to them, with an ultimate objective to maximize the number of message deliveries, defined as expected posting number (EPN). We first prove the submodularity of the EPN function, resulting in a general greedy algorithm with a performance bound of 1 - 1/e. We further develop two faster algorithms to accelerate the computing speed for large-scale social networks. The first algorithm leverages two estimation methods to compute the upper bound for marginal EPN without a loss of accuracy. The second algorithm generates an approximation solution based on the upper bound and lower bound estimation, with a performance bound of epsilon(1 - 1/e). We have implemented a prototype system based on a private data center at the Nanyang Technological University campus in Singapore to enable video clip extraction and sharing among social users. Furthermore, we conduct experiments on four real large-scale social networks (with different scales and structures) and the results show that the proposed methods are much faster than previous algorithms but with high accuracy.