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

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

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

引言

針對當(dāng)前社區(qū)發(fā)現(xiàn)算法在處理大規(guī)模社交網(wǎng)絡(luò)數(shù)據(jù)時存在的諸多不足，如社區(qū)劃分質(zhì)量較差、計算效率低下等問題，本文提出了一種改良版本的社區(qū)發(fā)現(xiàn)算法，沿用了Louvain算法第一階段的做法，但在第二階段采取了一系列優(yōu)化策略。該算法經(jīng)過優(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ù)降到最低。

1. Louvain算法概述

Louvain算法是一種經(jīng)典的社區(qū)發(fā)現(xiàn)算法，其核心思想是基于模塊度優(yōu)化，通過不斷地將節(jié)點(diǎn)聚集并適當(dāng)劃分，從而得到最終的社區(qū)劃分結(jié)果。具體來說，該算法會反復(fù)地將網(wǎng)絡(luò)中的節(jié)點(diǎn)合并到不同的社區(qū)中，同時根據(jù)一定的模塊度計算公式，評估合并前后社區(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作為個體，與其所有鄰居節(jié)點(diǎn)之間連接的總強(qiáng)度；ki，in代表各個節(jié)點(diǎn)i與社區(qū)中節(jié)點(diǎn)鄰接邊權(quán)重之和；m項(xiàng)代表整個社交網(wǎng)絡(luò)中所有邊的權(quán)重總和。通過優(yōu)化這些權(quán)重相關(guān)的變量，Louvain算法可以得到較優(yōu)的社區(qū)劃分結(jié)果。Louvain算法的執(zhí)行過程分為兩個階段。在階段1中，算法將網(wǎng)絡(luò)中的節(jié)點(diǎn)劃分到不同的社t。具體來說，對于每個節(jié)點(diǎn)，如果其鄰居節(jié)點(diǎn)可以歸入一個不同的社區(qū)，則需要按照一定順序，將節(jié)點(diǎn)依次嘗試添加到這個社區(qū)中。在每次添加時，根據(jù)公式（1）計算添加前后模塊度的變化量，選擇使模塊度提升最大的社區(qū)作為節(jié)點(diǎn)的所屬社區(qū)。

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

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

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

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

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

在社交網(wǎng)絡(luò)中，通常表現(xiàn)出無標(biāo)度、小世界效應(yīng)等特點(diǎn)，因此，整個社交網(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)通常對附近的低度數(shù)節(jié)點(diǎn)產(chǎn)生較高的吸引力，從而形成一個完整的社區(qū)。當(dāng)Louvain算法階段1執(zhí)行完畢后，會產(chǎn)生大量的小社區(qū)和少量的大社區(qū)。在Louvain算法階段2中，可以完成對新網(wǎng)絡(luò)圖G'的構(gòu)建。在Louvain算法階段1中，借助各個社區(qū)，可以壓縮出若干個節(jié)點(diǎn)，這些節(jié)點(diǎn)經(jīng)過組合，形成新網(wǎng)絡(luò)圖G'。根據(jù)社交網(wǎng)絡(luò)特點(diǎn)，本文基于Louvain算法，提出一種改進(jìn)的社區(qū)發(fā)現(xiàn)算法，該算法可以對大社區(qū)之間的合并操作進(jìn)行有效抑制，同時，還能實(shí)現(xiàn)對小社區(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，同時，該階段2無須進(jìn)行迭代執(zhí)行。在整個網(wǎng)絡(luò)圖G節(jié)點(diǎn)中，含有若干個社區(qū)集合C，由于階段1存在過多的小社區(qū)，因此，在階段2中，要不斷地劃分社區(qū)。

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

（2）

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

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

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

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

步驟3：運(yùn)用式（2），計算出種子節(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，此時，整個算法全部結(jié)束。

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

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

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

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

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

為全面評測本文提出算法的社區(qū)劃分質(zhì)量和計算效率，開展了與Louvain算法和吳祖峰算法的對比實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果如表1所示，選取了模塊度Q、社區(qū)數(shù)量和算法運(yùn)行時間三個指標(biāo)作為評估標(biāo)準(zhǔn)。其中，模塊度Q可以用來衡量社區(qū)劃分的質(zhì)量和合理性，模塊度越高，表明社區(qū)劃分結(jié)果越好。通過比較不同算法在這三個指標(biāo)上的表現(xiàn)，可以全面評價本文算法的優(yōu)劣和改進(jìn)效果。從表1可以看出，與Louvain算法、吳祖峰算法等相比，本文算法的模塊度Q更大，社區(qū)數(shù)量更小，這說明運(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é)果對比

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

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

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

結(jié)語

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

參考文獻(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ī)模無監(jiān)督圖對齊方法研究[J].計算機(jī)學(xué)報，2023，46（7）：1350-1365.

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

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