Seed selection for viral marketing in online social networks : from influence maximization to profit maximization

• Main Author: Tang, Jing
• Other Authors: Yuan Junsong
• Format: Theses and Dissertations
• Language: English
• Published: 2017
• Subjects: DRNTU::Business::Marketing
• Online Access: http://hdl.handle.net/10356/72857
• Institution: Nanyang Technological University

Online Social Networks (OSNs) attract billions of users. Information can be disseminated widely and rapidly through OSNs with "word-of-mouth" effects. Viral marketing is such a typical application in which new products or commercial activities are advertised by some seed users in OSNs to other users in a cascading manner. A large amount of recent work has been focusing on viral marketing in OSNs. In this thesis, three seed selection problems in viral marketing are investigated. We start from the classical influence maximization. Then, we look at profit maximization for advertisers and OSN providers respectively that naturally combines the benefit with the cost of viral marketing. Recent research has adopted the sampling approach to achieve a (1-1/e-ε)-approximation guarantee for influence maximization. One fundamental step of this approach is to examine the approximation assurance of the seed set constructed under a given number of samples generated. We focus on this essential step and propose a framework to Maximize the online Approximation Guarantee (MAG). Our framework exploits instance-specific information during execution to construct online bounds that can potentially break the conventional approximation limit of (1-1/e). The applications of MAG are two-fold. First, MAG can provide online approximation guarantees for runtime-restricted influence maximization in which only a limited amount of execution time is allowed to generate samples for influence estimation. Second, by deriving a better online approximation guarantee, MAG can be used to save the running time needed to reach an approximation target for traditional influence maximization. The selection of initial seed users yields a tradeoff between the expense and reward of viral marketing. We define a profit metric that combines the benefit of influence spread with the cost of seed selection in viral marketing. We carry out a comprehensive study on finding a set of seed nodes to maximize the profit of viral marketing. We show that the profit metric is significantly different from the influence metric in that it is no longer monotone. This characteristic differentiates the profit maximization problem from the traditional influence maximization problem. We develop new seed selection algorithms for profit maximization with strong approximation guarantees. We also derive several upper bounds to benchmark the practical performance of an algorithm on any specific problem instance. An OSN provider is often hired by an advertiser to conduct viral marketing campaigns. The OSN provider generates revenue from the commission paid by the advertiser which is determined by the spread of its product information. Meanwhile, to propagate influence, the activities performed by users such as viewing video ads normally induce diffusion cost to the OSN provider. We attempt to find a seed set to optimize a new profit metric that combines the benefit of influence spread with the cost of influence propagation for the OSN provider. Under many diffusion models, such a profit metric is the difference between two submodular functions which is challenging to optimize as it is neither submodular nor monotone. We design a general two-phase framework to select seeds for profit maximization and develop several bounds to measure the quality of the seed set constructed. Extensive experimental evaluations with real OSN datasets demonstrate the effectiveness of our algorithms and techniques.