1. NCCU Academic Hub
  2. Publications
  3. College of Informatics
  4. Theses
  5. Item

Publications-Theses

Article View/Open

Publication Export

Google ScholarTM

NCCU Library

Citation Infomation

Related Publications in TAIR

題名 利用標籤社會網絡之影響力最大化達到目標式廣告行銷
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 (日期) 2010en_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) G0097753017en_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 (描述) 97753017zh_TW
dc.description (描述) 99zh_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
第二章 相關研究 4
2.1 Influence Maximization 4
2.2 Independent Cascade Model 6
2.3 Weighted Cascade Model 8
第三章 研究方法 9
3.1 問題定義 9
3.2 LabeledGreedy Algorithm 10
3.2 LabeledCELFGreedy Algorithm 13
3.3 LabeledNewGreedy Algorithm 14
3.4 LabeledDegreeDiscount 16
3.5 ProximityDiscount 18
3.5.1 Proximity for Independent Cascade Model 18
3.5.2 Computing Proximity 19
3.5.3 ProximityDiscount Algorithm 21
3.6 MaximumCoverage 24
3.7 Proximity Threshold and Maximum Coverage Threshold 25
第四章 實驗結果與評估 27
4.1 實驗設計 27
4.2 實驗結果 28
第五章 結論與未來研究方向 36
5.1 結論 36
5.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/#G0097753017en_US
dc.subject (關鍵詞) 標籤社會網絡zh_TW
dc.subject (關鍵詞) 影響力zh_TW
dc.subject (關鍵詞) 社會網絡zh_TW
dc.subject (關鍵詞) 極大化zh_TW
dc.subject (關鍵詞) Labeled influence maximizationen_US
dc.subject (關鍵詞) Influence maximizationen_US
dc.subject (關鍵詞) Social networken_US
dc.title (題名) 利用標籤社會網絡之影響力最大化達到目標式廣告行銷zh_TW
dc.title (題名) Influence maximization in labeled social network for target advertisingen_US
dc.type (資料類型) thesisen
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