Event Identification for Social Streams using Keyword-based Evolving Graph Sequences

從關鍵字變動圖形序列識別社群資訊事件

關心怡(Kwan, Elizabeth)

指導教授 ： 陳宜欣

國立清華大學/電機資訊學院/資訊系統與應用研究所/碩士(2012年)

摘要

Social networks, which have become extremely popular nowadays, contains tremendous amount of user-generated content about real-world events. This user-generated content can naturally reflect the real-world event as they happen, and sometimes even ahead of newswire. This is why the content of social streams is particularly useful for event identification purposes. The goal of this work is to do event identification in social streams.

We proposed a model called Keyword-based Evolving Graph Sequences (kEGS) to capture the characteristic of social streams and how information propagates in the social streams. We use keywords to represent the contents of the message posted in the social streams. And, construct kEGS for each keyword, which contains the social structures and the time dimension. We also introduce the measurements we use on graphs constructed for event identification purposes. Finally, analyze the graphs by using the measurements introduced to identify events.

In this work, we use Twitter feeds as our source of social streams data. We have crawled Twitter site and collected over 7 million tweets, 13,000 users, and more than 5 million following relationship. Our experimental results show the usefulness of our approach for identifying real-world event in social streams.

關鍵字

事件識別 ； 事件偵測 ； 社群資訊 ； 社群網路 ； Twitter ； 圖形

並列摘要

社群網路在現今相當受到歡迎，它包含了大量使用者創造的內容。現實生活中的事件發生時，這些使用者創造的內容可以完整反映出事件，甚至較新聞媒體報導快速。這也是社群資訊在識別事件方面特別有效用的原因。本研究的目標是在社群資訊中識別事件。

在本研究中，我們建立了一個關鍵字圖形演變模型(Keyword-based Evolving Graph Sequences, kEGS)來擷取社群資訊的特性以及資訊如何在社群中傳播。我們使用關鍵字來表示社群資訊中的訊息內容。接著，為每一個關鍵字建立關鍵字演變圖形，圖形中包含了社群結構及時間維度資訊。同時，我們發展了一套圖形測量方法。最後，使用測量方法來分析關鍵字演變圖形以識別事件。

在本研究中，我們使用Twitter作為社群資訊來源。我們從Twitter收集了超過7,000,000則訊息、13,000筆使用者資訊以及超過5,000,000組關係。我們的實驗結果顯示，關鍵字圖形演變模型在社群資訊中識別事件是有效用的。

並列關鍵字

event identification ； event detection ； social stream ； social network ； Twitter ； graph

參考文獻

[1] J. Allan, editor. Topic Detection and Tracking: Event-based Information Organiza-

tion. Kluwer Academic Publ, 2002.

[4] M. Granovetter. The Strength of Weak Ties. The American Journal of Sociology,

[5] R. Kumar, J. Novak, and A. Tomkins. Structure and evolution of online social

networks, 2006.