"Viral Marketing"
334978
Stop and Stare: Optimal Sampling Algorithms for Viral Marketing in Billion scale Networks
Influence Maximization (IM) that seeks a small set of key users who spread the influence widely into the network, is a core problem in multiple domains. It finds applications in viral marketing, epidemic control, and assessing cascading failures within complex systems. Despite the huge amount of effort, IM in billion scale networks such as Facebook, Twitter, and World Wide Web has not been satisfactorily solved. Even the state of the art methods such as TIM+ and IMM may take days on those networks. In this paper, we propose SSA and D SSA, two novel sampling frameworks for IM based viral marketing problems. SSA and D SSA are up to 1200 times faster than the SIGMOD'15 best method, IMM, while providing the same (1 1/e e) approximation guarantee. Underlying our frameworks is an innovative Stop and Stare strategy in which they stop at exponential check points to verify (stare) if there is adequate statistical evidence on the solution quality. Theoretically, we prove that SSA and D SSA are the first approximation algorithms that use (asymptotically) minimum numbers of samples, meeting strict theoretical thresholds characterized for IM. The absolute superiority of SSA and D SSA are confirmed through extensive experiments on real network data for IM and another topic aware viral marketing problem, named TVM.
SIGMOD Conference
Hung T Nguyen My T Thai Thang N Dinh
15372703
Cost aware Targeted Viral Marketing in billion scale networks
Online social networks have been one of the most effective platforms for marketing and advertising. Through the "world of mouth" exchanges, so called viral marketing, the influence and product adoption can spread from few key influencers to billions of users in the network. To identify those key influencers, a great amount of work has been devoted for the Influence Maximization (IM) problem that seeks a set of k seed users that maximize the expected influence. Unfortunately, IM encloses two impractical assumptions: 1) any seed user can be acquired with the same cost and 2) all users are equally interested in the advertisement. In this paper, we propose a new problem, called Cost aware Targeted Viral Marketing (CTVM) to find the most cost effective seed users who can influence the most relevant users to the advertisement. Since CTVM is NP hard, we design an efficient (1 1/e e) approximation algorithm, named BCT, to solve the problem in billion scale networks. Comparing with IM algorithms, we show that BCT is both theoretically and experimentally faster than the state of the arts while providing better solution quality. Moreover, we prove that under the Linear Threshold model, BCT is the first sub linear time algorithm for CTVM (and IM) in dense networks. In our experiments with a Twitter dataset, containing 1.46 billions of social relations and 106 millions tweets, BCT can identify key influencers in each trending topic in only few minutes.
IEEE INFOCOM 2016 The 35th Annual IEEE International Conference on Computer Communications
Hung T Nguyen Thang N Dinh My T Thai
9206191
A Billion Scale Approximation Algorithm for Maximizing Benefit in Viral Marketing
Online social networks have been one of the most effective platforms for marketing and advertising. Through the "world of mouth" exchanges, so called viral marketing, the influence and product adoption can spread from few key influencers to billions of users in the network. To identify those key influencers, a great amount of work has been devoted for the influence maximization <italic>IM</italic> problem that seeks a set of <inline formula> <tex math notation="LaTeX"$k$ /tex math>/inline formula> seed users that maximize the expected influence. Unfortunately, <italic>IM</italic> encloses two impractical assumptions: 1) any seed user can be acquired with the same cost and 2) all users are equally interested in the advertisement. In this paper, we propose a new problem, called <italic>cost aware targeted viral marketing</italic> <italic>CTVM</italic> to find the most cost effective seed users, who can influence the most relevant users to the advertisement. Since <italic>CTVM</italic> is NP hard, we design an efficient <inline formula> <tex math notation="LaTeX"(1 1/\sqrt {e} \epsilon /tex math>/inline formula> approximation algorithm, named Billion scale Cost award Targeted algorithm (BCT) to solve the problem in billion scale networks. Comparing with <italic>IM</italic> algorithms, we show that <italic>BCT</italic> is both theoretically and experimentally faster than the state of the arts while providing better solution quality. Moreover, we prove that under the linear threshold model, <italic>BCT</italic> is the first <italic>sub linear time</italic> algorithm for <italic>CTVM</italic> (and <italic>IM</italic> in dense networks. We carry a comprehensive set of experiments on various real networks with sizes up to several billion edges in diverse disciplines to show the absolute superiority of <italic>BCT</italic> on both <italic>CTVM</italic> and <italic>IM</italic> domains. Experiments on Twitter data set, containing 1.46 billions of social relations and 106 millions tweets, show that <italic>BCT</italic> can identify key influencers in trending topics in only few minutes.
IEEE/ACM Transactions on Networking
Hung T Nguyen My T Thai Thang N Dinh
9594898
Identification of multi spreader users in social networks for viral marketing
Identifying high spreading power nodes is an interesting problem in social networks. Finding super spreader nodes becomes an arduous task when the nodes appear in large numbers, and the number of existing links becomes enormous among them. One of the methods that is used for identifying the nodes is to rank them based on k shell decomposition. Nevertheless, one of the disadvantages of this method is that it assigns the same rank to the nodes of a shell. Another disadvantage of this method is that only one indicator is fairly used to rank the nodes. k Shell is an approach that is used for ranking separate spreaders, yet it does not have enough efficiency when a group of nodes with maximum spreading needs to be selected; therefore, this method, alone, does not have enough efficiency. Accordingly, in this study a hybrid method is presented to identify the super spreaders based on k shell measure. Afterwards, a suitable method is presented to select a group of superior nodes in order to maximize the spread of influence. Experimental results on seven complex networks show that our proposed methods outperforms other well known measures and represents comparatively more accurate performance in identifying the super spreader nodes.
J. Inf. Sci.
Amir Sheikhahmadi Mohammad Ali Nematbakhsh
40951451
Validating viral marketing strategies in Twitter via agent based social simulation
We present a method to validate viral marketing strategies in Twitter.The method is based on an Agent based Social Simulation research methodology.A rumor spread model and control strategies are also presented as a case study.The model and the strategies are evaluated against others in the literature.An open source simulator and the Twitter data employed are also given. A number of marketing phenomena are too complex for conventional analytical or empirical approaches. This makes marketing a costly process of trial and error: proposing, imagining, trying in the real world, and seeing results. Alternatively, Agent based Social Simulation (ABSS) is becoming the most popular approach to model and study these phenomena. This research paradigm allows modeling a virtual market to: design, understand, and evaluate marketing hypotheses before taking them to the real world. However, there are shortcomings in the specialized literature such as the lack of methods, data, and implemented tools to deploy a realistic virtual market with ABSS. To advance the state of the art in this complex and interesting problem, this paper is a seven fold contribution based on a (1) method to design and validate viral marketing strategies in Twitter by ABSS. The method is illustrated with the widely studied problem of rumor diffusion in social networks. After (2) an extensive review of the related works for this problem, (3) an innovative spread model is proposed which rests on the exploratory data analysis of two different rumor datasets in Twitter. Besides, (4) new strategies are proposed to control malicious gossips. (5) The experimental results validate the realism of this new propagation model with the datasets and (6) the strategies performance is evaluated over this model. (7) Finally, the article is complemented by a free and open source simulator.
Expert Syst. Appl.
Emilio Serrano Carlos Angel Iglesias
12789751
Profit maximization for viral marketing in Online Social Networks
Information can be disseminated widely and rapidly through Online Social Networks (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. The budget allocation for seed selection reflects a tradeoff between the expense and reward of viral marketing. In this paper, we define a general profit metric that naturally combines the benefit of influence spread with the cost of seed selection in viral marketing to eliminate the need for presetting the budget for seed selection. 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. As a result, from the computability perspective, the problem of profit maximization is much more challenging than that of influence maximization. We develop new seed selection algorithms for profit maximization with strong approximation guarantees. Experimental evaluations with real OSN datasets demonstrate the effectiveness of our algorithms.
2016 IEEE 24th International Conference on Network Protocols (ICNP)
Jing Tang Xueyan Tang Junsong Yuan
57758350
Multi criteria decision support for planning and evaluation of performance of viral marketing campaigns in social networks
The current marketing landscape, apart from conventional approaches, consists of campaigns designed especially for launching information diffusion processes within online networks. Associated research is focused on information propagation models, campaign initialization strategies and factors affecting campaign dynamics. In terms of algorithms and performance evaluation, the final coverage represented by the fraction of activated nodes within a target network is usually used. It is not necessarily consistent with the real marketing campaigns using various characteristics and parameters related to coverage, costs, behavioral patterns and time factors for overall evaluation. This paper presents assumptions for a decision support system for multi criteria campaign planning and evaluation with inputs from agent based simulations. The results, which are delivered from a simulation model based on synthetic networks in a form of decision scenarios, are verified within a real network. Last, but not least, the study proposes a multi objective campaign evaluation framework with several campaign evaluation metrics integrated. The results showed that the recommendations generated with the use of synthetic networks applied to real networks delivered results according to the decision makers' expectation in terms of the used evaluation criteria. Apart from practical applications, the proposed multi objective approach creates new evaluation possibilities for theoretical studies focused on information spreading processes within complex networks.
PloS one
Artur Karczmarczyk Jaroslaw Jankowski Jaroslaw Watrobski
16193565
Can information be spread as a virus? Viral Marketing as epidemiological model
In epidemiology, an epidemic is defined as the spread of an infectious disease to a large number of people in a given population within a short period of time. In the marketing context, a message is viral when it is broadly sent and received by the target market through person to person transmission. This specific marketing communication strategy is commonly referred as viral marketing. Because of this similarity between an epidemic and the viral marketing process and because the understanding of the critical factors to this communications strategy effectiveness remain largely unknown, the mathematical models in epidemiology are presented in this marketing specific field. In this paper, an epidemiological model susceptible infected recovered to study the effects of a viral marketing strategy is presented. It is made a comparison between the disease parameters and the marketing application, and MATLAB simulations are performed. Finally, some conclusions are carried out and their marketing implications are exposed: interactions across the parameters suggest some recommendations to marketers, as the profitability of the investment or the need to improve the targeting criteria of the communications campaigns. Copyright (c) 2015 John Wiley Sons, Ltd.
ArXiv
Helena Sofia Rodrigues Manuel Jose Fonseca
13699203
Profit Maximization for Viral Marketing in Online Social Networks: Algorithms and Analysis
Information can be disseminated widely and rapidly through Online Social Networks (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. The selection of initial seed users yields a tradeoff between the expense and reward of viral marketing. In this paper, we define a general profit metric that naturally 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. Experimental evaluations with real OSN datasets demonstrate the effectiveness of our algorithms and techniques.
IEEE Transactions on Knowledge and Data Engineering
Jing Tang Xueyan Tang Junsong Yuan
57373554
Community based influence maximization for viral marketing
Derived from the idea of word to mouth advertising and with applying information diffusion theory, viral marketing attracts wide research interests because of its business value. As an effective marketing strategy, viral marketing is to select a small set of initial users based on trust among close social circles of friends or families so as to maximize the spread of influence in the social network. In this paper, we propose a new community based influence maximization method for viral marketing that integrates community detection into influence diffusion modeling, instead of performing community detection independently, to improve the performance. We first build a comprehensive latent variable model which captures community level topic interest, item topic relevance and community membership distribution of each user, and we propose a collapsed Gibbs sampling algorithm to train the model. Then we infer community to community influence strength using topic irrelevant influence and community topic interest, and further infer user to user influence strength using community to community influence strength and community membership distribution of each user. Finally we propose a community based heuristic algorithm to mine influential nodes that selects the influential nodes with a divide and conquer strategy, considering both topic aware and community relevant to enhance quality and improve efficiency. Extensive experiments are conducted to evaluate effectiveness and efficiency of our proposals. The results validate our ideas and show the superiority of our method compared with state of the art influence maximization algorithms.
Applied Intelligence
Huimin Huang Hong Shen Zaiqiao Meng Huajian Chang Huaiwen He