社交網路循序互動樣式之探勘

Abstract

由於網際網路技術的進步，社群網路迅速崛起。許多社群網路包括數以百萬計的使用者，人們在社群網路中的互動累積成為一個龐大的資料庫。如何從社群網路的互動資料庫中找出人們互動的樣式，已成為重要的研究議題。探勘社群網路中的互動樣式，可幫助我們分析使用者的行為模式，提升經營社群網路的技術，規劃行銷與廣告策略等等。因此，在本篇論文中，我們提出了一個演算法叫「MSIP」，以探勘在社群網路資料庫中使用者的互動樣式。MSIP演算法主要可以分成兩個步驟，首先，搜尋整個資料庫來找出所有長度為一的頻繁樣式，並且建立這些頻繁樣式的投影資料庫。然後，利用深度優先搜尋法產生所有的頻繁樣式。在搜尋的過程中，我們設計三個有效的修剪策略以刪除不可能的候選樣式，以及利用一個封閉性檢查機制移除非最大樣式。因此，MSIP演算法可以有效地探勘社群網路中的互動樣式。實驗結果顯示在執行速度和記憶體使用量上，MSIP演算法均優於改良式的MSPX演算法。

With advance of web technology, many social networks have been highly developed in recent years. A large amount of interactions between users in a social network have been collected into databases. Mining interaction patterns in social networks can help us to analyze user’s interactions and behavior, promote the technologies of running social networks, and formulate marketing and advertisement strategies. Therefore, in this thesis, we propose an efficient method, called MSIP (Maximal Sequential Interaction Patterns), to mine maximal interaction patterns in social network databases. The proposed algorithm consisted of two phases. First, we scan the database to find all frequent patterns of length one (1-patterns) and generate the projected database for each frequent 1-patterns. Next, we recursively mine all frequent patterns in a depth-first search (DFS) manner until no more frequent patterns can be found. During mining process, we employ three effective pruning strategies to prune unnecessary candidates and a closure checking scheme to remove non-maximal frequent patterns. Therefore, the proposed method can efficiently mine interaction patterns in social networks. The experimental results show that the MSIP algorithm outperforms the modified MSPX algorithm.