一種新的在線社交網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法

何道兵，劉小洋，丁 楠

(重慶理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，重慶400054)

1 前言

在線社交網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)研究算法，隨著時(shí)代的發(fā)展，已經(jīng)成為了一個(gè)值得深入研究的科學(xué)問題。社交網(wǎng)絡(luò)現(xiàn)在已經(jīng)成為了人們生活不可缺少的一部分，是對(duì)現(xiàn)實(shí)關(guān)系的一個(gè)映射，是基于互聯(lián)網(wǎng)和通信平臺(tái)形成的一個(gè)大數(shù)據(jù)網(wǎng)絡(luò)。對(duì)網(wǎng)絡(luò)數(shù)據(jù)和結(jié)構(gòu)的認(rèn)識(shí)[1-3]，能讓人們更好的理解網(wǎng)絡(luò)上事物發(fā)生過程，使人們更好的設(shè)計(jì)、控制網(wǎng)絡(luò)。而虛擬社區(qū)的發(fā)現(xiàn)作為網(wǎng)絡(luò)科學(xué)的經(jīng)典問題，讓眾多學(xué)者不斷地追尋探索[4-7]。研究發(fā)現(xiàn)在現(xiàn)實(shí)中包含著各種多樣的網(wǎng)絡(luò)，就像社交、技術(shù)、生物等方面因某種關(guān)系而產(chǎn)生網(wǎng)絡(luò)，這些網(wǎng)絡(luò)都具有一個(gè)共同特性就是社區(qū)結(jié)構(gòu)。同一特性節(jié)點(diǎn)以及它們的關(guān)系連邊所構(gòu)成的圖便是網(wǎng)絡(luò)社區(qū)，不同的社區(qū)連接組成社交網(wǎng)絡(luò)，社區(qū)內(nèi)部連接邊比社區(qū)之間連接邊往往更加稠密。社區(qū)結(jié)構(gòu)是社交網(wǎng)絡(luò)的重要結(jié)構(gòu)特征之一[8-12]，它代表了真實(shí)網(wǎng)絡(luò)的異質(zhì)性和模塊化的特點(diǎn)，它在網(wǎng)絡(luò)的功能和拓?fù)浞治鲋邪l(fā)揮著重要作用。此外，社交網(wǎng)絡(luò)通常在社區(qū)上會(huì)展現(xiàn)出單個(gè)節(jié)點(diǎn)和整個(gè)網(wǎng)絡(luò)所不具備的特點(diǎn)。因此，對(duì)社會(huì)網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法的研究在很多方面具有重要意義[13-16]。

本文為了克服傳統(tǒng)的社交網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法僅僅是從數(shù)學(xué)理論上進(jìn)行分析的不足之處，采用微博用戶數(shù)據(jù)集和karate數(shù)據(jù)集上進(jìn)行社區(qū)劃分，運(yùn)用了凝聚思想并引入模塊度增量的概念來構(gòu)建社交網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法。

2 相關(guān)工作

在最近幾年中，復(fù)雜網(wǎng)絡(luò)中社區(qū)結(jié)構(gòu)的發(fā)現(xiàn)和分析越來越受到社會(huì)的重視，已經(jīng)出現(xiàn)了許多社區(qū)發(fā)現(xiàn)算法。自Girvan和Newman提出 GN 算法以來由計(jì)算機(jī)科學(xué)、物理學(xué)以及數(shù)學(xué)等多個(gè)學(xué)科發(fā)展出許多社區(qū)發(fā)現(xiàn)的算法，并廣泛應(yīng)用于各個(gè)科學(xué)領(lǐng)域的具體問題中[17-19]。

在最開始大家的理解，社區(qū)指的是在一個(gè)系統(tǒng)中某些個(gè)體因?yàn)橛幸恍┕餐c(diǎn)或者相似點(diǎn)，分析而形成在外部稀疏且在內(nèi)部緊密的連接結(jié)構(gòu)。非重疊社區(qū)發(fā)現(xiàn)是一種硬劃分，其中每個(gè)節(jié)點(diǎn)只能屬于一個(gè)社區(qū)，社區(qū)之間沒有交集。非重疊社區(qū)研究主要有傳統(tǒng)方法的譜方法以及基于模塊度的GN算法，對(duì)于非重疊社區(qū)發(fā)現(xiàn)算法的研究主要?dú)w功于Girvan與Newman在2002年的開創(chuàng)性研究工作[20-22]。

在真實(shí)的社交網(wǎng)絡(luò)中，人們往往同時(shí)屬于不同的社區(qū)，并且屬于多個(gè)社區(qū)的人。一方面，重疊節(jié)點(diǎn)是網(wǎng)絡(luò)中關(guān)鍵點(diǎn)，重疊社區(qū)因此而產(chǎn)生聯(lián)系；另一方面，重疊社區(qū)反映了更加真實(shí)的網(wǎng)絡(luò)結(jié)構(gòu)[7]。因此，對(duì)重疊社區(qū)進(jìn)行發(fā)現(xiàn)和研究是更符合現(xiàn)實(shí)網(wǎng)絡(luò)的真實(shí)性的，更具有社會(huì)價(jià)值，更應(yīng)引起研究者的重視和關(guān)注。重疊社區(qū)發(fā)現(xiàn)方法主要有以下幾類：基于派系過濾的重疊社區(qū)發(fā)現(xiàn)算法，基于局部擴(kuò)張及優(yōu)化的方法，基于線圖/邊社區(qū)的發(fā)現(xiàn)方法。隨著近十多年來的研究和發(fā)展，社區(qū)發(fā)現(xiàn)研究的重點(diǎn)一直都在發(fā)生改變，根據(jù)當(dāng)前互聯(lián)網(wǎng)技術(shù)驅(qū)動(dòng)的社交網(wǎng)絡(luò)環(huán)境中的網(wǎng)絡(luò)拓?fù)浜蜕鐓^(qū)結(jié)構(gòu)特征，社區(qū)發(fā)現(xiàn)的研究仍然面臨著若干的挑戰(zhàn)性問題[23-24]。

3 傳統(tǒng)社區(qū)發(fā)現(xiàn)算法

3.1 采用分裂思想的算法

在2002年由Girvan和Newman提出的分裂算法，現(xiàn)如今已經(jīng)成為了社區(qū)發(fā)現(xiàn)算法的一大經(jīng)典算法，就是GN算法[25-26]。眾所周知，社區(qū)與社區(qū)之間的聯(lián)系相對(duì)來說較為稀疏，這也就代表著社區(qū)與社區(qū)之間的溝通渠道相對(duì)較少，因此一個(gè)社區(qū)與另一個(gè)社區(qū)需要通過這些溝通渠道中的至少一個(gè)。如果能夠從中找到這些較為重要的溝通通道并且進(jìn)行移除的話，那么網(wǎng)絡(luò)就自然而然地會(huì)進(jìn)行社區(qū)劃分。Girvan和Newman提出了使用邊介數(shù)來對(duì)每條邊的網(wǎng)絡(luò)連通重要性進(jìn)行記錄，在對(duì)網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行社區(qū)發(fā)現(xiàn)過程中，分析時(shí)需要關(guān)心網(wǎng)絡(luò)圖是有向邊還是無向邊，是正權(quán)邊還是負(fù)權(quán)邊，頂點(diǎn)是否存在自環(huán)的可能。邊介數(shù)指的是網(wǎng)絡(luò)中的頂點(diǎn)間的最短路徑經(jīng)過該邊的次數(shù)，對(duì)于無權(quán)圖，最短路徑是頂點(diǎn)之間數(shù)量最少的邊，而有權(quán)圖中為兩點(diǎn)之間權(quán)值和最少的連邊。邊介數(shù)的數(shù)學(xué)公式定義見式(1)。

(1)

其中的σst(v)表示的是從上s→t最短路徑上經(jīng)過了節(jié)點(diǎn)v的最短路徑數(shù)，σst表示了s→t上的最短路徑數(shù)。每次需要找到s節(jié)點(diǎn)到v節(jié)點(diǎn)的最短路徑上v的前驅(qū)節(jié)點(diǎn)集合，因?yàn)閟到v的最短路徑上一定會(huì)經(jīng)過v的某前驅(qū)節(jié)點(diǎn)。在計(jì)算最短路徑上。可以對(duì)無權(quán)圖調(diào)用BFS廣度優(yōu)先遍歷算法，對(duì)有權(quán)圖調(diào)用Dijkstra算法[26-27]。

該算法使用一個(gè)隊(duì)列來存放每次遍歷的節(jié)點(diǎn)，使用visited數(shù)組記錄該節(jié)點(diǎn)是否訪問過。初始時(shí)所有節(jié)點(diǎn)都未被訪問過，灰色節(jié)點(diǎn)為即將訪問的節(jié)點(diǎn)，先從第一個(gè)結(jié)點(diǎn)v1開始進(jìn)行入隊(duì)操作并將該節(jié)點(diǎn)visited置為1表示已經(jīng)訪問過。由于v1為隊(duì)頭元素，所以v1出隊(duì)并且鄰節(jié)點(diǎn)全部為待訪問節(jié)點(diǎn)，直到最后隊(duì)列為空退出循環(huán)，此時(shí)所有節(jié)點(diǎn)均已訪問過。

而Dijkstra只能計(jì)算單元最短路而且權(quán)值必須為正，該算法是基于貪心的思想。對(duì)每個(gè)節(jié)點(diǎn)進(jìn)行一次遍歷就可計(jì)算出該節(jié)點(diǎn)到其它節(jié)點(diǎn)的最短路徑，通過集合S存放已找出的最短路徑，U集合存放還未找出的最短路徑的節(jié)點(diǎn)。每次通過在U集合中找出最短路徑的點(diǎn)然后加入S集合中，同時(shí)U集合進(jìn)行更新。循環(huán)到遍歷結(jié)束后，U集合為空就得到該節(jié)點(diǎn)到每個(gè)連通節(jié)點(diǎn)的最短路徑。GN算法的基本流程如下。

1)根據(jù)網(wǎng)絡(luò)圖結(jié)構(gòu)采用有效的最短路徑算法，計(jì)算出所有節(jié)點(diǎn)間的最短路徑，得出網(wǎng)絡(luò)中每條邊的邊介數(shù)。

2)找出所有邊介數(shù)中的最大值，當(dāng)邊介數(shù)最大值唯一時(shí)將該邊介數(shù)進(jìn)行移除，當(dāng)邊介數(shù)最大值不唯一時(shí)，可以隨機(jī)選擇一條邊斷開，也可以同時(shí)將所有邊介數(shù)最大值的邊斷開。

3)移除邊后，對(duì)網(wǎng)絡(luò)中剩余的邊依據(jù)步驟1思路重新進(jìn)行邊介數(shù)的計(jì)算。

4)對(duì)步驟2、3進(jìn)行循環(huán)，當(dāng)為網(wǎng)絡(luò)中所有的邊被移除時(shí)算法進(jìn)行終止。

對(duì)GN算法使用karate數(shù)據(jù)集進(jìn)行社區(qū)劃分后，對(duì)每次迭代后的模塊度進(jìn)行統(tǒng)計(jì)，得到了圖1表示了GN算法過程中邊數(shù)量與模塊度值的關(guān)系。

圖1 GN算法社區(qū)劃分Q值分布

可以看出，當(dāng)?shù)?3次時(shí)才開始出現(xiàn)了劃分，因?yàn)榍懊婷恳淮蔚厔澐挚赡艹霈F(xiàn)正好劃分成獨(dú)立社區(qū)，社區(qū)之間的相連邊均被刪除的情況。當(dāng)?shù)?9次時(shí)出現(xiàn)了社區(qū)模塊度巔峰值，取該模塊度下的社區(qū)劃分情況即為GN算法對(duì)karate數(shù)據(jù)集的最佳劃分。

圖2為在Q值分布中選擇了最大模塊度時(shí)的社區(qū)劃分情況，即為GN算法發(fā)現(xiàn)的社區(qū)劃分?？梢钥闯觯捎贕N算法是刪除最大邊介數(shù)，在移除邊的過程中，會(huì)優(yōu)先移除孤立點(diǎn)的，這也導(dǎo)致劃分過程中產(chǎn)生了較多的孤立點(diǎn)，如3.6中一共有21個(gè)社區(qū)存在，其中19個(gè)社區(qū)都是孤立社區(qū)。

圖2 GN社區(qū)劃分結(jié)果

3.2 采用聚合思想的算法

GN算法是針對(duì)全局性的，是對(duì)整體網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行劃分，而在現(xiàn)實(shí)的網(wǎng)絡(luò)結(jié)構(gòu)中，全局性網(wǎng)絡(luò)數(shù)據(jù)是很難實(shí)現(xiàn)的，通過對(duì)局部網(wǎng)絡(luò)的分析才是更有效的社區(qū)發(fā)現(xiàn)算法。所以Newman基于貪心思想提出了基于模塊度最大化的貪心算法FN算法，該算法將全局的最優(yōu)化分解成了局部最優(yōu)化問題，通過找出每個(gè)小塊的局部最優(yōu)值，最后將所有的局部最優(yōu)值整理一起，變成全局的近似最優(yōu)值。

貪心算法意味著在解決問題時(shí)始終做出當(dāng)前時(shí)刻的最佳選擇。也就是說，并不會(huì)去考慮整體的最優(yōu)性，從某方面來說，它是對(duì)局部最優(yōu)解的選擇。并不是所有的問題都可以通過貪心算法得到整體的最優(yōu)解，局部還是整體的最優(yōu)關(guān)鍵還是進(jìn)行貪婪算法時(shí)進(jìn)行的策略選擇。要確保選擇的貪婪策略必須沒有后遺癥，也就是說某一狀態(tài)一定只和當(dāng)前的狀態(tài)有著聯(lián)系，而并不會(huì)影響到未來的狀態(tài)[18]。貪婪的選擇意味著可以通過一系列局部最優(yōu)選擇，即貪婪的選擇來實(shí)現(xiàn)對(duì)所尋求問題的整體最佳解決方案。貪婪的選擇是自頂向下連續(xù)地進(jìn)行迭代選擇。每次做出貪婪的選擇時(shí)，問題就會(huì)減少到一個(gè)較小的子問題。貪婪算法的基本思想是從問題的初始解決方案一步一步地進(jìn)行，根據(jù)優(yōu)化措施，每個(gè)步驟必須確?？梢垣@得局部最優(yōu)解。每個(gè)步驟只考慮一個(gè)數(shù)據(jù)，但是該選擇要能夠滿足獲得局部最優(yōu)解的條件。如果下一個(gè)數(shù)據(jù)和部分最優(yōu)解決方案不再是可行的解決方案時(shí)，則在枚舉完所有數(shù)據(jù)之前將數(shù)據(jù)添加到部分解決方案中，或者無法再添加的時(shí)候進(jìn)行算法終止。FN算法最開始初始化的時(shí)候，將網(wǎng)絡(luò)中的所有的節(jié)點(diǎn)都看成一個(gè)單獨(dú)的社區(qū)，然后對(duì)所有的兩兩有聯(lián)系的社區(qū)合并進(jìn)行考慮，計(jì)算出每次社區(qū)合并會(huì)導(dǎo)致的模塊度增量ΔQ。由貪心算法的原則可知，每次劃分只對(duì)模塊度增量的最大值和最小值的兩兩社區(qū)進(jìn)行社區(qū)合并，一直迭代到當(dāng)所有的節(jié)點(diǎn)都合并成為一個(gè)社區(qū)。FN算法的具體步驟如下所述。

1)網(wǎng)絡(luò)結(jié)構(gòu)初始化，刪除掉網(wǎng)絡(luò)結(jié)構(gòu)中的所有連接邊，然后將每一個(gè)節(jié)點(diǎn)都看作是一個(gè)獨(dú)立的社區(qū)。

2)將網(wǎng)絡(luò)中存在的有連通關(guān)系的節(jié)點(diǎn)劃分為一個(gè)社區(qū)。對(duì)于還沒有加入的網(wǎng)絡(luò)連通邊都重新添加回網(wǎng)絡(luò)結(jié)構(gòu)中，若在網(wǎng)絡(luò)邊加入后，對(duì)兩個(gè)社區(qū)之間進(jìn)行了連接那么對(duì)兩個(gè)社區(qū)進(jìn)行合并，然后計(jì)算新的網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行社區(qū)劃分后的模塊度增量。每次只選取合并模塊度增量中的最大值或者減量中的最小值的兩個(gè)社區(qū)。

3)一直對(duì)步驟2進(jìn)行循環(huán)迭代，直到社區(qū)劃分的社區(qū)數(shù)量值為1時(shí)。

4)對(duì)所有社區(qū)劃分模塊度值進(jìn)行遍歷，尋找選擇具有最大模塊度的社區(qū)作為網(wǎng)絡(luò)的最佳劃分。

在FN算法的計(jì)算過程中，要注意每次進(jìn)行模塊度計(jì)算的時(shí)候，都必須要在完整的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)上，也就意味著在拓?fù)浣Y(jié)構(gòu)上包含了網(wǎng)絡(luò)中所有的邊。對(duì)FN算法使用karate數(shù)據(jù)集進(jìn)行運(yùn)算后，記錄每次添加邊后的Q值，分布結(jié)果如圖3所示。

圖3 FN算法社區(qū)發(fā)現(xiàn)Q值分布

從圖3的Q值分布圖可以看出，最開始將所有點(diǎn)看作單獨(dú)的社區(qū)此時(shí)模塊度為0，到最后所有節(jié)點(diǎn)在一個(gè)社區(qū)模塊度為0。該算法在每次迭代對(duì)所有可能邊進(jìn)行添加，根據(jù)模塊度的增量增加最大減少最小原則，從而達(dá)到了社區(qū)分布的收斂。圖3中的Q值巔峰值就是社區(qū)劃分得最好結(jié)果，由圖可知，此時(shí)邊數(shù)添加為53條，根據(jù)結(jié)果記錄得到添加邊1和0時(shí)，得到53條邊的最優(yōu)結(jié)果。取出最優(yōu)解進(jìn)行數(shù)據(jù)可視化，得到圖4。

圖4 FN算法結(jié)果示意圖

從可視化圖中可以很好看出，每種顏色為一個(gè)社區(qū)的劃分，karate數(shù)據(jù)集經(jīng)過FN算法分為四個(gè)社區(qū)，此時(shí)是FN算法的最優(yōu)解。對(duì)比前面GN算法的運(yùn)行結(jié)果，存在許多的孤立點(diǎn)，F(xiàn)N算法的運(yùn)行結(jié)果明顯更加可靠，而且運(yùn)行時(shí)間更低，F(xiàn)N算法的步驟理解以及算法的實(shí)現(xiàn)都比GN算法更容易。

4 提出的MICDA算法

在MICDA算法中，新加入了一個(gè)模塊度增量ΔQ的概念，在對(duì)模塊度進(jìn)行初始化的時(shí)候應(yīng)該滿足式(2)。

(2)

式中，eij表示i、j社區(qū)邊連接的比例，初始所有節(jié)點(diǎn)單獨(dú)一個(gè)社區(qū)時(shí)，所有社區(qū)不相連，得出初始模塊度為0。在對(duì)模塊度增量進(jìn)行初始化的時(shí)候，元素?cái)?shù)據(jù)應(yīng)該滿足下列數(shù)學(xué)式(3)。

(3)

式中，ki，in表示的最新構(gòu)建圖i節(jié)點(diǎn)在社區(qū)C的權(quán)重之和，∑tot表示與社區(qū)C相連節(jié)點(diǎn)的邊的總權(quán)重，ki表示了i節(jié)點(diǎn)的總權(quán)重值。該公式比較復(fù)雜，對(duì)公式進(jìn)行簡化后得到式(4)。

(4)

ki表示節(jié)點(diǎn)i的度，kj表示節(jié)點(diǎn)j的度，m表示網(wǎng)絡(luò)中當(dāng)前結(jié)構(gòu)所有邊的數(shù)量。提出的MICDA算法1如下。

算法1：提出的MICDA算法

Step1：對(duì)所有節(jié)點(diǎn)進(jìn)行數(shù)據(jù)初始化，將每個(gè)節(jié)點(diǎn)i置于單獨(dú)的社區(qū)i中。

Step2：第一節(jié)點(diǎn)開始進(jìn)行選擇，找到該節(jié)點(diǎn)的所有鄰居節(jié)點(diǎn)，根據(jù)式(4，3)計(jì)算出當(dāng)該節(jié)點(diǎn)加入每一個(gè)鄰居社區(qū)時(shí)的ΔQ，如果ΔQ取值大于0就將鄰居節(jié)點(diǎn)劃分到當(dāng)前節(jié)點(diǎn)社區(qū)中，否則保持原社區(qū)不改變。

Step3：對(duì)step2進(jìn)行循環(huán)，迭代直達(dá)當(dāng)前節(jié)點(diǎn)所在社區(qū)為穩(wěn)定值。

Step4：每個(gè)社區(qū)劃分后，構(gòu)建一個(gè)新的圖結(jié)構(gòu)，將在同一個(gè)社區(qū)的節(jié)點(diǎn)全部看作一個(gè)新節(jié)點(diǎn)。新節(jié)點(diǎn)內(nèi)部節(jié)點(diǎn)與節(jié)點(diǎn)之間的權(quán)重，看作新節(jié)點(diǎn)自環(huán)產(chǎn)生的權(quán)值。新節(jié)點(diǎn)與鄰居節(jié)點(diǎn)的權(quán)值為內(nèi)部所有節(jié)點(diǎn)對(duì)該鄰居節(jié)點(diǎn)權(quán)值。完成新圖的構(gòu)建后，重復(fù)step2直到模塊度Q取值最大時(shí)終止。

算法1中對(duì)步驟2、步驟3的一個(gè)節(jié)點(diǎn)迭代過程如圖5所示，對(duì)步驟4中新圖結(jié)構(gòu)的構(gòu)建如圖6所示。

圖5為MICDA算法的迭代示意圖，最初五個(gè)節(jié)點(diǎn)是獨(dú)立的五個(gè)社區(qū)，在經(jīng)過步驟2的完全迭代后，發(fā)現(xiàn)2節(jié)點(diǎn)屬于1節(jié)點(diǎn)所在社區(qū)。此時(shí)進(jìn)行新圖的構(gòu)建，將節(jié)點(diǎn)1和節(jié)點(diǎn)2壓縮為一個(gè)新節(jié)點(diǎn)1，這時(shí)圖中只有四個(gè)節(jié)點(diǎn)存在。繼續(xù)對(duì)步驟2進(jìn)行迭代，以此發(fā)現(xiàn)了節(jié)點(diǎn)3、4、5都可以歸到新節(jié)點(diǎn)1中，進(jìn)行了三次新圖的構(gòu)建后，得到全圖只有一個(gè)社區(qū)1存在，節(jié)點(diǎn)1、2、3、4、5都屬于社區(qū)1中，此時(shí)不再有節(jié)點(diǎn)社區(qū)發(fā)生改變結(jié)束迭代。

圖5 MICDA迭代過程圖

圖6 MICDA算法過程示意圖

圖6更詳細(xì)的解釋了MICDA的新圖的構(gòu)建和權(quán)值的重新計(jì)算，MICDA算法的一次迭代分為模塊度優(yōu)化和社區(qū)聚合兩個(gè)大步驟。模塊度優(yōu)化為找到當(dāng)前節(jié)點(diǎn)的所有鄰居節(jié)點(diǎn)，將模塊度增量大于0節(jié)點(diǎn)加入當(dāng)前節(jié)點(diǎn)社區(qū)，上圖節(jié)點(diǎn)優(yōu)化后分為了四個(gè)顏色社區(qū)。社區(qū)聚合就是將所有相同顏色節(jié)點(diǎn)歸為一個(gè)新節(jié)點(diǎn)，如紅色節(jié)點(diǎn)全部看作16號(hào)新節(jié)點(diǎn)，新節(jié)點(diǎn)自環(huán)權(quán)值為所有紅色節(jié)點(diǎn)權(quán)值。從圖4.2可以看出整個(gè)算法中最重要的一步就是社區(qū)聚合，將節(jié)點(diǎn)融合成新節(jié)點(diǎn)，并通過初始邊關(guān)系計(jì)算新的節(jié)點(diǎn)與邊權(quán)值。該方法的偽代碼如算法2。

算法2 MICDA構(gòu)建新圖

輸入：cluser節(jié)點(diǎn)社區(qū)數(shù)組

輸出：聚合后新節(jié)點(diǎn)組成的圖結(jié)構(gòu)new_edge

function rebuildGraph()

int[n] change

change_size ← 0

boolean[n] vis

for i=0→n do

if vis[cluster[i]] then

continue

vis[cluster[i]] ← true

change[change_size++] ← cluster[i]

end for

int[] index ← new int[n];

for i=0→change_size do

index[change[i]] ← i

end for

int new_n ← change_size;

for i=0 → global_n do

global_cluster[i] ← new_global_cluster[i]

end for

top ← new_top

for i=0 → m do

edge[i]=new_edge[i]

end for

for i=0 → new_n do

node_weight[i] ← new_node_weight[i]

head[i] ← new_head[i]

end for

n ← new_n

init_cluster()

end function

通過算法1和式(4)可以實(shí)現(xiàn)MICDA算法。對(duì)karate數(shù)據(jù)集使用MICDA算法后，得到MICDA算法的模塊度隨著迭代次數(shù)的分布情況如圖7所示。

圖7 karate社區(qū)劃分結(jié)果

圖7為每次迭代后當(dāng)前模塊度值，由于MICDA算法每次添加邊不止一條，所以不像GN和FN算法可以曲線波動(dòng)大，MICDA結(jié)果更加簡潔易于理解，根據(jù)模塊度峰值取社區(qū)劃分最佳情況，進(jìn)行數(shù)據(jù)可視化得到圖8。

圖8 MICDA社區(qū)劃分結(jié)果圖

5 仿真結(jié)果與分析

5.1 時(shí)間復(fù)雜度

當(dāng)存在用不同方法的算法去解決一個(gè)相同的問題的時(shí)候會(huì)有時(shí)間復(fù)雜度的分析，因?yàn)椴煌乃惴ê脡氖菚?huì)影響整個(gè)程序的效率的，而進(jìn)行算法分析的意義在于選取合適的算法以及對(duì)劣質(zhì)算法進(jìn)行一定改善。對(duì)于算法，時(shí)間復(fù)雜度是定性地描述運(yùn)行時(shí)間的函數(shù)，一般用大O符號(hào)進(jìn)行表述。

圖9 微博用戶數(shù)據(jù)集社區(qū)發(fā)現(xiàn)時(shí)間復(fù)雜度比較

圖9為基于標(biāo)簽傳播的LPA算法和COPRA算法時(shí)間復(fù)雜度對(duì)比圖，兩個(gè)算法均是對(duì)微博用戶地區(qū)數(shù)據(jù)集進(jìn)行社區(qū)發(fā)現(xiàn)。由上圖可以看出由于LPA是非重疊社區(qū)發(fā)現(xiàn)算法，因此COPRA的時(shí)間復(fù)雜度比LPA更高。根據(jù)之前第三章得到的LPA和COPRA迭代次數(shù)圖，LPA的收斂性明顯更快COPRA。因此LPA的時(shí)間復(fù)雜度性能更好，但作為社區(qū)發(fā)現(xiàn)，COPRA是對(duì)重疊社區(qū)發(fā)現(xiàn)更具有實(shí)際意義。

圖10 karate數(shù)據(jù)集社區(qū)發(fā)現(xiàn)時(shí)間復(fù)雜度對(duì)比

圖10對(duì)COPRA算法、GN算法、FN算法以及MICDA算法的算法時(shí)間復(fù)雜度對(duì)比圖，以上算法采用源數(shù)據(jù)均是karate數(shù)據(jù)集。由上圖可以看出，GN算法的時(shí)間復(fù)雜度最高，MICDA算法時(shí)間復(fù)雜度最低。MICDA算法的時(shí)間復(fù)雜度性能得到了大大的提升，不管是對(duì)比基于模塊度最大化的經(jīng)典算法還是基于標(biāo)簽傳播的經(jīng)典算法。

5.2 模塊度Q

一個(gè)適用性高的算法應(yīng)該能夠識(shí)別良好的社區(qū)結(jié)構(gòu)[19]。人們常用的對(duì)良好社區(qū)結(jié)構(gòu)劃分得度量標(biāo)準(zhǔn)是模塊度函數(shù)，模塊化是目前常用的對(duì)網(wǎng)絡(luò)劃分穩(wěn)定性進(jìn)行度量的方法。模塊度最早是由Newman提出的一個(gè)適用性高的算法應(yīng)該能夠識(shí)別良好的社區(qū)結(jié)構(gòu)。人們常用的對(duì)良好社區(qū)結(jié)構(gòu)劃分得度量標(biāo)準(zhǔn)是模塊度函數(shù)，模塊化是目前常用的對(duì)網(wǎng)絡(luò)劃分穩(wěn)定性進(jìn)行度量的方法。模塊化計(jì)算的意義在于，連接網(wǎng)絡(luò)中兩個(gè)不同類型節(jié)點(diǎn)的邊緣比例的預(yù)期比率減去在相同社區(qū)結(jié)構(gòu)下任意連接兩個(gè)節(jié)點(diǎn)的邊緣比例[20]。在對(duì)劃分社區(qū)后進(jìn)行當(dāng)前社區(qū)結(jié)構(gòu)的模塊度計(jì)算，如果當(dāng)前社區(qū)結(jié)構(gòu)的模塊度值越高，表示了該算法在當(dāng)前劃分情況下是最可取的。

在進(jìn)行模塊度計(jì)算的過程中，由于大多數(shù)的網(wǎng)絡(luò)結(jié)構(gòu)是未知的，不會(huì)需要使用網(wǎng)絡(luò)已知的社區(qū)結(jié)構(gòu)進(jìn)行對(duì)比，因此模塊度用來作為社區(qū)劃分的評(píng)價(jià)指標(biāo)是適用最廣泛的。

圖11為基于模塊度的GN和FN算法與改進(jìn)后的MICDA算法分別對(duì)karate數(shù)據(jù)集進(jìn)行社區(qū)發(fā)現(xiàn)后，模塊度分布圖中出現(xiàn)的巔峰值。可以看出，三個(gè)算法的劃分都在0.3～0.7之間取值正常，而GN算法發(fā)現(xiàn)的社區(qū)結(jié)構(gòu)是比較差的，而改進(jìn)后的MICDA算法發(fā)現(xiàn)的社區(qū)結(jié)構(gòu)是最良好的。

圖11 算法模塊度對(duì)比

6 結(jié)論

本文針對(duì)社交網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)進(jìn)行了深入研究，將模塊度引入到社區(qū)發(fā)現(xiàn)檢測算法中，提出了一種改進(jìn)的社交網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法。其主要工作有：①運(yùn)用凝聚思想，從微博社交網(wǎng)絡(luò)中的節(jié)點(diǎn)開始，按照社區(qū)劃分的標(biāo)準(zhǔn)自底向上的凝聚成一個(gè)大社區(qū)；②新引入了一個(gè)模塊度增量的概念；采用微博社交網(wǎng)絡(luò)用戶數(shù)據(jù)集和karate數(shù)據(jù)集上進(jìn)行社區(qū)劃分，并與傳統(tǒng)的社區(qū)發(fā)現(xiàn)算法GN和FN進(jìn)行對(duì)比分析。③提出的算法使得代碼更易于實(shí)現(xiàn)，時(shí)間性能更高；提出的新算法在時(shí)間復(fù)雜度大大降低，降低為12%左右。

下一步將對(duì)社交網(wǎng)絡(luò)中的重疊社區(qū)進(jìn)行分析和研究。