大規(guī)模圖計(jì)算在社區(qū)發(fā)現(xiàn)中的應(yīng)用研究

摘要：為更好地布局和展示社交網(wǎng)絡(luò)數(shù)據(jù)，降低圖計(jì)算和布局難度，本文提出了一種改進(jìn)的社區(qū)發(fā)現(xiàn)算法，旨在解決現(xiàn)有社區(qū)發(fā)現(xiàn)算法存在的社區(qū)質(zhì)量低和圖計(jì)算效率低等問題。該算法以Louvain算法為基礎(chǔ)，針對(duì)大規(guī)模社交網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行了優(yōu)化和改進(jìn)。最后，采用實(shí)驗(yàn)驗(yàn)證的方式分析和對(duì)比了本文算法的有效性和可靠性。實(shí)驗(yàn)結(jié)果表明，與Louvain算法、吳祖峰算法等相比，本文算法在提高社區(qū)劃分質(zhì)量和效率方面具有顯著優(yōu)勢(shì)。

關(guān)鍵詞：圖計(jì)算；社區(qū)發(fā)現(xiàn)

引言

針對(duì)當(dāng)前社區(qū)發(fā)現(xiàn)算法在處理大規(guī)模社交網(wǎng)絡(luò)數(shù)據(jù)時(shí)存在的諸多不足，如社區(qū)劃分質(zhì)量較差、計(jì)算效率低下等問題，本文提出了一種改良版本的社區(qū)發(fā)現(xiàn)算法，沿用了Louvain算法第一階段的做法，但在第二階段采取了一系列優(yōu)化策略。該算法經(jīng)過(guò)優(yōu)化和改進(jìn)，能夠更加貼合大規(guī)模社交網(wǎng)絡(luò)的特性和實(shí)際需求。根據(jù)社交網(wǎng)絡(luò)特點(diǎn)，預(yù)先選取最大度數(shù)的節(jié)點(diǎn)，并將該節(jié)點(diǎn)設(shè)置為種子節(jié)點(diǎn)，實(shí)現(xiàn)小社區(qū)的及時(shí)合并，使得該算法迭代次數(shù)降到最低。

1. Louvain算法概述

Louvain算法是一種經(jīng)典的社區(qū)發(fā)現(xiàn)算法，其核心思想是基于模塊度優(yōu)化，通過(guò)不斷地將節(jié)點(diǎn)聚集并適當(dāng)劃分，從而得到最終的社區(qū)劃分結(jié)果。具體來(lái)說(shuō)，該算法會(huì)反復(fù)地將網(wǎng)絡(luò)中的節(jié)點(diǎn)合并到不同的社區(qū)中，同時(shí)根據(jù)一定的模塊度計(jì)算公式，評(píng)估合并前后社區(qū)質(zhì)量的變化，選擇能夠最大程度提高模塊度的方案，直至模塊度不再有提升為止[1]。其目標(biāo)函數(shù)為

（1）

式（1）中cin項(xiàng)表示該社區(qū)內(nèi)部所有邊的權(quán)重之和；ctot項(xiàng)體現(xiàn)了社區(qū)C與外部世界的聯(lián)系程度；ki項(xiàng)展示了節(jié)點(diǎn)i作為個(gè)體，與其所有鄰居節(jié)點(diǎn)之間連接的總強(qiáng)度；ki，in代表各個(gè)節(jié)點(diǎn)i與社區(qū)中節(jié)點(diǎn)鄰接邊權(quán)重之和；m項(xiàng)代表整個(gè)社交網(wǎng)絡(luò)中所有邊的權(quán)重總和。通過(guò)優(yōu)化這些權(quán)重相關(guān)的變量，Louvain算法可以得到較優(yōu)的社區(qū)劃分結(jié)果。Louvain算法的執(zhí)行過(guò)程分為兩個(gè)階段。在階段1中，算法將網(wǎng)絡(luò)中的節(jié)點(diǎn)劃分到不同的社t。具體來(lái)說(shuō)，對(duì)于每個(gè)節(jié)點(diǎn)，如果其鄰居節(jié)點(diǎn)可以歸入一個(gè)不同的社區(qū)，則需要按照一定順序，將節(jié)點(diǎn)依次嘗試添加到這個(gè)社區(qū)中。在每次添加時(shí)，根據(jù)公式（1）計(jì)算添加前后模塊度的變化量，選擇使模塊度提升最大的社區(qū)作為節(jié)點(diǎn)的所屬社區(qū)。

將最大值設(shè)置為max△Q，如果max△Q大于0，將節(jié)點(diǎn)i加入該社區(qū)后模塊度有所提升，在Louvain算法的執(zhí)行過(guò)程中，階段1會(huì)將網(wǎng)絡(luò)中的節(jié)點(diǎn)初步劃分到不同社區(qū)，根據(jù)模塊度公式計(jì)算；如果將某個(gè)節(jié)點(diǎn)加入某個(gè)社區(qū)能使模塊度提高，則將其歸入該社區(qū)，否則保持原社區(qū)歸屬。階段1完成后，可獲得一個(gè)初步的社區(qū)劃分結(jié)果和對(duì)應(yīng)的模塊度值。

階段2則對(duì)階段1的結(jié)果進(jìn)行迭代優(yōu)化。每輪迭代都會(huì)重新計(jì)算模塊度，當(dāng)模塊度函數(shù)在給定的迭代步驟下無(wú)法獲得進(jìn)一步提升時(shí)，算法的迭代過(guò)程終止。

2. 結(jié)合種子節(jié)點(diǎn)的社區(qū)發(fā)現(xiàn)算法

2.1 問題征集與創(chuàng)新方案

在現(xiàn)有Louvain算法中，階段2會(huì)多次執(zhí)行迭代環(huán)節(jié)，當(dāng)模塊Q度停止變化時(shí)，迭代環(huán)節(jié)執(zhí)行結(jié)束。當(dāng)處理大規(guī)模網(wǎng)絡(luò)數(shù)據(jù)時(shí)，Louvain算法會(huì)存在迭代次數(shù)多、運(yùn)行效率低、大社區(qū)合并過(guò)度、小社區(qū)數(shù)量過(guò)多等問題，為提高社交網(wǎng)絡(luò)數(shù)據(jù)信息的展示效率和清晰度，要適當(dāng)?shù)販p少社區(qū)發(fā)現(xiàn)算法運(yùn)行時(shí)間和小社區(qū)數(shù)量。因此，Louvain算法不適用于大規(guī)模社交網(wǎng)絡(luò)數(shù)據(jù)圖計(jì)算和可視化處理需求[2]。

在社交網(wǎng)絡(luò)中，通常表現(xiàn)出無(wú)標(biāo)度、小世界效應(yīng)等特點(diǎn)，因此，整個(gè)社交網(wǎng)絡(luò)節(jié)點(diǎn)度數(shù)主要呈現(xiàn)冪率分布特點(diǎn)，導(dǎo)致社交網(wǎng)絡(luò)中含有較多的低度數(shù)節(jié)點(diǎn)和少量的高度數(shù)節(jié)點(diǎn)。其中，高度數(shù)節(jié)點(diǎn)通常對(duì)附近的低度數(shù)節(jié)點(diǎn)產(chǎn)生較高的吸引力，從而形成一個(gè)完整的社區(qū)。當(dāng)Louvain算法階段1執(zhí)行完畢后，會(huì)產(chǎn)生大量的小社區(qū)和少量的大社區(qū)。在Louvain算法階段2中，可以完成對(duì)新網(wǎng)絡(luò)圖G'的構(gòu)建。在Louvain算法階段1中，借助各個(gè)社區(qū)，可以壓縮出若干個(gè)節(jié)點(diǎn)，這些節(jié)點(diǎn)經(jīng)過(guò)組合，形成新網(wǎng)絡(luò)圖G'。根據(jù)社交網(wǎng)絡(luò)特點(diǎn)，本文基于Louvain算法，提出一種改進(jìn)的社區(qū)發(fā)現(xiàn)算法，該算法可以對(duì)大社區(qū)之間的合并操作進(jìn)行有效抑制，同時(shí)，還能實(shí)現(xiàn)對(duì)小社區(qū)的有效合并處理，有效解決Louvain算法存在的缺陷問題。

2.2 改進(jìn)的社區(qū)發(fā)現(xiàn)算法

本文所提出的改進(jìn)社區(qū)發(fā)現(xiàn)算法在保留Louvain算法階段1的基礎(chǔ)上，重點(diǎn)改進(jìn)了Louvain算法階段2，同時(shí)，該階段2無(wú)須進(jìn)行迭代執(zhí)行。在整個(gè)網(wǎng)絡(luò)圖G節(jié)點(diǎn)中，含有若干個(gè)社區(qū)集合C，由于階段1存在過(guò)多的小社區(qū)，因此，在階段2中，要不斷地劃分社區(qū)。

在改進(jìn)社區(qū)發(fā)現(xiàn)算法階段2中，進(jìn)一步壓縮處理階段1所對(duì)應(yīng)的劃分結(jié)果，從而完成對(duì)新網(wǎng)絡(luò)圖G'的構(gòu)建。在構(gòu)建好的新網(wǎng)絡(luò)圖G'中，選取多個(gè)種子節(jié)點(diǎn)，該種子節(jié)點(diǎn)集合如下所示：

（2）

式（2）中的deg（ν）代表節(jié)點(diǎn)ν的度數(shù)；g代表節(jié)點(diǎn)平均度數(shù)；p代表節(jié)點(diǎn)度數(shù)所對(duì)應(yīng)的標(biāo)準(zhǔn)方差。在劃分社區(qū)時(shí)，算法將所有節(jié)點(diǎn)分配到不同的社區(qū)中。對(duì)于網(wǎng)絡(luò)中的每個(gè)非種子節(jié)點(diǎn)i，算法會(huì)檢查其鄰居節(jié)點(diǎn)所屬的社區(qū)情況。如果該節(jié)點(diǎn)的鄰居節(jié)點(diǎn)分屬于多個(gè)不同的社區(qū)，那么算法會(huì)按照一定的順序，嘗試將該節(jié)點(diǎn)逐一加入這些社區(qū)中。每次加入時(shí)，算法利用公式（1）計(jì)算該節(jié)點(diǎn)加入前后模塊度的變化量，以評(píng)估該節(jié)點(diǎn)加入該社區(qū)對(duì)模塊度（即社區(qū)質(zhì)量）的影響程度，以評(píng)估將節(jié)點(diǎn)△Qj（j=1，2，…，t）劃分到不同社區(qū)的優(yōu)劣。如果該社區(qū)含有若干個(gè)種子節(jié)點(diǎn)，需要將該社區(qū)自動(dòng)添加到所設(shè)置好的集合D1中，反之，則自動(dòng)添加到集合D2中。然后，對(duì)集合D1中的△Qj最大值設(shè)置為max△Q，如果該△Qj最大值大于0，需要將節(jié)點(diǎn)i自動(dòng)分配△Qj到最大值所對(duì)應(yīng)的社區(qū)中，反之，須對(duì)集合D2中的△Qj最大值設(shè)置為max△Q，如果該△Qj最大值大于0，需要將節(jié)點(diǎn)i自動(dòng)分配到△Qj最大值所對(duì)應(yīng)的社區(qū)中，對(duì)于那些既不屬于種子節(jié)點(diǎn)集合，也不適合并入任何一個(gè)含有種子節(jié)點(diǎn)的社區(qū)的節(jié)點(diǎn)，算法將保留其原有的社區(qū)歸屬，不對(duì)其進(jìn)行重新分配[3]。

本文提出的改進(jìn)社區(qū)發(fā)現(xiàn)算法具體步驟如下：

步驟1：通過(guò)對(duì)Louvain算法的階段 1進(jìn)行執(zhí)行，初步獲得相應(yīng)的社區(qū)劃分結(jié)果，該結(jié)果用C表示。

步驟2：對(duì)所獲得的社區(qū)劃分結(jié)果C進(jìn)行初步壓縮處理，獲得G'（V'，E'）。

步驟3：運(yùn)用式（2），計(jì)算出種子節(jié)點(diǎn)集合S。

步驟4：將非種子節(jié)點(diǎn)i直接分配到所構(gòu)建好的新社區(qū)中。

步驟5：重復(fù)操作步驟4，將所有非種子節(jié)點(diǎn)i分配到相應(yīng)的新社區(qū)中。

步驟6：輸出最終社區(qū)劃分結(jié)果C，此時(shí)，整個(gè)算法全部結(jié)束。

3. 實(shí)驗(yàn)和結(jié)果分析

3.1 社區(qū)發(fā)現(xiàn)算法實(shí)驗(yàn)方案

本文主要選用了模塊度值Q、社區(qū)數(shù)量、算法運(yùn)行時(shí)間三種評(píng)價(jià)指標(biāo)，模塊度值Q和社區(qū)劃分效果之間存在正相關(guān)關(guān)系，后者隨著前者的變大而變得越來(lái)越好，算法運(yùn)行時(shí)間和算法運(yùn)行效率存在反相關(guān)關(guān)系，后者隨著前者的變短而變得越來(lái)越高。

3.2 社區(qū)發(fā)現(xiàn)算法實(shí)驗(yàn)及分析

3.2.1 不同數(shù)據(jù)集實(shí)驗(yàn)的統(tǒng)計(jì)對(duì)比

為全面評(píng)測(cè)本文提出算法的社區(qū)劃分質(zhì)量和計(jì)算效率，開展了與Louvain算法和吳祖峰算法的對(duì)比實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果如表1所示，選取了模塊度Q、社區(qū)數(shù)量和算法運(yùn)行時(shí)間三個(gè)指標(biāo)作為評(píng)估標(biāo)準(zhǔn)。其中，模塊度Q可以用來(lái)衡量社區(qū)劃分的質(zhì)量和合理性，模塊度越高，表明社區(qū)劃分結(jié)果越好。通過(guò)比較不同算法在這三個(gè)指標(biāo)上的表現(xiàn)，可以全面評(píng)價(jià)本文算法的優(yōu)劣和改進(jìn)效果。從表1可以看出，與Louvain算法、吳祖峰算法等相比，本文算法的模塊度Q更大，社區(qū)數(shù)量更小，這說(shuō)明運(yùn)用本文算法可以獲得較高的社區(qū)劃分質(zhì)量。此外，本文算法運(yùn)行效率明顯高于其他兩種算法。實(shí)驗(yàn)結(jié)果表明：本文所提出的改進(jìn)社區(qū)發(fā)現(xiàn)算法具有社區(qū)劃分質(zhì)量高、算法運(yùn)行效率高等特點(diǎn)。

3.2.2 典型數(shù)據(jù)集的可視化結(jié)果對(duì)比

為直觀對(duì)比本文算法與Louvain算法在社區(qū)劃分效果上的差異，對(duì)部分?jǐn)?shù)據(jù)集進(jìn)行了可視化處理，結(jié)果分別呈現(xiàn)在圖1和圖2中。由于吳祖峰算法和Louvain算法在本數(shù)據(jù)集上產(chǎn)生了相同的社區(qū)劃分，因此分別與本文算法進(jìn)行對(duì)比，其實(shí)質(zhì)含義是一致的，無(wú)須重復(fù)展示。通過(guò)將改進(jìn)算法與經(jīng)典算法的輸出結(jié)果并列比對(duì)，能夠更加直觀地反映出兩種算法在處理同一數(shù)據(jù)時(shí)的差異表現(xiàn)，有助于凸顯本文算法的創(chuàng)新之處。在這些可視化圖中，使用不同顏色代表不同的社區(qū)，同一顏色的節(jié)點(diǎn)表示它們被劃分到了同一個(gè)社區(qū)。通過(guò)對(duì)比不同算法產(chǎn)生的社區(qū)劃分結(jié)果，可以直觀評(píng)估算法的優(yōu)劣及改進(jìn)效果。

Hamsterster數(shù)據(jù)集社區(qū)劃分結(jié)果可視化對(duì)比如圖2所示。從圖2中可以看出，運(yùn)用Louvain算法所劃分的社區(qū)數(shù)量為131個(gè)，運(yùn)用本文算法所劃分的社區(qū)數(shù)量為30個(gè)，這說(shuō)明運(yùn)用本文算法所劃分的小社區(qū)數(shù)量相對(duì)較少，有效地解決了Louvain算法存在的小社區(qū)數(shù)量過(guò)多問題。

在數(shù)據(jù)集中可以發(fā)現(xiàn)，本文算法所獲得的模塊度Q遠(yuǎn)遠(yuǎn)超過(guò)Louvain算法，這說(shuō)明本文算法可以緩解Louvain算法存在的過(guò)度合并大社區(qū)問題。

結(jié)語(yǔ)

在社交網(wǎng)絡(luò)中，含有無(wú)尺度、小世界特性的社區(qū)結(jié)構(gòu)，應(yīng)用該社區(qū)結(jié)構(gòu)，可以降低圖計(jì)算復(fù)雜度，通過(guò)應(yīng)用圖計(jì)算技術(shù)，可以實(shí)現(xiàn)對(duì)網(wǎng)絡(luò)數(shù)據(jù)的計(jì)算和獲得。本文在參照Louvain算法的基礎(chǔ)上，提出一種改進(jìn)社區(qū)發(fā)現(xiàn)算法，該算法滿足圖計(jì)算、圖可視化相關(guān)標(biāo)準(zhǔn)和要求。在本文算法的設(shè)計(jì)中，主要采取了以下策略：選取度數(shù)較大的節(jié)點(diǎn)作為種子節(jié)點(diǎn)，避免了使用Louvain算法時(shí)大社區(qū)過(guò)度合并的問題。優(yōu)先合并小社區(qū)，將小社區(qū)數(shù)量降至最小。在第二階段無(wú)須進(jìn)行迭代執(zhí)行，減少了計(jì)算開銷。實(shí)驗(yàn)結(jié)果表明：與Louvain算法、吳祖峰算法相比，本文算法在提高社區(qū)劃分質(zhì)量和效率方面具有顯著優(yōu)勢(shì)。

參考文獻(xiàn)：

[1]歐朋成.大規(guī)模網(wǎng)絡(luò)表示學(xué)習(xí)和結(jié)構(gòu)發(fā)現(xiàn)算法研究[D].石家莊：河北地質(zhì)大學(xué)，2020.

[2]王晨旭，周俊銘，姜佩京.基于拓?fù)浣Y(jié)構(gòu)表示學(xué)習(xí)的大規(guī)模無(wú)監(jiān)督圖對(duì)齊方法研究[J].計(jì)算機(jī)學(xué)報(bào)，2023，46（7）：1350-1365.

[3]趙鵬.大規(guī)模圖計(jì)算系統(tǒng)優(yōu)化技術(shù)研究[D].北京：中國(guó)科學(xué)院大學(xué)，2019.

作者簡(jiǎn)介：王延楠，本科，研究方向：大數(shù)據(jù)、圖計(jì)算。