Isolated Vertices and the Longest Edge of the Minimum Spanning Tree of Weighted Configuration

Get Complete Project Material File(s) Now! »

Viral Marketing: Examples, Applications and Numerical Studies

In a viral marketing campaign, a firm initially targets a small set of pioneers and hopes that they would influence a sizeable fraction of the population by diffusion of influence through the network. In general, any marketing campaign might fail to go viral in the first try. As such, it would be useful to have some guide to evaluate the effectiveness of the campaign and judge whether it is worthy of further resources, and in case the campaign has potential, how to hit upon a good pioneer who can make the campaign go viral.
In this chapter, we use the results of the previous chapter and some key illustrative examples to provide an insight from a firm’s perspective regarding how to evaluate the effectiveness of a marketing campaign and do cost-benefit analysis by collecting relevant statistical data from the pioneers it selects.


The penetration of internet and the emergence of huge online social networks in the last decade has radically altered the way that people consume media and print, leading to an ongoing decline in importance of conventional channels and consequently, marketing through them. This radical shift has brought in its wake a host of opportunities as well as challenges for the advertisers. On the one hand, firms finally have the possibility to reach in a cost-effective way not only the past responsive customers, but indeed all the potentially responsive ones. But the firms, in general, have found it a hit-or-miss game to gain attention through the new medium, with the chance of a hit depending on the loyaity of its fan-base. What makes viral marketing tempting for the firms is that when it is a hit, it is a spectacular one. But continuing to spend resources on a campaign while hoping that it goes viral is a precarious strategy. The fat-tail uncertainty of viral marketing makes it inherently different from conventional marketing and calls for a fundamentally different approach to decision-making: which individuals, and how many, to initially target in the online network? What amount of resources to spend on these initially targeted pioneers? And most importantly, when to stop, admit the inefficacy of the current campaign and develop a new one?
Configuration model serves as a useful first approximation of an online social network, particularly when one does not have an access to a detailed information about the network structure. The diffusion dynamic studied in Chapter 2 can be stated in this context as follows: any individual in the network influences a random subset of its neighbours, the distribution of which depends on the effectiveness of the marketing campaign.
We first illustrate large-network-limit results proved in Chapter 2 for configuration model having two types of degree-distribution: Poisson and Power Law. Three examples illustrating the dynamic of influence propagation on these two networks are considered: (1) Bernoulli transmissions; (2) Node percolation; (3) Coupon-collector transmissions.
Based on the above analysis, we offer a practical decision-making guide for marketing on online networks which could be useful to firms with no prior access to detailed network structure. Specifically, we consider the naïve strategy of picking some number of pioneers at random from the population, spending some fixed amount of resources on each of them and waiting to see if the campaign goes viral, picking another batch if it does not. For this strategy, we suggest what statistical data the firm should collect from its pioneers, and based on these, how to estimate the effectiveness of the campaign and make a cost-benefit analysis.
We will continue to use the notation introduced in the previous chapter.

Related Work

The phenomenon of viral propagation was first studied in the context of the spread of epidemics on complex networks, whence the term viral marketing originates ([6], [50]). The impact of social network structure on the propagation of social and economic behavior has also been recognized ([8], [52]) and there is growing evidence of its importance ([7]).
In the context of viral marketing, the principal approach which has been developed tries to exploit the network structure to maximize the probability of marketing campaign going viral for each dollar spent. This approach relies on the availability of large databases containing detailed information regarding the network structure and the past instances of influence propagation to come up with the best predictor of the most influential individuals who should be targeted for future campaigns ([42], [25]). In our approach, we do not rely on locating the pioneers by data-mining the network. Instead, we suggest a way to measure the current campaign’s effectiveness based on its ongoing diffusion in the network. This idea can possibly complement the data mining approach when the network information is freely accessible.

READ  The human genome and genetic diversity


Let us consider the results of Chapter 2 in the context of a few illustrative network examples. In what follows, denote by GD(x) = E[x D] and GD(t) (x) = E[x ] the probability generating function (pgf) of D and D(t), respectively. In the notation of Chapter 2, this means that GD(x) = g(x, x) (3.1) and GD(t) (x) = (x).

Bernoulli transmissions

Let us assume some arbitrary distribution of the degree D satisfying Condition 1.3 (to guarantee the existence of the big component of the social graph). Suppose that each user decides independently for each of its friends with probability p 2 [0, 1] whether to transmit the influence to him or not. We call this model CM with Bernoulli transmissions and p the transmission probability. Note that given the total degree D, the transmitter degree D(t) is Binomial(D, p) random variable.
Proposition 3.1 In the CM with a general degree distribution D satisfying Condition 1.3 and Bernoulli transmissions, the campaign can go viral if and only if the transmission probability p satisfies p > E[D] E[D2] E[D] .
Example 3.2.1 (Poisson degree) When D has Poisson distribution of parameter (in which case the CM is asymptotically equivalent to the Erd˝os-Rényi model in the local weak sense as defined in refSi.lwc) the condition (3.3) reduces to p > 1 and by (3.4), the fraction of the influenced population and good pioneers, whp, is equal to (1 )=p, where is the unique zero of the function (x 1)=p + 1 exp( (x 1) in (0, 1) .
More commonly observed degree-distributions in social networks have power-law tails.
Recall from Proposition 3.1, that Bernoulli transmissions lead to the model where the fraction of the influenced population and the fraction of good pioneers are asymptotically equal to each other. In what follows we present two scenarios where the set of good pioneers and the influenced population have different size.

Enthusiastic and apathetic users or node percolation

Consider CM with a general degree distribution D satisfying (2.4), whose nodes either transmit the influence to all their friends (these are “enthusiastic” nodes) or do not transmit to any of their friends (“apathetic” ones). Let p denote the fraction of nodes in the network which are enthusiastic. Note that this model corresponds to the node-percolation 1 on the CM.

Table of contents :

1 Random Graphs: an Overview 
1.1 Galton-Watson Branching Processes
1.2 Erd˝os-Rényi Random Graph
1.2.1 Phase transition: Emergence of a giant component
1.2.2 Connectivity
1.3 Configuration Model
1.3.1 Phase transition: Emergence of a giant component
1.3.2 Information diffusion
1.3.3 Connectivity
1.3.4 Diameter of weighted configuration model
1.4 Local weak convergence
2 Viral Marketing in Configuration Model 
2.1 Introduction
2.1.1 Enhanced Configuration Model
2.1.2 Results
2.1.3 Methodology
2.1.4 Related Work
2.2 Notation and Results
2.2.1 Forward influence propagation
2.2.2 Pioneers— Branching process heuristic
2.2.3 Dual Back-Propagation Process
2.2.4 Concluding Remarks
2.3 Analysis of the Original Forward-Propagation Process
2.4 Analysis of the Dual Back-Propagation Process
2.5 Duality Relation
3 Viral Marketing: Examples, Applications and Numerical Studies 
3.1 Introduction
3.1.1 Related Work
3.2 Examples
3.2.1 Bernoulli transmissions
3.2.2 Enthusiastic and apathetic users or node percolation
3.2.3 Absentminded users or coupon-collector transmissions
3.2.4 Numerical examples Simulations Estimation Analytic evaluation Case study
3.3 Application to Viral Campaign Evaluation
4 Isolated Vertices and the Longest Edge of the Minimum Spanning Tree of Weighted Configuration
4.1 Introduction
4.2 Results
4.3 Isolated vertices of weighted configuration model
4.4 Longest edge of MST
5 FutureWork: Convex comparison of Random Graphs 
5.1 Convex Comparison of Random Graphs
5.1.1 Convex Order on Galton-Watson Tree and Implications
5.1.2 Convex Order on Sequences of Finite Random Graphs and Implications in Configuration


Related Posts