模塊度最優(yōu)化算法

由于網(wǎng)絡(luò)所有可能的劃分?jǐn)?shù)量是巨大的，假設(shè)網(wǎng)絡(luò)的結(jié)點(diǎn)數(shù)和邊數(shù)分別為n和m，則所有可能的社區(qū)劃分?jǐn)?shù)是一個(gè)以n為指數(shù)的數(shù)。因此，在所有可能的劃分中找出最優(yōu)劃分是一個(gè)NP-hard問題。針對這一問題，目前一些相應(yīng)算法已被提出，其可以在合理的時(shí)間內(nèi)找出模塊度最大化的近似最優(yōu)劃分。

模塊度最大化問題是一個(gè)經(jīng)典的最優(yōu)化問題，Mark NewMan 基于貪心思想提出了模塊度最大化的貪心算法FN 。貪心思想的目標(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ú)立的小社區(qū)。然后，考慮所有相連社區(qū)兩兩合并的情況，計(jì)算每種合并帶來的模塊度的增量。基于貪心原則，選取使模塊度增長最大或者減小最少的兩個(gè)社區(qū)，將它們合并成一個(gè)社區(qū)。如此循環(huán)迭代，直到所有結(jié)點(diǎn)合并成一個(gè)社區(qū)。隨著迭代的進(jìn)行，網(wǎng)絡(luò)總的模塊度是不斷變化的，在模塊度的整個(gè)變化過程中，其最大值對應(yīng)網(wǎng)絡(luò)的社區(qū)劃分即為近似的最優(yōu)社區(qū)劃分。

貪心算法FN具體步驟:

該算法中，需要注意的是，每次加入的邊只是影響網(wǎng)絡(luò)的社區(qū)劃分，而每次計(jì)算網(wǎng)絡(luò)劃分的模塊度時(shí)，都是在網(wǎng)絡(luò)完整的拓?fù)浣Y(jié)構(gòu)上進(jìn)行，即網(wǎng)絡(luò)所有的邊都存在的拓?fù)浣Y(jié)構(gòu)上。

為了降低算法的時(shí)間復(fù)雜度，Vincent Blondel等人提出了另一種層次貪心算法 。該算法包括兩個(gè)階段，第一階段合并社區(qū)，算法將每個(gè)結(jié)點(diǎn)當(dāng)作一個(gè)社區(qū)，基于模塊度增量最大化標(biāo)準(zhǔn)決定你哪些鄰居社區(qū)應(yīng)該被合并。經(jīng)過一輪掃描后開始第二階段，算法將第一階段發(fā)現(xiàn)的所有社區(qū)重新看成結(jié)點(diǎn)，構(gòu)建新的網(wǎng)絡(luò)，在新網(wǎng)絡(luò)上重復(fù)進(jìn)行第一階段，這兩個(gè)階段重復(fù)運(yùn)行，直到網(wǎng)絡(luò)社區(qū)劃分的模塊度不再增長，得到網(wǎng)絡(luò)的社區(qū)近似最優(yōu)劃分。

這個(gè)簡單算法具有一下幾個(gè)優(yōu)點(diǎn):首先，算法的步驟比較直觀并且易于實(shí)現(xiàn);其次，算法不需要提前設(shè)定網(wǎng)絡(luò)的社區(qū)數(shù)，并且該算法可以呈現(xiàn)網(wǎng)絡(luò)的完整的分層社區(qū)結(jié)構(gòu)，能夠發(fā)現(xiàn)在線社交網(wǎng)絡(luò)的分層的虛擬社區(qū)結(jié)構(gòu)，獲得不同分辨率的虛擬社區(qū);再次，計(jì)算機(jī)模擬實(shí)驗(yàn)顯示，在稀疏網(wǎng)絡(luò)上，算法是時(shí)間復(fù)雜度是線性的，在合理的時(shí)間內(nèi)可以處理結(jié)點(diǎn)數(shù)超過10^9的網(wǎng)絡(luò)，因此十分適合在線社交網(wǎng)絡(luò)這樣超大規(guī)模的負(fù)責(zé)網(wǎng)絡(luò)中虛擬社區(qū)的發(fā)現(xiàn)。

模塊度也稱模塊化度量值，是目前常用的一種衡量網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)強(qiáng)度的方法，最早由Mark NewMan 提出了 。模塊度的定義為:

模塊度值的大小主要取決于網(wǎng)絡(luò)中結(jié)點(diǎn)的社區(qū)分配C，即網(wǎng)絡(luò)的社區(qū)劃分情況，可以用來定量的衡量網(wǎng)絡(luò)社區(qū)劃分質(zhì)量，其值越接近1，表示網(wǎng)絡(luò)劃分出的社區(qū)結(jié)構(gòu)的強(qiáng)度越強(qiáng)，也就是劃分質(zhì)量越好。因此可以通過最大化模塊度Q來獲得最優(yōu)的網(wǎng)絡(luò)社區(qū)劃分。