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

題名 利用資訊串流探勘社群網路中的多樣角色
Discovering various roles from social networks by information cascade
作者 曾智煒
Tzeng, Chih Wei
貢獻者 陳良弼
Chen, Arbee L.P.
曾智煒
Tzeng, Chih Wei
關鍵詞 路徑探勘
社群網路
領袖探索
Path Mining,
Social Network,
Leader Discovery
日期 2010
上傳時間 4-Sep-2013 18:15:07 (UTC+8)
摘要 由於近年社群網路各種應用網站興起，像是Facebook、Twitter，等，相關議
題也逐漸受到討論，例如越來越多利用社群網路傳播訊息或者病毒式行銷的相關
研究。當我們能夠找出一個社群網路當中，習慣的傳播模式或者是傳播路徑，並
且能從中定位各種角色的重要性，進一步在社群網路中找出這些角色後，在這些
相關的議題的應用將更加靈活。
目前各大社群網路應用網站，使用者都可以與社群網路中的好友分享自己的
動作，例如發佈影片或圖片，評論，按「讚」等，基於這樣的前提使用者的任何
活動是有機會被社群網路中的好友影響，因此我們定義好友間影響的可能性，以
及依觀察合理的定義出社群網路中較為重要的角色。
我們的演算法經由收集使用者在固定社群網路應用網站的各種動作，加上動
作的時間所形成的動作誌(action log)，以及使用者們所構成的社群網路，可以從
社群網路中找出主要的資訊傳遞路徑以及各種不同限制下的領袖以及追隨者，並
且將會利用社群網路應用網站驗證分析我們所定義的角色成為結論。
Recently, social networking services and websites such as Facebook
and Twitter are taking more and more parts in our daily life. Issues
of influence propagation have been studied in recent years. To fill
in the gap of previous works, we aim to discover the main path
of influence and define the importance of leader in hierarchy on
the social graph. Social networking users are influenced by the
power of social networking service as they are able to post and
likevideos, pictures and comments. Therefore, in this study we
propose to discover the possibility of a relation and important roles by
mining social activities. After collecting performed action and time
stamp from different users and understanding their social network,
our framework was able to identify the main influence paths and
leaders under different constrains. Most importantly, our approach
outperforms both on precision/recall and ranking in realistic data.
參考文獻 [1] Charu C. Aggarwal, Yan Li, Jianyong Wang, and Jing Wang. Frequent pattern mining with uncertain data. In Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining,KDD `09, pages 29{38, New York, NY, USA, 2009. ACM.
[2] Charu C. Aggarwal and Philip S. Yu. A survey of uncertain data algorithms and applications. IEEE Trans. on Knowl. and Data Eng., 21:609{623, May 2009.
[3] Rakesh Agrawal and Ramakrishnan Srikant. Fast algorithms for mining association rules in large databases. In Proceedings of the 20th International Conference on Very Large Data Bases, VLDB `94, pages 487{499, San Francisco, CA, USA, 1994. Morgan Kaufmann Publishers Inc.
[4] Thomas Bernecker, Hans-Peter Kriegel, Matthias Renz, Florian Verhein, and Andreas Zuee. Probabilistic frequent itemset mining in uncertain databases.In Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, KDD `09, pages 119{128, New York,
NY, USA, 2009. ACM.
[5] Freimut Bodendorf and Carolin Kaiser. Detecting opinion leaders and trends in online social networks. In Proceeding of the 2nd ACM workshop on Social web search and mining, SWSM `09, pages 65{68, New York, NY, USA, 2009.ACM.
[6] Wei Chen, Yajun Wang, and Siyu Yang. Efficient in
uence maximization in social networks. In Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, KDD `09, pages 199{208, New York, NY, USA, 2009. ACM.
[7] Chun-Kit Chui, Ben Kao, and Edward Hung. Mining frequent itemsets from uncertain data. In Proceedings of the 11th Pacific-Asia conference on Advances in knowledge discovery and data mining, PAKDD`07, pages 47{58, Berlin, Heidelberg, 2007. Springer-Verlag.
[8] Ilham Esslimani, Armelle Brun, and Anne Boyer. Detecting leaders in behavioral networks. In Proceedings of the 2010 International Conference on Advances in Social Networks Analysis and Mining, ASONAM `10, pages281{285, Washington, DC, USA, 2010. IEEE Computer Society.
[9] Manuel Gomez Rodriguez, Jure Leskovec, and Andreas Krause. Inferring networks of diffusion and influence. In Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining, KDD`10, pages 1019{1028, New York, NY, USA, 2010. ACM.
[10] Amit Goyal, Francesco Bonchi, and Laks V.S. Lakshmanan. Discovering leaders from community actions. In Proceeding of the 17th ACM conference on Information and knowledge management, CIKM `08, pages 499{508, New York, NY, USA, 2008. ACM.
[11] Amit Goyal, Francesco Bonchi, and Laks V.S. Lakshmanan. Learning influence probabilities in social networks. In Proceedings of the third ACM international conference on Web search and data mining, WSDM `10, pages 241{250, New York, NY, USA, 2010. ACM.
[12] David Kempe, Jon Kleinberg, and Eva Tardos. Maximizing the spread of influence through a social network. In Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining,KDD `03, pages 137{146, New York, NY, USA, 2003. ACM.
[13] Xiaodan Song, Yun Chi, Koji Hino, and Belle Tseng. Identifying opinion leaders in the blogosphere. In Proceedings of the sixteenth ACM conference on Conference on information and knowledge management, CIKM `07, pages 971{974, New York, NY, USA, 2007. ACM.
[14] Liwen Sun, Reynold Cheng, David W. Cheung, and Jiefeng Cheng. Mining uncertain data with probabilistic guarantees. In Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining, KDD `10, pages 273{282, New York, NY, USA, 2010. ACM.
[15] Zhongwu Zhai, Hua Xu, and Peifa Jia. Identifying opinion leaders in bbs. In Proceedings of the 2008 IEEE/WIC/ACM International Conference on Web Intelligence and Intelligent Agent Technology - Volume 03, pages 398{401,
Washington, DC, USA, 2008. IEEE Computer Society.4
描述 碩士
國立政治大學
資訊科學學系
98753001
99
資料來源 http://thesis.lib.nccu.edu.tw/record/#G0098753001
資料類型 thesis
dc.contributor.advisor 陳良弼zh_TW
dc.contributor.advisor Chen, Arbee L.P.en_US
dc.contributor.author (Authors) 曾智煒zh_TW
dc.contributor.author (Authors) Tzeng, Chih Weien_US
dc.creator (作者) 曾智煒zh_TW
dc.creator (作者) Tzeng, Chih Weien_US
dc.date (日期) 2010en_US
dc.date.accessioned 4-Sep-2013 18:15:07 (UTC+8)-
dc.date.available 4-Sep-2013 18:15:07 (UTC+8)-
dc.date.issued (上傳時間) 4-Sep-2013 18:15:07 (UTC+8)-
dc.identifier (Other Identifiers) G0098753001en_US
dc.identifier.uri (URI) http://nccur.lib.nccu.edu.tw/handle/140.119/60267-
dc.description (描述) 碩士zh_TW
dc.description (描述) 國立政治大學zh_TW
dc.description (描述) 資訊科學學系zh_TW
dc.description (描述) 98753001zh_TW
dc.description (描述) 99zh_TW
dc.description.abstract (摘要) 由於近年社群網路各種應用網站興起，像是Facebook、Twitter，等，相關議
題也逐漸受到討論，例如越來越多利用社群網路傳播訊息或者病毒式行銷的相關
研究。當我們能夠找出一個社群網路當中，習慣的傳播模式或者是傳播路徑，並
且能從中定位各種角色的重要性，進一步在社群網路中找出這些角色後，在這些
相關的議題的應用將更加靈活。
目前各大社群網路應用網站，使用者都可以與社群網路中的好友分享自己的
動作，例如發佈影片或圖片，評論，按「讚」等，基於這樣的前提使用者的任何
活動是有機會被社群網路中的好友影響，因此我們定義好友間影響的可能性，以
及依觀察合理的定義出社群網路中較為重要的角色。
我們的演算法經由收集使用者在固定社群網路應用網站的各種動作，加上動
作的時間所形成的動作誌(action log)，以及使用者們所構成的社群網路，可以從
社群網路中找出主要的資訊傳遞路徑以及各種不同限制下的領袖以及追隨者，並
且將會利用社群網路應用網站驗證分析我們所定義的角色成為結論。		zh_TW
dc.description.abstract (摘要) Recently, social networking services and websites such as Facebook
and Twitter are taking more and more parts in our daily life. Issues
of influence propagation have been studied in recent years. To fill
in the gap of previous works, we aim to discover the main path
of influence and define the importance of leader in hierarchy on
the social graph. Social networking users are influenced by the
power of social networking service as they are able to post and
likevideos, pictures and comments. Therefore, in this study we
propose to discover the possibility of a relation and important roles by
mining social activities. After collecting performed action and time
stamp from different users and understanding their social network,
our framework was able to identify the main influence paths and
leaders under different constrains. Most importantly, our approach
outperforms both on precision/recall and ranking in realistic data.		en_US
dc.description.tableofcontents 1 Introduction 5
1.1 Background and Motivation . . . . . . . . . . . . . . 5
1.2 Methodology Outline . . . . . . . . . . . . . . . . . . 7
1.3 Contributions . . . . . . . . . . . . . . . . . . . . . . 8
2 Related Work 10
2.1 In
uence on the Social Network . . . . . . . . . . . . 10
2.1.1 In
uence Maximization . . . . . . . . . . . . . 11
2.1.2 In
uence via Actions Information . . . . . . . 12
2.1.3 leader detection . . . . . . . . . . . . . . . . . 14
2.2 Uncertain Frequent Itemsets . . . . . . . . . . . . . . 15
2.2.1 Uncertain Frequent Itemsets with Expected
Support . . . . . . . . . . . . . . . . . . . . . 16
2.2.2 Uncertain frequent itemsets with probability
guarantee on support counts . . . . . . . . . . 17
3 Methodolagy 18
3.1 Problem Fomulation . . . . . . . . . . . . . . . . . . 18
3.2 Framework . . . . . . . . . . . . . . . . . . . . . . . . 22
3.3 Apriori Probabilistic Path Mining(APPM) . . . . . . 23
3.4 Various Roles Discovery . . . . . . . . . . . . . . . . 26
3.4.1 Discovering N-chain Leaders . . . . . . . . . . 26
3.4.2 Loyalty of a user . . . . . . . . . . . . . . . . 28
4 Experiment 30
4.1 Experiment Setup . . . . . . . . . . . . . . . . . . . . 30
4.2 In
uence Path Analysis . . . . . . . . . . . . . . . . . 32
4.3 Various Roles Analysis . . . . . . . . . . . . . . . . . 33
4.3.1 Leader Validation . . . . . . . . . . . . . . . . 34
Validation Measure . . . . . . . . . . . . . . . 36
Result of Relevance . . . . . . . . . . . . . . . 37
Result of Leader Ranking . . . . . . . . . . . 38
5 Conclusions 41		zh_TW
dc.format.extent 2537381 bytes-
dc.format.mimetype application/pdf-
dc.language.iso en_US-
dc.source.uri (資料來源) http://thesis.lib.nccu.edu.tw/record/#G0098753001en_US
dc.subject (關鍵詞) 路徑探勘zh_TW
dc.subject (關鍵詞) 社群網路zh_TW
dc.subject (關鍵詞) 領袖探索zh_TW
dc.subject (關鍵詞) Path Mining,en_US
dc.subject (關鍵詞) Social Network,en_US
dc.subject (關鍵詞) Leader Discoveryen_US
dc.title (題名) 利用資訊串流探勘社群網路中的多樣角色zh_TW
dc.title (題名) Discovering various roles from social networks by information cascadeen_US
dc.type (資料類型) thesisen
dc.relation.reference (參考文獻) [1] Charu C. Aggarwal, Yan Li, Jianyong Wang, and Jing Wang. Frequent pattern mining with uncertain data. In Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining,KDD `09, pages 29{38, New York, NY, USA, 2009. ACM.
[2] Charu C. Aggarwal and Philip S. Yu. A survey of uncertain data algorithms and applications. IEEE Trans. on Knowl. and Data Eng., 21:609{623, May 2009.
[3] Rakesh Agrawal and Ramakrishnan Srikant. Fast algorithms for mining association rules in large databases. In Proceedings of the 20th International Conference on Very Large Data Bases, VLDB `94, pages 487{499, San Francisco, CA, USA, 1994. Morgan Kaufmann Publishers Inc.
[4] Thomas Bernecker, Hans-Peter Kriegel, Matthias Renz, Florian Verhein, and Andreas Zuee. Probabilistic frequent itemset mining in uncertain databases.In Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, KDD `09, pages 119{128, New York,
NY, USA, 2009. ACM.
[5] Freimut Bodendorf and Carolin Kaiser. Detecting opinion leaders and trends in online social networks. In Proceeding of the 2nd ACM workshop on Social web search and mining, SWSM `09, pages 65{68, New York, NY, USA, 2009.ACM.
[6] Wei Chen, Yajun Wang, and Siyu Yang. Efficient in
uence maximization in social networks. In Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, KDD `09, pages 199{208, New York, NY, USA, 2009. ACM.
[7] Chun-Kit Chui, Ben Kao, and Edward Hung. Mining frequent itemsets from uncertain data. In Proceedings of the 11th Pacific-Asia conference on Advances in knowledge discovery and data mining, PAKDD`07, pages 47{58, Berlin, Heidelberg, 2007. Springer-Verlag.
[8] Ilham Esslimani, Armelle Brun, and Anne Boyer. Detecting leaders in behavioral networks. In Proceedings of the 2010 International Conference on Advances in Social Networks Analysis and Mining, ASONAM `10, pages281{285, Washington, DC, USA, 2010. IEEE Computer Society.
[9] Manuel Gomez Rodriguez, Jure Leskovec, and Andreas Krause. Inferring networks of diffusion and influence. In Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining, KDD`10, pages 1019{1028, New York, NY, USA, 2010. ACM.
[10] Amit Goyal, Francesco Bonchi, and Laks V.S. Lakshmanan. Discovering leaders from community actions. In Proceeding of the 17th ACM conference on Information and knowledge management, CIKM `08, pages 499{508, New York, NY, USA, 2008. ACM.
[11] Amit Goyal, Francesco Bonchi, and Laks V.S. Lakshmanan. Learning influence probabilities in social networks. In Proceedings of the third ACM international conference on Web search and data mining, WSDM `10, pages 241{250, New York, NY, USA, 2010. ACM.
[12] David Kempe, Jon Kleinberg, and Eva Tardos. Maximizing the spread of influence through a social network. In Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining,KDD `03, pages 137{146, New York, NY, USA, 2003. ACM.
[13] Xiaodan Song, Yun Chi, Koji Hino, and Belle Tseng. Identifying opinion leaders in the blogosphere. In Proceedings of the sixteenth ACM conference on Conference on information and knowledge management, CIKM `07, pages 971{974, New York, NY, USA, 2007. ACM.
[14] Liwen Sun, Reynold Cheng, David W. Cheung, and Jiefeng Cheng. Mining uncertain data with probabilistic guarantees. In Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining, KDD `10, pages 273{282, New York, NY, USA, 2010. ACM.
[15] Zhongwu Zhai, Hua Xu, and Peifa Jia. Identifying opinion leaders in bbs. In Proceedings of the 2008 IEEE/WIC/ACM International Conference on Web Intelligence and Intelligent Agent Technology - Volume 03, pages 398{401,
Washington, DC, USA, 2008. IEEE Computer Society.4		zh_TW