Sorry, you need to enable JavaScript to visit this website.

Streaming Influence Maximization in Social Networks based on Multi-Action Credit Distribution

Citation Author(s):
Qilian Yu, Hang Li, Yun Liao, Shuguang Cui
Submitted by:
Qilian Yu
Last updated:
12 April 2018 - 4:47pm
Document Type:
Poster
Document Year:
2018
Event:
Presenters:
Qilian Yu
Paper Code:
1213
Categories:
 

In a social network, influence maximization is the problem of identifying a set of users that own the maximum influence ability across the network. In this paper, a novel credit distribution (CD) based model, termed as the multi-action CD (mCD) model, is introduced to quantify the influence ability of each user. Compared to existing models, the new model can work with practical datasets where one type of action is recorded for multiple times. Based on this model, influence maximization is formulated as a submodular maximization problem under a knapsack constraint, which is NP-hard. An efficient streaming algorithm is developed to achieve (1/3-epsilon) approximation of the optimality. Experiments conducted on real Twitter dataset demonstrate that the mCD model enjoys high accuracy compared to the conventional CD model in estimating the total number of people who get influenced in a social network. Furthermore, compared to the greedy algorithm, the proposed single-pass streaming algorithm achieves similar performance in terms of influence maximization, while running several orders of magnitude faster.

up
0 users have voted: