IEEE Transactions on Computational Social Systems · 2019 · 14 citations · 25 references
Social SciencesEconomicsMarketingCollective BehaviorOptimizationSocial InfluenceCombinatorial OptimizationGreedy AlgorithmsNetwork OptimizationProfit MaximizationSocial Network AnalysisSocial NetworksGreedy ApproximationGreedy HeuristicsHeuristicsPolynomial Time ComplexityPolynomial-time AlgorithmsProfit Maximization ModelsSubmodular MaximizationSubmodular Optimization
In the past decade, tremendous research effort has been devoted to viral marketing. Most existing works on seed selection in social networks do not take into account the scenario when a profit can be generated from group activities. Each activity has a profit that can be measured by the excitement of the participants. The excitement about one piece of information can vary significantly among different groups of people. Given a social network and a profit function, how can we select the seed users to maximize the expected total amount of profit? This problem is essentially different from the classic influence maximization problem, and existing approaches cannot be directly applied to solve the problem. In this paper, we study the problem of activity profit maximization in social networks. We first prove that the maximizing activity profit problem is nondeterministic polynomial time-hard and cannot be approximated within a constant factor by the simple greedy algorithm. Supermodular degree of a function measures the extent to which it violates submodularity. We design an algorithm that achieves an approximation ratio of (1/(Δ+ 2)) provided that the supermodular degree of the social graph is bounded with A. We then develop an exchange-based technique to further improve the quality of the solution. We also devise a randomized variation approach to overcome the computational burden of the proposed algorithms. Extensive experimental results on three real benchmark data sets demonstrate the efficacy and efficiency of our algorithms over several baseline heuristics.
25
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
Efficient influence maximization in social networks
Wei Chen, Yajun Wang, Siyu Yang · 2009 · 2.2K citations
The dynamics of viral marketing
Jure Leskovec, Lada A. Adamic, Bernardo A. Huberman · ACM Transactions on the Web · 2007 · 2.1K citations · Full text