以改良型基因演算法偵測動態社群網路之階層式重疊群聚結構之研究

Abstract

社群網路是由許多個體之間的互動關係所組成，當中這些個體常因背景或興趣的不同而各自聚成數個群聚，即形成群聚結構，而群聚結構又包括重疊與階層的群聚結構。此外，兩個體之間的互動關係會隨著時間而改變，因此動態社群網路群聚結構的偵測是個重要的議題。過去的方法中大都以兩階段的方式來解決重疊與階層群聚結構，但我們認為第二階段的偵測結果會受限於第一階段所得到的結果。因此，為了改進二階段偵測方式的瑕疵，本文提出具有挑戰性的一階段方式，同時偵測動態社群網路的重疊與階層群聚結構。而欲以一階段方式得到動態社群網路的重疊與階層群聚結構，我們提出了一個可同時最大化重疊與階層群聚結構品質的函式，並以改良型基因演算法搜尋最佳解，當中加入移民機制與區域搜尋提升求解效率。另外，本研究亦考量了社群容量及階層結構之階層數的門檻限制來增強所偵測群聚結構的品質。 實驗結果顯示，在兩個常用來衡量群聚結構品質的衡量指標下，我們所提出的改良型基因演算法皆較過去的方法所偵測出來的群聚結構有較佳的品質表現。此外，在模擬動態的社群網路中，階層式重疊群聚結構之變化亦可被觀察到。

Social network characterizes the relationship among people. Generally, those people are clustered into numerous communities due to their backgrounds or interests. The previous problems on detecting community structures for static and dynamic social networks can be classified into overlapping and hierarchical community structures. However, previous works are always using two-stage method to detect the hierarchical overlapping community structures. We think that the result of second stage will be limited to the first while using the two-stage methods. As a result, we proposed a one-stage method to detect overlapping and hierarchical community structure simultaneously with an optimizing function. In addition, we also concerned the capacity of each community and the threshold of each level in our problem. Due to optimizing community structure was proven to an N-P hard problem, this paper resolves this problem with a memetic algorithm, which is a genetic algorithm incorporated with a local search scheme. From the experimental results, we can find that our method can detect the social networks correctly while comparing with previous methods. Finally, the dynamic hierarchical overlapping community structures can be observed in the simulation case study.