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.

Introduction

As online social networks (OSN) grow rapidly[1, 2, 3], the information diffusion and social influence get into people’s daily life deeply. Therefore, the influence-driven information technology and influence-based research subjects have been studied extensively in literatures. One of subjects is the viral marketing. In fact, advertisements in online social networks have gained better results than traditional medias sometimes, such as newspapers and televisions. Among existing works in viral marketing, most of efforts in the literature are made on products used by a single person[4, 5, 6]. In this paper, we consider the product which is used by many persons, i.e., a online game with many players. When multiple players participate in an online game, interaction behaviors between game players are always accompanied by browsing on advertisements showed on the game scene, which will lead to advertising revenue. The more frequent the interaction between players, the more times an advertisement is presented and viewed which means more revenues[7]. All these benefits or revenues are related to information interaction between people involved in one game. We use game profit to represent the revenues gained from game players mentioned above.