病毒式行銷(viral marketing)透過人際之間的互動，藉由消費者對消費者的推薦，達到廣告效益。而廣告商要如何進行病毒式行銷？廣告商必須在有限資源下從人群中找出具有影響力的人，將產品或是概念推薦給更多的消費者，以說服消費者會採納他們的意見。
利用社會網絡(Social network)，我們可以簡單地將消費者之間的關係用節點跟邊呈現，而Influence Maximization就是在社會網絡上選擇最具有影響力的k個消費者，而這k個消費者能影響最多的消費者。
然而，廣告相當重視目標消費群，廣告目的就是希望能夠影響目標消費群，使目標消費群購買產品。因此，我們針對標籤社會網絡(Labeled social network)提出Labeled influence maximization的問題，不同過往的研究，我們加入了標籤的條件，希望在標籤社會網絡中影響到最多符合標籤條件的節點。
針對標籤社會網絡，我們除了修改四個解決Influence maximization problem的方法，Greedy、NewGreedy、CELFGreedy和DegreeDiscount，以找出影響最多符合類別條件的節點的趨近解。我們也提出了兩個新的方法ProximityDiscount和MaximumCoverage來解決Labeled influence maximization problem。我們在Offline時，先計算節點與節點之間的Proximity，當行銷人員Online擬定行效策略時，系統利用Proximity，Onlin找出趨近解。
實驗所採用的資料是Internet Movie Database的社會網絡。根據實驗結果顯示，在兼顧效率與效果的情況下，適合用ProximityDiscount來解決Labeled influence maximization problem。

Influence maximization problem is to find a small subset of nodes (seed nodes) in a social network that could maximize the spread of influence. But when marketers advertise for some products, they have a set of target audience. However, influence maximization doesn’t take target audience into account.
This thesis addresses a new problem called labeled influence maximization problem, which is to find a subset of nodes in a labeled social network that could influence target audience and maximizes the profit of influence. In labeled social network, every node has a label, and every label has profit which can be set by marketers.
We propose six algorithms to solve labeled influence maximization problem. To accommodate the objective of labeled influence maximization, four algorithms, called LabeledGreedy, LabeledNewGreedy, LabeledCELFGreedy, and LabeledDegreeDiscount, are modified from previous studies on original influence maximization. Moreover, we propose two new algorithms, called ProximityDiscount and MaximumCoverage, which offline compute the proximities of any two nodes in the labeled social network. When marketers make strategies online, the system will return the approximate solution by using proximities.
Experiments were performed on the labeled social network constructed from Internet Movie Database, the result shows that ProximityDiscount may provide good efficiency and effectiveness.

[1] F. Bass, “A New Product Growth Model for Consumer Durables,” Management Science, Vol. 5, No. 5, 1969.
[2] J. Brown and P. Reinegen, “Social Ties and Word-of-mouth Referral Behavior,” Journal of Consumer Research, Vol. 14, No. 3, 1987.
[3] W. Chen, Y. Wang, and S. Yang, “Efficient Influence Maximization in Social Networks,” Proc. of ACM International Conference on Knowledge Discovery and Data Ming SIGKDD, 2009.
[4] A. Chin and M. Chignell, “A Social Hypertext Model for Finding Community in Blogs,” Proc. of Conference on Hypertext and Hypermedia, 2006.
[5] G. Cornuejols, M.Fisher and G. Nemhauser, “Location of Bank Accounts to Optimize Float,” Management Science, Vol. 23, 1997
[6] P. Domings and M. Richardson, “Mining the Network Value of Consumers,” Proc. of ACM International Conference on Knowledge Discovery and Data Mining SIGKDD, 2001.
[7] P. G. Doyle and J. L. Sell, “Random Walks and Electrical Networks,” The Mathematical Association of America, 1985.
[8] C. Faloutsos, K. S. McCurley, and A. Tomkins, “Fast Discovery of Connection Subgraphs,” Proc. of ACM International Conference on Knowledge Discovery and Data Mining SIGKDD, 2004.
[9] B. Gallagher, H. Tong, T. Eliassi-Rad, and C. Faloutsos, “Using Ghost Edges for Classification in Sparsely Labeled Networks,” Proc. of ACM International Conference
on Knowledge Discovery and Data Mining SIGKDD, 2008.
[10] J. Goldenberg, B. Libai, and E. Muller, “Using Complex Systems Analysis to Advance Marketing Theory Development,” Academy of Marketing Science Review, Vol. 2001, No. 9, 2001.
[11] J. Goldenberg, B. Libai, and E. Muller, “Talk of the Network: A Complex Systems Look at the Underlying Process of Word-of-Mouth,” Marketing Letters, Vol.12, No. 3 , 2003.
[12] D. Kempe, J. Kleinberg, and E. Tardos, “Maximizing the Spread of Influence through a Social Network,” Proc. of ACM International Conference on Knowledge Discovery and Data Mining SIGKDD, 2003.
[13] N. Katoh, T. Ibaraki and H. Mine, “An Efficient Algorithm for k Shortest Simple Paths,” Networks, Vol.12 , pages.411-427,1982.
[14] Y. Koren, S. C. North, and C. Volinsky, “Measuring and Extracting Proximity in Networks,” Proc. of ACM International Conference on Knowledge Discovery and Data Mining SIGKDD, 2006.
[15] J. Leskovec, L. A. Adamic, and B. A. Huberman, “The Dynamics of Viral Marketing,” ACM Transactions on the Web, Vol. 1, No. 1, 2007.
[16] J. Leskovec, A. Krause, C. Guestrin, C. Faloutsos, J. VanBriesen, and N. Glance, “Cost-effective Outbreak Detection in Networks,” Proc. of ACM International Conference on Knowledge Discovery and Data Ming SIGKDD, 2007.
[17] D. Liben-Nowell and J. Kleinberg, “The Link Prediction Problem for Social Network,” Proc. of International Conference on Information and Knowledge Management CIKM, 2003.
[18] V. Mahajan, E. Muller, and F. Bass, “New Product Diffusion Model in Marketing: A Review and Directions for Research,” Journal of Marketing, Vol.54, No.1m pages.1-26, 1990.
[19] E. Q. V. Martins and M. M. B. Pascoal, “A New Implementation of Yen’s ranking loopless paths algorithm,” Quarterly Journal of the Belgian, French and Italian Operations Research Societies, 2002.
[20] G. Nemhauser, L. Wolsey, and M. Fisher, “An Analysis of the Approximations for Maximizing Submodular Set Functions,” Mathematical Programming, Vol.14, No.1, 1978.
[21] M. Richardson and P. Domingos, “Mining Knowledge-Sharing Sites for Viral Marketing,” Proc. of International Conference on Knowledge Discovery and Data Mining, 2002.
[22] J. Scripps, P. N. Tan, and A. H. Esfahanian, “Exploring the Link Structure and Community-based Node Roles in Networked Data,” Proc. of IEEE International Conference on Data Mining ICDM, 2007.
[23] H. Tong, C. Faloutsos, and J. Y. Pan, “Fast Random Walk with Restart and Its Applications,” Proc. of IEEE International Conference on Data Mining ICDM, 2006.
[24] X. Yan and J. Han, “gSpan: Graph-Based Substructure Pattern Mining,” Proc. of the 2002IEEE International Conference on Data Mining ICDM, 2002.