Viral Marketing of Online Game by DS Decomposition In Social Networks



Journal Title

Journal ISSN

Volume Title


Elsevier B.V.


In social networks, the spread of influence has been studied extensively, but most efforts in existing literature are made on the product used by a single person. This paper attempts to address the product which is used by many persons such as the online game. When multiple people participate in one game, interaction between users is accompanied by browsing and clicking on advertisements, and operators can also earn certain advertising revenues. All these revenues are related to information interaction between people involved in one game. We use game profit to represent all of the revenues gained from players involved in one game and model the game profit maximization problem in social networks, which finds a seed set to maximize the game profit between players who are influenced to buy the game. We prove that the problem is NP-hard and the objective function is neither submodular nor supermodular. To solve it, we decompose it into the Difference between two Submodular functions (DS decomposition) and propose four heuristic algorithms. To address the complexity of computing objective function, we design a new sampling method based on reverse reachable set technology. Experiment results on real datasets show that our approaches perform well. ©2019 Elsevier B.V.


Due to copyright restrictions full text access from Treasures at UT Dallas is restricted to current UTD affiliates (use the provided Link to Article).


Profit--Internet games, Influence (Psychology)--Internet games, Social networks, Heuristic algorithms, Marketing, Advertising, Submodular functions, Internet games

This work is partly supported by the National Natural Science Foundation of China (NSFC No. 61672323), the Fundamental Research Funds of Shandong University (Grant No. 2017JC043), the Key Research and Development Program of Shandong Province (2017GGX10122, 2017GGX10142) and the Fundamental Research Funds for the Central Universities (Grant No. GK201703005).


©2019 Elsevier B.V.