[科普中國(guó)]-Fast Girvan Newman社團(tuán)發(fā)現(xiàn)算法

模塊度最大化問題是一個(gè)典型的最優(yōu)化問題，Mark Newman基于貪心思想提出了模塊度最大化的貪心算法FN1。貪心思想的目標(biāo)是為了找出目標(biāo)函數(shù)的整體最優(yōu)值或者近似最優(yōu)值，它將整體最優(yōu)化問題分解為局部最優(yōu)化問題，找出每個(gè)小的局部最優(yōu)值，最終將局部最優(yōu)值整合成整體的近似最優(yōu)值。FN算法將模塊度最優(yōu)化問題分解為模塊度局部最優(yōu)化問題，初始時(shí)，算法將網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)都單獨(dú)的看作獨(dú)立的小社區(qū)。然后，考慮所有相連社區(qū)兩兩合并的情況，計(jì)算每種合并帶來的模塊度的增量?；谪澬脑瓌t，選取使模塊度增長(zhǎng)最大或者減小最少的兩個(gè)社區(qū)，將它們合并成一個(gè)新的社區(qū)。如此循環(huán)迭代，直到所有節(jié)點(diǎn)合并成一個(gè)社區(qū)。隨著迭代的進(jìn)行，網(wǎng)絡(luò)總的模塊度是不斷變化的，在模塊度的整個(gè)變化過程中，其最大值對(duì)應(yīng)的網(wǎng)絡(luò)的社區(qū)劃分即為近似的最優(yōu)社區(qū)劃分。

貪心算法FN具體步驟如下所述：

（1）去掉網(wǎng)絡(luò)中所有的邊，網(wǎng)絡(luò)的每個(gè)節(jié)點(diǎn)都單獨(dú)作為一個(gè)社區(qū)；

（2）網(wǎng)絡(luò)中的每個(gè)連通部分作為一個(gè)社區(qū)，將還未加入網(wǎng)絡(luò)的邊分別重新加回網(wǎng)絡(luò)，如果加入網(wǎng)絡(luò)的邊連接了兩個(gè)不同的社區(qū)，即合并了兩個(gè)社區(qū)，則計(jì)算形成的新的社區(qū)劃分的模塊度的增量。選擇使模塊度增長(zhǎng)最大或者減小最少的兩個(gè)社區(qū)進(jìn)行合并；

（3）如果網(wǎng)絡(luò)的社區(qū)數(shù)大于1，則返回步驟 （2） 繼續(xù)迭代，否則轉(zhuǎn)到步驟 （4）；

（4）遍歷每種社區(qū)劃分對(duì)應(yīng)的模塊度的值，選取模塊度最大的社區(qū)劃分作為網(wǎng)絡(luò)的最優(yōu)劃分。