利用區域式擴展與最佳化處理於重疊性社群結構之偵測與分析

Abstract

社群結構偵測為圖形探勘的重要問題，近年來更有許多研究者投入重疊性的社群結構偵測之研究，以回應現實世界網路中節點常同時隸屬於不只一個社群的狀況。本研究著重於基於區域式擴展與最佳化的重疊性社群結構偵測演算法。我們提出一架構以研究此特定種類之演算法，此架構包括數個議題：(1) 選取初始種子節點； (2) 社群擴展； (3) 精煉種子節點； (4) 後處理重覆社群、無主節點。本研究的主要貢獻為：(1) 基於節點間接鄰居與鄰居個數的新擴展函數，以提昇對於高度重疊社群偵測的表現； (2) 基於累加社群內各邊之中間性，將種子節點精煉的新方法，以減輕錯誤的種子節點之影響。

Community structure detection is an important problem in graph mining, and recently many researchers have been devoted to overlapping community structure detection to respond to real-work networks in which vertices often simultaneously belong to more than one community. This study focuses on the algorithms for overlapping community detection based on local expansion and optimization. A framework is proposed to investigate this particular type of algorithms in several issues: (1) choosing initial seed vertices; (2) community expansion; (3) refining seed vertices and (4) post-processing duplicate communities and homeless vertices. The contributions of this work are: (1) new expansion functions based on indirect neighbors of vertices and counts of neighbors to improve the performance in highly overlapping community detection, and (2) a new method to refine seed vertices based on accumulated centrality of edges in communities to mitigate the effects of incorrect seed vertices.