[發(fā)明專利]基于Louvain算法的社區(qū)發(fā)現(xiàn)方法、計算機(jī)設(shè)備及其可讀存儲介質(zhì)

在審

• 申請?zhí)枺?/td>: 202010149155.7
• 申請日: 2020-03-06
• 公開（公告）號: CN111028092A
• 公開（公告）日: 2020-04-17
• 發(fā)明（設(shè)計）人: 伍捷;韓柳;黃文輝;廖健;祝大裕
• 申請（專利權(quán)）人: 中郵消費(fèi)金融有限公司
• 主分類號: G06Q50/00
• 分類號: G06Q50/00
• 代理公司: 廣州微斗專利代理有限公司 44390
• 代理人: 唐立平

本發(fā)明涉及基于Louvain算法的社區(qū)發(fā)現(xiàn)方法、計算機(jī)設(shè)備及其可讀存儲介質(zhì)。該方法包括：S1：根據(jù)輸入數(shù)據(jù)生成表征網(wǎng)絡(luò)結(jié)構(gòu)的圖，圖包括節(jié)點(diǎn)及邊；S2：將圖的每個節(jié)點(diǎn)作為獨(dú)立社區(qū)；S3：進(jìn)行內(nèi)層循環(huán)，更新每個節(jié)點(diǎn)的歸屬社區(qū)；S4：重復(fù)步驟S3，直到圖的模塊度變化的百分比小于第一閾值且當(dāng)前循環(huán)次數(shù)為偶數(shù)，或內(nèi)層循環(huán)次數(shù)大于第二閾值且當(dāng)前循環(huán)次數(shù)為偶數(shù)，結(jié)束內(nèi)層循環(huán)；S5：對每個社區(qū)進(jìn)行連通性檢查，若不連通，則切分成多個連通的子圖，每個連通的子圖作為獨(dú)立社區(qū)；S6：對所有社區(qū)進(jìn)行壓縮，把每個社區(qū)壓縮成一個節(jié)點(diǎn)；S7：將步驟S6的結(jié)果輸入步驟S2，重復(fù)步驟S3至S6，直至圖的模塊度不再變化或變化的百分比小于第三閾值時，輸出結(jié)果。

技術(shù)領(lǐng)域

本發(fā)明涉及數(shù)據(jù)挖掘技術(shù)領(lǐng)域，特別涉及一種基于Louvain算法的社區(qū)發(fā)現(xiàn)方法、計算機(jī)設(shè)備及其可讀存儲介質(zhì)。

背景技術(shù)

復(fù)雜網(wǎng)絡(luò)是復(fù)雜系統(tǒng)的抽象，現(xiàn)實中許多復(fù)雜系統(tǒng)都可以用復(fù)雜網(wǎng)絡(luò)的相關(guān)特性進(jìn)行描述和分析，如萬維網(wǎng)、社會關(guān)系網(wǎng)絡(luò)等。其中，網(wǎng)絡(luò)中的節(jié)點(diǎn)表示系統(tǒng)中的個體，邊表示個體間的關(guān)系。復(fù)雜網(wǎng)絡(luò)一直是許多領(lǐng)域的研究熱點(diǎn)，其中社區(qū)結(jié)構(gòu)是復(fù)雜網(wǎng)絡(luò)中的一個普遍特征，研究網(wǎng)絡(luò)中的社區(qū)對理解整個網(wǎng)絡(luò)的結(jié)構(gòu)和功能起到至關(guān)重要的作用，并且可幫助我們分析與預(yù)測整個網(wǎng)絡(luò)各元素間的交互關(guān)系。

對社區(qū)發(fā)現(xiàn)的研究自Newman于2002年提出“社區(qū)”與模塊度概念以來有了快速的發(fā)展，大體可分為圖分割、圖聚類、節(jié)點(diǎn)表達(dá)等幾個方向，影響力最大的幾個算法包括Louvain算法、標(biāo)簽傳播算法、Infomap算法。

標(biāo)簽傳播算法：該算法使用鄰居節(jié)點(diǎn)的信息來決定當(dāng)前節(jié)點(diǎn)的社區(qū)，并且可以應(yīng)用到重疊社區(qū)（Overlapping）的發(fā)現(xiàn)中，但會存在結(jié)果震蕩、性能不穩(wěn)定等問題。

Louvain算法：該算法是一種基于Modularity優(yōu)化的啟發(fā)式算法，它的優(yōu)點(diǎn)是快速、準(zhǔn)確，且能發(fā)現(xiàn)社區(qū)的層級結(jié)構(gòu)，被認(rèn)為是性能最好的社區(qū)發(fā)現(xiàn)算法之一。同時，因為該算法會不斷對社區(qū)進(jìn)行壓縮并構(gòu)造新圖，所以計算量較小，能支持大規(guī)模的復(fù)雜網(wǎng)絡(luò)。

Infomap算法：該算法從編碼的角度，在發(fā)現(xiàn)網(wǎng)絡(luò)的一種最優(yōu)的二級編碼的同時，獲取對應(yīng)的社區(qū)結(jié)構(gòu)。算法思路類似于Louvain算法，但沒有壓縮社區(qū)構(gòu)造新圖的步驟，計算量較大。

標(biāo)簽傳播算法的優(yōu)點(diǎn)在于實現(xiàn)簡單直觀，但準(zhǔn)確性一般且性能不穩(wěn)定；Infomap算法準(zhǔn)確性較高但計算量較大；Louvain算法準(zhǔn)確性良好且計算量較小，更適合大規(guī)模的復(fù)雜網(wǎng)絡(luò)。但是，公開的Louvain算法為串行化算法，無法在分布式計算系統(tǒng)中應(yīng)用。

發(fā)明內(nèi)容

基于此，有必要提供一種效率更高的基于Louvain算法的社區(qū)發(fā)現(xiàn)方法、計算機(jī)設(shè)備及其可讀存儲介質(zhì)。

本發(fā)明實施例一方面提供一種基于Louvain算法的社區(qū)發(fā)現(xiàn)方法，其包括如下步驟:

S1：根據(jù)輸入數(shù)據(jù)生成用于表征網(wǎng)絡(luò)結(jié)構(gòu)的圖，圖包括節(jié)點(diǎn)以及連接節(jié)點(diǎn)的邊,將圖存儲于數(shù)據(jù)結(jié)構(gòu)中；

S2：將圖中的每個節(jié)點(diǎn)作為一個獨(dú)立的社區(qū)；

S3：進(jìn)行內(nèi)層循環(huán)，更新每個節(jié)點(diǎn)的歸屬社區(qū)；

S4：重復(fù)步驟S3，直到所述圖的模塊度變化的百分比小于第一閾值且當(dāng)前循環(huán)次數(shù)為偶數(shù)，或者內(nèi)層循環(huán)次數(shù)大于第二閾值且當(dāng)前循環(huán)次數(shù)為偶數(shù)，結(jié)束內(nèi)層循環(huán)；

S5：對每個社區(qū)進(jìn)行連通性檢查，若不連通，則把它切分成多個連通的子圖，每個連通的子圖作為一個獨(dú)立的社區(qū)；

S6：對社區(qū)進(jìn)行壓縮，把每個社區(qū)壓縮成一個節(jié)點(diǎn)；

S7：將步驟S6的結(jié)果輸入步驟S2，并重復(fù)步驟S3至S6，直至所述圖的模塊度不再變化或者變化的百分比小于第三閾值時，輸出結(jié)果。