IEEE Access · 2018 · 17 citations · 18 references
ComputingData ScienceData MiningRecommender SystemsSocial InfluenceInteger ProgrammingNetwork OptimizationSocial Network AnalysisKnapsack ApproximationKnapsack ProblemsSocial Influence ModelingSocial Network InfluenceSubmodular MaximizationSubmodular Optimization
In a social network, influence maximization is the problem of identifying a set of users that own the maximum <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">influence ability</i> across the network. In this paper, a novel credit distribution (CD)-based model, termed as the multiaction CD (mCD) model, is introduced to quantify the influence ability of each user, which works with practical datasets where one type of action could be recorded for multiple times. Based on this model, influence maximization is formulated as a submodular maximization problem under a general knapsack constraint, which is NP hard. An efficient streaming algorithm with one-round scan over the user set is developed to find a suboptimal solution. Specifically, we first solve a special case of knapsack constraints, i.e., a cardinality constraint, and show that the developed streaming algorithm can achieve ( <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$({1}/{2})-\epsilon $ </tex-math></inline-formula> ) approximation of the optimality. Furthermore, for the general knapsack case, we show that the modified streaming algorithm can achieve ( <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$({1}/{3})-\epsilon $ </tex-math></inline-formula> ) approximation of the optimality. Finally, experiments are conducted over real Twitter dataset and 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. Moreover, through the comparison to the conventional CD, non-CD models, and the mCD model with the greedy algorithm on the performance of the influence maximization problem, we show the effectiveness and efficiency of the proposed mCD model with the streaming algorithm.
18
Maximizing the spread of influence through a social network
David Kempe, Jon Kleinberg, Éva Tardos · 2003 · 7.3K citations
Mining the network value of customers
Pedro Domingos, Matt Richardson · 2001 · 2.9K citations
{SNAP Datasets}: {Stanford} Large Network Dataset Collection
Jure Leskovec, Andrej Krevl · 2014 · 2.8K citations
Cost-effective outbreak detection in networks
Jure Leskovec, Andreas Krause, Carlos Guestrin et al. · 2007 · 2.5K citations · Full text
Public Health, Environmental Sciences, Outbreak Detection +7