近年來社群網路有著蓬勃的發展,社群網路的分析也隨之變成熱門的主題,社群網路中的成員,通常藉由由一個或多個特定類型的相互依存關係而連結在一起,如價值觀、理想、觀念、友誼、血緣、合作等等關係。在社群網路上有一種獨特的特性,我們稱之為社群結構,在同一個社群裡的成員彼此之間會有更多的共同關係和互動,而了解社群結構可以發掘更多有用的資訊。在過去已有許多研究可以在靜態的網路中檢測社群結構,然而社群網路上的使用者以及使用者之間的關係會隨著時間而變動,我們提出有效率的追溯與動態更新社群結構的方法,導入核心社群結構的概念,在不同時間點上追溯核心社群結構的變化,發掘動態的社群結構上。
我們以基於Clique的演算法做為基礎,將現有的CPM演算法做出改良,使用3-Cliques為基礎,接著以該核心社群結構為已知的資訊,在新的時間點的社群網路上追溯這些已知的資訊以便得知社群網路的變化。為了達到有效率的更新和追溯,針對有變化的部分,我們提出Clique Adjacent Bipartite Graph (CAB graph)來記錄Cliques,並將核心社群結構轉換成此資料結構來表示,透過此特殊資料結構的特性以提高追溯的效率,發展出有效率的動態更新演算法,所以我們將運用不同的資料結構來檢測社群,使得基於Clique的方法複雜度降至最低,其成果發表於ACM SIGKDD Conference的SNAKDD workshop中。