Richardson & Domingos, KDD 2002

From ScribbleWiki: Analysis of Social Media

Jump to: navigation, search


Mining Knowledge-Sharing Sites for Viral Marketing

Authors: Matthew Richardson and Pedro Domingos


Review -by Shilpa Arora

Note: I have added the mathematic formulation to the textual description for detailed understanding.

Introduction & Motivation

Data mining has been used in marketing to identify the potential people as targets for marketing the product/service. Direct marketing aims at making this decision based on individual's characteristics and Mass marketing uses the properties of the population the individual belongs to, to select a group of people to target for marketing. However, members in the market tend to influence each other and people often trust and act on recommendation from their friends. Thus, it would be beneficial to market the product to those with strongest influence in the market. Viral Marketing aims at identifying the most influential people in the market. A classic example of viral marketing is the Hotmail email service which grew from 0 to 12 million users in 18 months with the inclusion of a promotional message with service's URL in every email sent using it.

In addition to a customer's intrinsic value (based on the products he is likely to purchase), viral marketing also considers the network value of a customer. The network value of a customer is measured by his influence on other's probability of purchasing the product. To determine the network value of customers, we need to know the relationship between them. Chat rooms, discussion forums and knowledge-sharing web sites are rich source of such information. Knowledge-sharing sites are often product-oriented where people discuss their opinions about products, and rate and compare several products, providing a rich source of customer preferences and interactions.

In this paper, the authors propose models for finding optimal viral marketing plans and test these models on Epinions, a popular knowledge sharing site. They also present techniques for marketing in a situation when we have only partial knowledge about the relationships between customers and show that these techniques perform well with very limited marketing research funds.

Viral Marketing Model

A viral marketing model is defined for a given product, a potential set of customers for the product, neighbors of each customer who influence him and a marketing plan for each customer. Probability that a customer will buy a product is defined as the weighted sum of the probability that he will buy the product on his own (based on his likings and without his neighbors influence) and the probability that he would buy the product under his neighbor's influence. The probabilities are weighted by how self-reliant the customer is (self-reliance factor). A linear model is employed to approximate the effect of neighbor's influence. The weights and influence of neighbors are estimated using a random sample of users or based on prior knowledge or demographic information

Mathematical Formulation

Suppose we have n potential customers and the variable <math>X_{i}=1</math>, if customer i buys the product being marketed. Let neighbors of <math>X_{i}</math> that influence him be <math>N_{i}</math>. Let Y describe a set of attributes of the product and <math>M_{i}</math> be the marketing action taken for customer i. For Boolean Marketing, <math>M_{i}</math> is 1 if a discount is offered to the customer and its 0 if no marketing action is performed. Thus, the probability the customer i will buy the product is defined as the

<math> P(X_{i}\mid N_{i},Y,M)=\beta_{i} P_{0}(X_{i}\mid Y,M_{i}) + (1-\beta_{i})P_{N}(X_{i}\mid N_{i},Y,M)</math>

where, <math> P_{0}(X_{i}\mid Y,M_{i}) </math> is <math>X_{i}'s</math> internal probability of purchasing the product based on individual's characteristics like in direct marketing. <math>P_{N}(X_{i}\mid N_{i},Y,M)</math> measures influence of neighbors on <math>X_{i}</math> and is defined as:

<math>P_{N}(X_{i}\mid N_{i},Y,M) = \sum_{X_{j} \in N_{i}} w_{ij} X_{j} </math>

where, <math> w_{ij} </math> represents the influence neighbor j has on customer i. In this paper only the possitive interactions between the customer is taken into consideration. <math> \beta_{i} </math> is a value between 0 and 1 that measures how self-reliant <math>X_{i}</math> is.

In this paper, the proposed model calculates optimal marketing plan for a product that has not yet been introduced in the market. Hence, in this situation the state of neighbors will not be known and it needs to sum over all possible neighbor states. This would give us:

<math> P(X_{i}\mid N_{i},Y,M)=\beta_{i} P_{0}(X_{i}\mid Y,M_{i}) + (1-\beta_{i})\sum_{X_{j} \in N_{i}} w_{ij}P(X_{j}\mid Y,M)</math>

With this recursive formulation for probabilities, the algorithm is applied iteratively with initial assignment as the internal probabilities <math>P_{0}(X_{i}=1\mid Y,M_{i})</math>.

Evalution using Expected lift in Profit (ELP)

Goal of Viral Marketing is to find the marketing plan that maximizes profit. Thus, to evaluate the models, the authors define a measure called Expected Lift in Profit (ELP). The expected lift in profit from a marketing action on a customer (intrinsic value) is defined as the difference in revenue weighted by the probability of the customer buying the product, with and without the marketing strategy minus the cost of marketing to the customer. Global lift can be calculated by summing over the effect over all the customers. A customer's total value is the global lift in profit from marketing to him and a customer's network value is the difference between his total and intrinsic values. A customer with high network value directly or indirectly influences many others to purchase and hence is a good candidate for marketing.

Mathematical Formulation

The expected lift in profit from performing marketing action z on customer i in isolation is defined as:

<math>ELP_{i}^{z}(Y,M) = r(z) P(X_{i}=1\mid Y,f_{i}^{z}(M))-r(0)P(X_{i}=1\mid Y,f_{i}^{0}(M))-c(z)</math> 

where, r(0) is the revenue from selling the product to the customer if no marketing action is performed, r(z) is the revenue if the product is purchased with marketing strategy z and <math>c_(z)</math> is the cost of performing action z. <math>f_{i}^{z}(M) <math> is the result of setting <math>M_{i}</math> to z and leaving the rest of M unchanged.

The global lift in profit is defined as:

<math>ELP(Y,M) = \sum_{i=1}^{n}[r(M_{i}) P(X_{i}=1\mid Y,M)-r(0)P(X_{i}=1\mid Y,M_{0})-c(M_{i})]</math>

For boolean marketing, z=0 or z=1 where z=0 means no marketing is performed and z=1 means offering the customer a discount.

Inference and Search

The goal here is to find the marketing plan M that maximizes the Expected Lift in Profit (ELP). A marketing plan suggests which customers to sell the product. Effect of a customer on other customers in the network can be used to decide whether to market to this person or not. Customer i's network effect is defined as the effect it has on the people he influences times their effect on the network. This approach is similar to the PageRank (Page et. al., 1998) algorithm for determining importance of web pages. In PageRank, a web page is ranked high if many highly ranked pages point to it. Similarly, in viral marketing, a customer is valued high if he influences many highly values customers.

Mathematic Formulation

The network effect each customer i has on a product with attributes Y, is defined as:

<math>\Detla_{i}(Y)=\sum_{j=1}^{n} w_{ji}\Detla_{j}(Y) </math>

<math>\Detla_{i}(Y)</math> is initialed to 1 for all i and then recursively re-calculated until convergence.

Applying the model to Epinions

At Epinions, members submit product reviews with ratings and they are paid each time their review is read. They also rate the reviews they read and list the reviews they trust. To apply the proposed model to Epinions, they use the self-reliance factor as 0.5 for all customers. They assume that all the people a user trusts have equal influence on him i.e. <math>w_{ij}=1/\mid N_{i} \mid for X_{j} \in N_{i}</math> and all the people a user trusts are his neighbors <math>N_{i}</math>. They used a single product attribute Y: one of the 25 product categories.

They present their results on a simple advertising situation (boolean marketing) with <math> \alpha=2, r_{0}=1 and r_{1}=1 </math> i.e. revenues were in the unit of number of products sold. alpha is the parameter that specifies the magnitude of the marketing effect. Marketing is expected to have a larger impact on customers who were already inclined to purchase the product.

Table 1 shows the profit comparison for no marketing, direct and viral marketing for boolean marketing. As can be seen, viral marketing outperforms direct marketing in all the cases with a substantial margin.


Figure 1 shows 500 highest network values in decreasing order. A network value of 200 for a given customer implies that by marketing to him, we essentially get free marketing to an additional 200 customers. A customer with high network value is one who: (1) is likely to purchase the product, and hence would be affected by the marketing, and (2) is trusted by many other customers in the network who have low self-reliance factor and have same trust characteristic.


Speed: The model introduced in this paper is linear and thus has tremendous speed advantages over a non-linear model (Domingos and Richardson, 2001). The network value is independent of the marketing actions being performed on others, which allows finding the optimal marketing plan without performing a heuristic search over plans.

Robustness to partial knowledge: Normally the entire social network between customers is not known to a company for making its marketing strategy. The proposed approach is also shown to be robust to partial network knowledge and outperforms direct marketing. They could achieve 69% lift in profit by knowing only 5% of the edges in the network. Robustness occurs when edges are missing at random as it results in a correlation between the number of people who trust a given person in the partial and the true network. A person with high network value in partial network also has higher network value in the full network.

Acquiring new network knowledge: Given the partial social network (or no information at all), the company may want to spend some marketing money in getting some more knowledge of the network to increase its profit. More information can be acquired by querying users for information about their neighbors. This raises an interesting question as to which users should we query given a limited budget. The paper suggests that querying customers with highest network effect on the partial network, i.e. those with large influence on the network, is helpful. They used an iterative process of querying the customers with highest network effect and then recalculating the network effects with the new information until all the marketing funds have been spent. Figure 4 shows that querying the users with highest network effect results in an order of magnitude more lift in profit than querying customers randomly. For faster processing, they re-calculate the network profit after querying 100 customers in each iteration.



In this paper the authors propose a model for viral marketing using knowledge sharing sites. The model makes strong linearity assumptions to achieve greater scalability. They also show that their approach is applicable in the case when only partial network information is available. In this review, I have discussed their approach for boolean marketing only. They also discuss applying their approach to continuous marketing actions i.e. where M_{i} is continuous between 0 and 1.


L. Page, S. Brin, R. Motwani, and T. Winograd. The PageRank citation ranking: Bringing order to the web. Technical Report, Stanford University, Stanford, CA. 1998.

P. Domingos and M. Richardson. Mining the Network Value of Customers. In Proceedings of the Seventh International Conference on Knowledge Discovery and Data Mining, pages 57-66, San Francisco, CA, 2001. ACM Press.

Personal tools
  • Log in / create account