一個基于中心度的社團結構發現新算法

摘要：針對GN算法在社團結構發現中時間復雜度高等問題，提出一種基于中心度的GN改進算法(DCGN)。該算法根據節點中心度以及節點之間的最短路徑首先確定社團結構中心節點集，然后逐步刪除社團結構中心節點之間的最大邊介數連邊，完成社團結構劃分。DCGN算法避免了GN算法邊介數計算開銷大的問題，算法的時間復雜度約為O(cmn)，其中c為常數，n為網絡成員數，m為網絡連邊數。將DCGN和CN算法同時應用到za-cHARy網絡及計算機隨機生成網絡中并進行了比較。實驗結果表明，所提出的DcGN算法在運行效率和效果方面較之CN算法均具有一定的優勢。