CNM社團發現算法是在NewmanFastGN算法的基礎上,Clauset等人採用堆的數據結構來計算和更新網路的模組性,提出了一種新的貪心算法。
基本介紹
- 中文名：CNM社團發現算法
- 外文名：CNM community detection method
在NewmanFastGN算法的基礎上,Clauset等人採用堆的數據結構來計算和更新網路的模組性,提出了一種新的貪心算法,這裡稱為，該算法的複雜度只有，已接近線性複雜度。
Newman貪心算法通過初始的連線矩陣計算模組度的增量ΔQ，而CNM算法直接構造一個模組度的增量矩陣ΔQ,然後通過對它的元素進行更新來得到模組性最大的一種社團結構。顯然,如果合併兩個不相連的社團,模組度Q的值是不會變的。因此只需要存儲那些有邊相連的社團i和j相應的元素,從而節省了存儲空間。輔助數據結構包括：模組性增量矩陣、最大堆、輔助向量。
算法流程：
1）初始化，初始化網路為n個社團，即每個節點就是一個獨立的社團，並計算模組性增量矩陣。
2）從最大堆中選擇最大的,合併相應的社團i和j,標記合併後的社團的標號為j;更新模組性增量矩陣ΔQ、最大堆H和輔助向量a。
3)重複步驟2),直到網路中所有的節點都歸到一個社團內。
