運用關係萃取策略於動態社群探勘之研究

Abstract

近來在動態社會網路上，因為社群演化的廣大應用，動態社群的問題已經引起重大的關注。多數潛在的社會現象實際上可經由分析社群網路結構萃取出來。雖然在動態社群上已有多數的研究發表。它們一般而言均針對一連串的互動圖作社群分群，一連串的互動圖是通常用來表現動態社群網路的一種方式。然而互動圖展露在人與人之間的關係可能是不夠充足，因為它只是在一個時間切片上的快照。在這時間切片上兩人若沒有互動發生，並不代表這兩人沒有關係。本篇論文提出一個新穎的演算法，EPC(關係萃取和社群氏族的社群探勘者)，可被用來探勘社群演化。我們提出了一個關係萃取策略，在一個時間窗內產生出關係圖。EPC 架構於關係圖來產生社群分群，且利用社群氏族對映來發掘出動態社群在動態社群網路上的演化。實驗結果在合成資料和真實數據中顯示EPC 的結果不僅在準確度比之前的方法佳，且在彈性和平滑程度也勝過之前的方法。

Recently, considerable attention has been paid to the issue of dynamic community in dynamic social network due to its widespread applications. Many potential social phenomena, in practice, can be extracted by analyzing the dynamic social structure over time. Although there have been many recent studies proposed on dynamic community, these works, generally, partition the community based on a sequence of interaction graphs, which is usually applied to express a dynamic social network. Nevertheless, the interaction graph may be insufficient to reveal the relationship among individuals, since, in a snapshot of time slice, no interaction among individuals does not indicate no actual relationship. In this thesis, a novel algorithm EPC, which stands for relationship Extraction and community Pedigree mapping Community miner, is developed to mine the evolution of community. We present a Relationship Extraction strategy to construct a relationship graph within a defined observation window. EPC partitions communities based on relationship graph and uses proposed Community Pedigree Mapping method to discover the evolution of dynamic community in dynamic social network. The experimental results on synthetic and real datasets show that EPC not only significantly outperforms the prior studies in accuracy but also possesses graceful scalability and smoothness.