Richardson and Domingos KDD 2002

Citation

 author = {Richardson, Matthew and Domingos, Pedro},
 title = {Mining knowledge-sharing sites for viral marketing},
 booktitle = {Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining},
 series = {KDD '02},
 year = {2002},
 isbn = {1-58113-567-X},
 pages = {61--70},
 numpages = {10},
 

Online version

http://alchemy.cs.washington.edu/papers/pdfs/richardson-domingos02b.pdf

Abstract from the paper

Viral marketing takes advantage of networks of influence among customers to inexpensively achieve large changes in behavior. Our research seeks to put it on a firmer footing by mining these networks from data, building probabilistic models of them, and using these models to choose the best viral marketing plan. Knowledge-sharing sites, where customers review products and advise each other, are a fertile source for this type of data mining. In this paper we extend our previous techniques, achieving a large reduction in computational cost, and apply them to data from a knowledge-sharing site. We optimize the amount of marketing funds spent on each customer, rather than just making a binary decision on whether to market to him. We take into account the fact that knowledge of the network is partial, and that gathering that knowledge can itself have a cost. Our results show the robustness and utility of our approach.

Summary

This paper attempts to show that by modeling the consumer market as a social network and exploiting the influence of peer opinions on customers, we can significantly increase profits. In the context of a social network, a customer not only has an intrinsic value (his value as a customer based on the products he is likely to purchase), but also his network value (based on his positive influence on others’ probabilities of purchasing the product). The authors model this interaction with a linear model and attempt to calculate the optimal marketing plan for a product. A marketing plan might involve giving discounts to some of the customers who have high network value. The optimal marketing plan would be the one that maximizes the Expected Lift in Profits (ELP). ELP is basically the increase in revenue on the whole customer network when a portion of the network is marketed to. The authors apply this model of customer influence and interactions to a social network mined from Epinions, a general consumer review site. The results of their experiments showed that viral marketing resulted in a considerable increase in profits over direct marketing.

The authors also showed that viral marketing is robust even in the presence of incomplete network knowledge. They simulated partial network knowledge by randomly removing edges from the social network. They computed the optimal marketing plan on the incomplete network and tested it on the complete network. The results were surprising: the company can achieve 69% of the lift in profit knowing only 5% of the edges in the network.

The authors also simulated what would happen if a company with little or no knowledge about the relationships between its customers, spends marketing research funds to try and acquire it by asking some of its customers for the list of people whose opinions they would seek when buying the company products. The authors would query the customer with the highest network effect on the partial network, recalculate network effects with the new information, query the next customer with highest network effect, and so on until the marketing funds are all spent. This method performed quite well, lifting profits by almost 3 times the lift achieved by random choice when 10% of the customers are queried.

Related Papers

• Leskovec et. al., ACM Conference on Electronic Commerce (EC), 2006.
• P. Domingos and M. Richardson. Mining the Network Valueof Customers. In Proceedings of the Seventh InternationalConference on Knowledge Discovery and Data Mining,pages 57-66, San Francisco, CA, 2001. ACM Press.