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

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

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

引言

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

1. Louvain算法概述

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

（1）

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

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

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

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

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

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

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

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

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

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

（2）

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

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

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

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

步驟3：運用式（2），計算出種子節(jié)點集合S。

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

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

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

3. 實驗和結果分析

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

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

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

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

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

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

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

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

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

結語

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

參考文獻：

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

[2]王晨旭，周俊銘，姜佩京.基于拓撲結構表示學習的大規(guī)模無監(jiān)督圖對齊方法研究[J].計算機學報，2023，46（7）：1350-1365.

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

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