Publications-Theses
Article View/Open
Publication Export
-
題名 結合背景影響與群眾參與之社群事件規模及其應用
Social Event Magnitudes via Background Influences and Engagement Capacities and its Applications作者 劉奎谷
Liu, Kwei-Guu貢獻者 劉吉軒
Liu, Jyi-Shane
劉奎谷
Liu, Kwei-Guu關鍵詞 事件偵測
非回溯矩陣
社群參與
譜演算法
Online event detection
Engagement capacities
Non-backtracking matrix
Spectral algorithms日期 2019 上傳時間 4-Mar-2019 21:42:56 (UTC+8) 摘要 了解社群事件爆發(例如，阿拉伯之春)已是社群計算領域中受到廣泛重視的研究分支之一，因為除了社群事件偵測的相關應用多元之外，其亦與資訊擴散相關研究有著密切關係。社群事件的發生可從兩個角度來觀察: 一為資訊的異常變化(例如，關鍵文字於短時間內的暴增) 、二為活動的人氣高低(例如，資訊分享) 。事件偵測演算法通常針對前者中的異常變化進行設計，而社群事件強度則是透過統計方法針對分享的人氣高低提供一測度。換言之，社群事件強度提供了人們一個較為直覺的數值表達方式，藉由該數可易於瞭解事件在某個時空下的程度。然而，與事件偵測演算法相較下，社群事件強度於應用上有其劣勢: 一為其仰賴轉發數據、二為不易整合資訊進行估測。因此，本研究受事件偵測演算設計的啟發，提出了另一測度的表達方式，謂之為社群事件規模。社群事件規模的計算概念為某一時段內背景影響與群眾參與的乘值；背景影響值的抽取乃是應用非回溯矩陣從文字資訊中取出，而群眾參與的計算則是將網絡結構轉化為社群參與值(亦為Ordered Shapley Value)而得出。因此，社群事件規模的優勢，如事件偵測演算一樣，可整合資訊，且如社群事件強度一樣，可提供一個了解社群事件程度的概念性數字。此外，社群事件規模的計算也提供了另一資訊整合方式，有別於常用的相似度整合資訊的方法。另，本研究示範如何將社群事件規模應用在非特定事件與特定事件的動態偵測。於非特定事件動態偵測實驗，本研究發現社群事件規模呈現長尾分佈，而此分佈常見於社會活動現象。此外，因社群事件規模為一數值，故可提供簡便的視覺呈現來了解事件程度的動態變化。於特定事件偵測實驗方面，社群事件規模亦可有效率地偵測出指定事件。
Detecting outbreaks of social events (e.g., Arab Spring) has been an active research area in social computing, because of its close relationship to the research of information diffusion. Outbreaks of social events can be viewed from two angles: 1. anomalous changes of information (e.g., an influx of text), and 2. popular actions (e.g., retweets). Event detection algorithms focus on extracting anomalous information, while popular actions are measured by estimating social event intensity, which is a rate to show how popular an action is in a social network during a short period. The rate is relatively intuitive and gives a holistic view about activity levels in a network, but it has a few disadvantages. First, its estimation cannot work without the information about numbers of shares. Second, the estimation isn’t easy. Inspired by event detection algorithms, this study proposes an alternative measure using the product of background influence and cooperation value in a fixed time interval, and it is called social event magnitude. Background influence is extracted from text via non-backtracking matrices, and cooperation value is obtained via social engagement capacities, a modified version of Shapley value. The proposed alternative gives a holistic view about activity levels in a network. The construction of proposed alternative shows another way to integrate multiple sources of information for event detection. We demonstrated social event magnitude on specified and unspecified online event detections. In the specified detection, the alternative has a better performance in precision-recall evaluation. In the unspecified detection, social event magnitudes follow a long-tailed distribution. Furthermore, social event magnitudes can be visualized for changing levels of activities.參考文獻 [1] C. Zhang, G. Zhou, Q. Yuan, H. Zhuang, Y. Zheng, L. Kaplan, S. Wang and J. Han, "GeoBurst: Real-Time Local Event Detection in Geo-Tagged Tweet Streams," in ACM Special Interest Group on Information Retrieval, Pisa, Italy, 2016.[2] T. Sakaki, M. Okazaki and Y. Matsuo, "Earthquake Shakes Twitter Users: Real-Time Event Detection by Social Sensors," in World Wide Web, Raleigh, North Carolina, USA, 2010.[3] C. Aggarwal and K. Subbian, "Event Detection in Social Streams," in Society for Industrial and Applied Mathematics Data Mining, Anaheim, CA, USA, 2012.[4] M. Cordeiro and J. Gama, "Online Social Networks Event Detection: A Survey," in Solving Large Scale Learning Tasks. Challenges and Algorithms, Springer, 2016, pp. 1-41.[5] S. Ranshous, S. Shen, D. Kourtra, S. Harenberg, C. Faloutsos and N. Samatova, "Anomaly Detection in Dynamic Networks: A Survey," Wiley Interdisciplinary Reviews: Computational Statistics, vol. 7, no. May, pp. 223-247, 2015.[6] Q. Zhao, M. Erdogdu, H. He, A. Rajaraman and J. Leskovec, "SEISMIC: A Self-Exciting Point Process Model for Predicting Tweet Popularity," in ACM Knowledge Discovery and Data Mining, Sydney, 2015.[7] M.-A. Rizoiu, Y. Lee, S. Mishra and L. Xie, "Hawkes Processes for Events in Social Media," in Frontiers of Multimedia Research, New York, ACM, 2018, pp. 191-218.[8] W. W. Cohen, "Enron Email Dataset," Carnegie Mellon University, 8 May 2015. [Online]. Available: https://www.cs.cmu.edu/~enron/. [Accessed 10 July 2018].[9] Y. Ogata, "Statistical Models for Earthquake Occurrences and Residual Analysis for Point Processes," Journal of the American Statistical Association, vol. 83, no. 401, pp. 9-27, 1985.[10] A. G. Hawkes, "Hawke Processes and their Applications to Finance: Review," Quantitative Finance, vol. 18, no. 2, pp. 193-198, 2018.[11] M.-A. Rizoiu, L. Xie, S. Sanner, M. Cebrian, H. Yu and P. V. Henteryck, "Expecting to be HIP: Hawkes Intensity Processses for Social Media Popularity," in World Wide Web, Perth, Australia, 2017.[12] R. Kobayashi and R. Lambiotte, "TiDeH: Time-Dependent Hawkes Process for Predicting Retweet Dynamics," in International Conference on Web and Social Media, Cologne, Germany, 2016.[13] M. Farajtabar, N. Du, M. Gomez-Rodriguez, I. Valera, H. Zha and L. Song, "Shaping Social Activity by Incentivizing Users," in Neural Information Processing Systems , Montreal, Canada, 2014.[14] T. Martin, X. Zhang and M. E. J. Newman, "Localization and Centrality in Networks," Physical Review E, vol. 90, no. 5, p. 052808, 2014.[15] F. Krzakala, C. Moore, E. Mossel, J. Neeman, A. Sly, L. Zdeborova and P. Zhang, "Spectral Redemption: Clustering Sparse Networks," Proceedings of the National Academy of Sciences of the United States of America, vol. 110, no. 52, pp. 20935-20940, 24 December 2013.[16] N. Alon, I. Benjamini, E. Lubetzky and S. Sodin, "Non-backtracking Random Walks Mix Faster," Communications in Contemporary Mathematics, vol. 9, no. 4, pp. 585-603, 2007.[17] O. Angel, J. Friedman and S. Hoory, "The Non-backtracking Spectrum of the Universal Cover of a Graph," Transactions of The American Mathematical Society, vol. 367, no. 6, pp. 4287-4318, 2015.[18] R. R. Nadakudiu and M. E. J. Newman, "Graph Spectra and Detectability of Community Structure in Networks," Physical Review Letters, vol. 108, no. 18, p. 188701, 2012.[19] T. Tao, Topics in Random Matrix Theory, Rhode Island: American Mathematical Society, 2012.[20] F. Chung, L. Lu and V. Vu, "The Spectra of Random Graphs with Given Expected Degrees," Proceedings of the National Academy of Sciences of the United States of America, vol. 100, no. 11, pp. 6313-6318, 2003.[21] C. Moore, "The Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardness," European Association for Theoretical Computer Science, vol. 121, no. February, 2017.[22] A. Decelle, F. Krzakala, C. Moore and L. Zdeborova, "Asymptotic Analysis of the Stochastic Block Model for Modular Networks and its Algorithmic Applications," Physical Review E, vol. 84, no. 6, p. 066106, 2011.[23] C. Bordenave, M. Lelarge and L. Massoulie, "Non-backtracking Spectrum of Random Graphs: Community Detection and Non-regular Ramanujan Graphs," in Symposium on Foundations of Computer Science, Berkeley, CA, USA, 2015.[24] A. Nikolaev, S. Gore and V. Govindaraju, "Engagement Capacity and Engaging Team Formation for Reach Maximization of Online Social Media Platforms," in ACM Knowledge Discovery and Data Mining, San Francisco, CA, USA, 2016.[25] R. P. Gilles, The Cooperative Game Theory of Networks and Hierarchies, Berlin Heidelberg: Springer, 2010.[26] Y. Yang, T. Pierce and J. Carbonell, "A Study on Retrospective and On-Line Event Detection," in ACM Special Interest Group in Information Retrieval, Melbourne, Australia, 1998.[27] S. Kumar, H. Liu, S. Metha and L. Subramaniam, "Exploring a Scalable Solution to Identifying Events in Noisy Twitter Streams," in ACM Advances in Social Networks Analysis and Mining, Paris, France, 2015.[28] X. Dong, D. Mavroeidis, F. Calabrese and P. Frossard, "Multiscale Event Detection in Social Media," Data Mining and Knowledge Discovery, vol. 29, no. 5, pp. 1374-1405, 2015.[29] M. Newman, "Networks: An Introduction," Oxford University Press, New York, NY, USA, 2010.[30] Z. Bai, J. Demmel, J. Dongarra, A. Ruhe and H. Vorst, Templates for the Solution of Algebraic Eigenvalue Problems: A Practical Guide, Philadelphia: Society for Industrial and Applied Mathematics, 2000. 描述 碩士
國立政治大學
資訊科學系
105753030資料來源 http://thesis.lib.nccu.edu.tw/record/#G0105753030 資料類型 thesis dc.contributor.advisor 劉吉軒 zh_TW dc.contributor.advisor Liu, Jyi-Shane en_US dc.contributor.author (Authors) 劉奎谷 zh_TW dc.contributor.author (Authors) Liu, Kwei-Guu en_US dc.creator (作者) 劉奎谷 zh_TW dc.creator (作者) Liu, Kwei-Guu en_US dc.date (日期) 2019 en_US dc.date.accessioned 4-Mar-2019 21:42:56 (UTC+8) - dc.date.available 4-Mar-2019 21:42:56 (UTC+8) - dc.date.issued (上傳時間) 4-Mar-2019 21:42:56 (UTC+8) - dc.identifier (Other Identifiers) G0105753030 en_US dc.identifier.uri (URI) http://nccur.lib.nccu.edu.tw/handle/140.119/122397 - dc.description (描述) 碩士 zh_TW dc.description (描述) 國立政治大學 zh_TW dc.description (描述) 資訊科學系 zh_TW dc.description (描述) 105753030 zh_TW dc.description.abstract (摘要) 了解社群事件爆發(例如，阿拉伯之春)已是社群計算領域中受到廣泛重視的研究分支之一，因為除了社群事件偵測的相關應用多元之外，其亦與資訊擴散相關研究有著密切關係。社群事件的發生可從兩個角度來觀察: 一為資訊的異常變化(例如，關鍵文字於短時間內的暴增) 、二為活動的人氣高低(例如，資訊分享) 。事件偵測演算法通常針對前者中的異常變化進行設計，而社群事件強度則是透過統計方法針對分享的人氣高低提供一測度。換言之，社群事件強度提供了人們一個較為直覺的數值表達方式，藉由該數可易於瞭解事件在某個時空下的程度。然而，與事件偵測演算法相較下，社群事件強度於應用上有其劣勢: 一為其仰賴轉發數據、二為不易整合資訊進行估測。因此，本研究受事件偵測演算設計的啟發，提出了另一測度的表達方式，謂之為社群事件規模。社群事件規模的計算概念為某一時段內背景影響與群眾參與的乘值；背景影響值的抽取乃是應用非回溯矩陣從文字資訊中取出，而群眾參與的計算則是將網絡結構轉化為社群參與值(亦為Ordered Shapley Value)而得出。因此，社群事件規模的優勢，如事件偵測演算一樣，可整合資訊，且如社群事件強度一樣，可提供一個了解社群事件程度的概念性數字。此外，社群事件規模的計算也提供了另一資訊整合方式，有別於常用的相似度整合資訊的方法。另，本研究示範如何將社群事件規模應用在非特定事件與特定事件的動態偵測。於非特定事件動態偵測實驗，本研究發現社群事件規模呈現長尾分佈，而此分佈常見於社會活動現象。此外，因社群事件規模為一數值，故可提供簡便的視覺呈現來了解事件程度的動態變化。於特定事件偵測實驗方面，社群事件規模亦可有效率地偵測出指定事件。 zh_TW dc.description.abstract (摘要) Detecting outbreaks of social events (e.g., Arab Spring) has been an active research area in social computing, because of its close relationship to the research of information diffusion. Outbreaks of social events can be viewed from two angles: 1. anomalous changes of information (e.g., an influx of text), and 2. popular actions (e.g., retweets). Event detection algorithms focus on extracting anomalous information, while popular actions are measured by estimating social event intensity, which is a rate to show how popular an action is in a social network during a short period. The rate is relatively intuitive and gives a holistic view about activity levels in a network, but it has a few disadvantages. First, its estimation cannot work without the information about numbers of shares. Second, the estimation isn’t easy. Inspired by event detection algorithms, this study proposes an alternative measure using the product of background influence and cooperation value in a fixed time interval, and it is called social event magnitude. Background influence is extracted from text via non-backtracking matrices, and cooperation value is obtained via social engagement capacities, a modified version of Shapley value. The proposed alternative gives a holistic view about activity levels in a network. The construction of proposed alternative shows another way to integrate multiple sources of information for event detection. We demonstrated social event magnitude on specified and unspecified online event detections. In the specified detection, the alternative has a better performance in precision-recall evaluation. In the unspecified detection, social event magnitudes follow a long-tailed distribution. Furthermore, social event magnitudes can be visualized for changing levels of activities. en_US dc.description.tableofcontents ACKNOWLEDGEMENT III摘要 IVABSTRACT VLIST OF FIGURES VIIILIST OF TABLES IX1. Introduction 11.1. Background 11.2. Motivation and Objective 31.3. Data 42. Related Research 52.1. Social Event Intensity 52.2. Non-backtracking Matrix 72.3. Engagement Capacity 153. Algorithmic Design 193.1. Observation 193.2. Flow of Procedure 214. Experiments 304.1. Experimental Preparation 304.2. Results of Online Unspecified Event Detection 324.3. Results of Online Specified Event Detection 365. Conclusion and Future Work 455.1. Conclusion 455.2. Future Work 46References 48 zh_TW dc.format.extent 2378771 bytes - dc.format.mimetype application/pdf - dc.source.uri (資料來源) http://thesis.lib.nccu.edu.tw/record/#G0105753030 en_US dc.subject (關鍵詞) 事件偵測 zh_TW dc.subject (關鍵詞) 非回溯矩陣 zh_TW dc.subject (關鍵詞) 社群參與 zh_TW dc.subject (關鍵詞) 譜演算法 zh_TW dc.subject (關鍵詞) Online event detection en_US dc.subject (關鍵詞) Engagement capacities en_US dc.subject (關鍵詞) Non-backtracking matrix en_US dc.subject (關鍵詞) Spectral algorithms en_US dc.title (題名) 結合背景影響與群眾參與之社群事件規模及其應用 zh_TW dc.title (題名) Social Event Magnitudes via Background Influences and Engagement Capacities and its Applications en_US dc.type (資料類型) thesis en_US dc.relation.reference (參考文獻) [1] C. Zhang, G. Zhou, Q. Yuan, H. Zhuang, Y. Zheng, L. Kaplan, S. Wang and J. Han, "GeoBurst: Real-Time Local Event Detection in Geo-Tagged Tweet Streams," in ACM Special Interest Group on Information Retrieval, Pisa, Italy, 2016.[2] T. Sakaki, M. Okazaki and Y. Matsuo, "Earthquake Shakes Twitter Users: Real-Time Event Detection by Social Sensors," in World Wide Web, Raleigh, North Carolina, USA, 2010.[3] C. Aggarwal and K. Subbian, "Event Detection in Social Streams," in Society for Industrial and Applied Mathematics Data Mining, Anaheim, CA, USA, 2012.[4] M. Cordeiro and J. Gama, "Online Social Networks Event Detection: A Survey," in Solving Large Scale Learning Tasks. Challenges and Algorithms, Springer, 2016, pp. 1-41.[5] S. Ranshous, S. Shen, D. Kourtra, S. Harenberg, C. Faloutsos and N. Samatova, "Anomaly Detection in Dynamic Networks: A Survey," Wiley Interdisciplinary Reviews: Computational Statistics, vol. 7, no. May, pp. 223-247, 2015.[6] Q. Zhao, M. Erdogdu, H. He, A. Rajaraman and J. Leskovec, "SEISMIC: A Self-Exciting Point Process Model for Predicting Tweet Popularity," in ACM Knowledge Discovery and Data Mining, Sydney, 2015.[7] M.-A. Rizoiu, Y. Lee, S. Mishra and L. Xie, "Hawkes Processes for Events in Social Media," in Frontiers of Multimedia Research, New York, ACM, 2018, pp. 191-218.[8] W. W. Cohen, "Enron Email Dataset," Carnegie Mellon University, 8 May 2015. [Online]. Available: https://www.cs.cmu.edu/~enron/. [Accessed 10 July 2018].[9] Y. Ogata, "Statistical Models for Earthquake Occurrences and Residual Analysis for Point Processes," Journal of the American Statistical Association, vol. 83, no. 401, pp. 9-27, 1985.[10] A. G. Hawkes, "Hawke Processes and their Applications to Finance: Review," Quantitative Finance, vol. 18, no. 2, pp. 193-198, 2018.[11] M.-A. Rizoiu, L. Xie, S. Sanner, M. Cebrian, H. Yu and P. V. Henteryck, "Expecting to be HIP: Hawkes Intensity Processses for Social Media Popularity," in World Wide Web, Perth, Australia, 2017.[12] R. Kobayashi and R. Lambiotte, "TiDeH: Time-Dependent Hawkes Process for Predicting Retweet Dynamics," in International Conference on Web and Social Media, Cologne, Germany, 2016.[13] M. Farajtabar, N. Du, M. Gomez-Rodriguez, I. Valera, H. Zha and L. Song, "Shaping Social Activity by Incentivizing Users," in Neural Information Processing Systems , Montreal, Canada, 2014.[14] T. Martin, X. Zhang and M. E. J. Newman, "Localization and Centrality in Networks," Physical Review E, vol. 90, no. 5, p. 052808, 2014.[15] F. Krzakala, C. Moore, E. Mossel, J. Neeman, A. Sly, L. Zdeborova and P. Zhang, "Spectral Redemption: Clustering Sparse Networks," Proceedings of the National Academy of Sciences of the United States of America, vol. 110, no. 52, pp. 20935-20940, 24 December 2013.[16] N. Alon, I. Benjamini, E. Lubetzky and S. Sodin, "Non-backtracking Random Walks Mix Faster," Communications in Contemporary Mathematics, vol. 9, no. 4, pp. 585-603, 2007.[17] O. Angel, J. Friedman and S. Hoory, "The Non-backtracking Spectrum of the Universal Cover of a Graph," Transactions of The American Mathematical Society, vol. 367, no. 6, pp. 4287-4318, 2015.[18] R. R. Nadakudiu and M. E. J. Newman, "Graph Spectra and Detectability of Community Structure in Networks," Physical Review Letters, vol. 108, no. 18, p. 188701, 2012.[19] T. Tao, Topics in Random Matrix Theory, Rhode Island: American Mathematical Society, 2012.[20] F. Chung, L. Lu and V. Vu, "The Spectra of Random Graphs with Given Expected Degrees," Proceedings of the National Academy of Sciences of the United States of America, vol. 100, no. 11, pp. 6313-6318, 2003.[21] C. Moore, "The Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardness," European Association for Theoretical Computer Science, vol. 121, no. February, 2017.[22] A. Decelle, F. Krzakala, C. Moore and L. Zdeborova, "Asymptotic Analysis of the Stochastic Block Model for Modular Networks and its Algorithmic Applications," Physical Review E, vol. 84, no. 6, p. 066106, 2011.[23] C. Bordenave, M. Lelarge and L. Massoulie, "Non-backtracking Spectrum of Random Graphs: Community Detection and Non-regular Ramanujan Graphs," in Symposium on Foundations of Computer Science, Berkeley, CA, USA, 2015.[24] A. Nikolaev, S. Gore and V. Govindaraju, "Engagement Capacity and Engaging Team Formation for Reach Maximization of Online Social Media Platforms," in ACM Knowledge Discovery and Data Mining, San Francisco, CA, USA, 2016.[25] R. P. Gilles, The Cooperative Game Theory of Networks and Hierarchies, Berlin Heidelberg: Springer, 2010.[26] Y. Yang, T. Pierce and J. Carbonell, "A Study on Retrospective and On-Line Event Detection," in ACM Special Interest Group in Information Retrieval, Melbourne, Australia, 1998.[27] S. Kumar, H. Liu, S. Metha and L. Subramaniam, "Exploring a Scalable Solution to Identifying Events in Noisy Twitter Streams," in ACM Advances in Social Networks Analysis and Mining, Paris, France, 2015.[28] X. Dong, D. Mavroeidis, F. Calabrese and P. Frossard, "Multiscale Event Detection in Social Media," Data Mining and Knowledge Discovery, vol. 29, no. 5, pp. 1374-1405, 2015.[29] M. Newman, "Networks: An Introduction," Oxford University Press, New York, NY, USA, 2010.[30] Z. Bai, J. Demmel, J. Dongarra, A. Ruhe and H. Vorst, Templates for the Solution of Algebraic Eigenvalue Problems: A Practical Guide, Philadelphia: Society for Industrial and Applied Mathematics, 2000. zh_TW dc.identifier.doi (DOI) 10.6814/THE.NCCU.CS.006.2019.B02 en_US
