學術產出-Theses
Article View/Open
Publication Export
-
題名 利用標籤社會網絡之影響力最大化達到目標式廣告行銷
Influence maximization in labeled social network for target advertising作者 李法賢 貢獻者 沈錳坤
李法賢關鍵詞 標籤社會網絡
影響力
社會網絡
極大化
Labeled influence maximization
Influence maximization
Social network日期 2010 上傳時間 27-Jun-2013 15:47:07 (UTC+8) 摘要 病毒式行銷(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. 描述 碩士
國立政治大學
資訊科學學系
97753017
99資料來源 http://thesis.lib.nccu.edu.tw/record/#G0097753017 資料類型 thesis dc.contributor.advisor 沈錳坤 zh_TW dc.contributor.author (Authors) 李法賢 zh_TW dc.creator (作者) 李法賢 zh_TW dc.date (日期) 2010 en_US dc.date.accessioned 27-Jun-2013 15:47:07 (UTC+8) - dc.date.available 27-Jun-2013 15:47:07 (UTC+8) - dc.date.issued (上傳時間) 27-Jun-2013 15:47:07 (UTC+8) - dc.identifier (Other Identifiers) G0097753017 en_US dc.identifier.uri (URI) http://nccur.lib.nccu.edu.tw/handle/140.119/58580 - dc.description (描述) 碩士 zh_TW dc.description (描述) 國立政治大學 zh_TW dc.description (描述) 資訊科學學系 zh_TW dc.description (描述) 97753017 zh_TW dc.description (描述) 99 zh_TW dc.description.abstract (摘要) 病毒式行銷(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。 zh_TW dc.description.abstract (摘要) 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. en_US dc.description.tableofcontents 摘要 i目錄 iii圖目錄 iv表目錄 vi第一章 前言 1第二章 相關研究 42.1 Influence Maximization 42.2 Independent Cascade Model 62.3 Weighted Cascade Model 8第三章 研究方法 93.1 問題定義 93.2 LabeledGreedy Algorithm 103.2 LabeledCELFGreedy Algorithm 133.3 LabeledNewGreedy Algorithm 143.4 LabeledDegreeDiscount 163.5 ProximityDiscount 183.5.1 Proximity for Independent Cascade Model 183.5.2 Computing Proximity 193.5.3 ProximityDiscount Algorithm 213.6 MaximumCoverage 243.7 Proximity Threshold and Maximum Coverage Threshold 25第四章 實驗結果與評估 274.1 實驗設計 274.2 實驗結果 28第五章 結論與未來研究方向 365.1 結論 365.2 未來研究方向 37 圖目錄圖2.1：影響力在Independent Cascade Model擴散的過程 6圖3.1：Labeled influence maximization之範例 10圖3.2：KTT`s greedy algorithm 11圖3.3：CELFGreedy algorithm 13圖3.4：NewGreedy algorithm 15圖3.5：LabeledDegreeDiscount algorithm 17圖3.6：前k條最短簡單路徑和前k條最短路徑之範例。 20圖3.8：ProximityDiscount的資料結構 23圖3.7：ProximityDiscount algorithm 23圖3.9：Maximum k coverage algorithm 24圖3.10：MaximumCoverage algorithm 25圖4.1：實驗一(L_t={Drama}, Profit_Drama=1)之效果。 29圖4.2：實驗一(L_t={Comedy}, Profit_Comed=1)之效果。 30圖4.3：實驗二(L_t={Comedy, Biography}, Profit_Comedy=1, Profit_Biography=1)之效果 30圖4.4：實驗二(L_t={Comedy, Thriller}, Profit_Comedy=1, Profit_Thriller=1)之效果 31圖4.5：實驗二(目標標籤為所有的標籤，且所有的目標標籤之利潤皆為1)之效果。 32圖4.6：實驗三(L_t={Comedy, Drama}, Profit_Drama=1,Profit_Comedy=3)之效果。 33圖4.7：實驗三(L_t={Comedy, Thriller, Drama}, Profit_Drama=1,Profit_Comedy=3,Profit_Thriller=5)之效果。 33圖4.7：LabeledDegreeDiscount、ProximityDiscount、MaximumCoverage和LabeledNewGreedy之執行時間比較。 35 表目錄表4.1：Dataset裡面不同Label的演員之數量 27 zh_TW dc.format.extent 1373426 bytes - dc.format.mimetype application/pdf - dc.language.iso en_US - dc.source.uri (資料來源) http://thesis.lib.nccu.edu.tw/record/#G0097753017 en_US dc.subject (關鍵詞) 標籤社會網絡 zh_TW dc.subject (關鍵詞) 影響力 zh_TW dc.subject (關鍵詞) 社會網絡 zh_TW dc.subject (關鍵詞) 極大化 zh_TW dc.subject (關鍵詞) Labeled influence maximization en_US dc.subject (關鍵詞) Influence maximization en_US dc.subject (關鍵詞) Social network en_US dc.title (題名) 利用標籤社會網絡之影響力最大化達到目標式廣告行銷 zh_TW dc.title (題名) Influence maximization in labeled social network for target advertising en_US dc.type (資料類型) thesis en dc.relation.reference (參考文獻) [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. zh_TW
