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

在審

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

1.一種基于Louvain算法的社區(qū)發(fā)現(xiàn)方法，其特征在于，包括如下步驟：

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

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

S3：進(jìn)行內(nèi)層循環(huán)，更新每個(gè)節(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：對(duì)每個(gè)社區(qū)進(jìn)行連通性檢查，若不連通，則把它切分成多個(gè)連通的子圖，每個(gè)連通的子圖作為一個(gè)獨(dú)立的社區(qū)；

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

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

2.根據(jù)權(quán)利要求1所述的基于Louvain算法的社區(qū)發(fā)現(xiàn)方法，其特征在于，在步驟S1和步驟S2之間，還包括步驟S12：對(duì)所述圖進(jìn)行連通性檢查，若不連通則把所述圖切分成多個(gè)連通的子圖。

3.根據(jù)權(quán)利要求1所述的基于Louvain算法的社區(qū)發(fā)現(xiàn)方法，其特征在于，步驟S3進(jìn)一步包括如下步驟：

S31：對(duì)每個(gè)節(jié)點(diǎn)i，計(jì)算其候選社區(qū)集合S_i，候選社區(qū)集合S_i由所有鄰居節(jié)點(diǎn)所在的社區(qū)與節(jié)點(diǎn)i當(dāng)前所在的社區(qū)構(gòu)成；

S32：對(duì)每個(gè)節(jié)點(diǎn)i，依次嘗試將其挪入S_i的每個(gè)社區(qū)，計(jì)算該節(jié)點(diǎn)i作為一個(gè)獨(dú)立社區(qū)挪入新社區(qū)C_j后的模塊度相對(duì)變化，Q為模塊度；

S33：記錄的最大值與對(duì)應(yīng)的新社區(qū)編號(hào)C_j，若內(nèi)層循環(huán)次數(shù)k為偶數(shù)，則僅當(dāng)原社區(qū)編號(hào) C_i>C_j時(shí)，才把當(dāng)前節(jié)點(diǎn)i的社區(qū)編號(hào)更新為C_j，否則社區(qū)編號(hào)不變；若內(nèi)層循環(huán)次數(shù)k為奇數(shù)，則僅當(dāng)原社區(qū)編號(hào) C_i≤C_j時(shí)才把當(dāng)前節(jié)點(diǎn)的社區(qū)編號(hào)更新為C_j，否則社區(qū)編號(hào)不變;

上述S31、S32、S33步驟均基于k-1次內(nèi)層循環(huán)后的狀態(tài)進(jìn)行計(jì)算并進(jìn)行同步更新。

4.根據(jù)權(quán)利要求3所述的基于Louvain算法的社區(qū)發(fā)現(xiàn)方法，其特征在于，在步驟S32中：

當(dāng)C_i≠C_j時(shí)：；（公式1）

在公式（1）中，是節(jié)點(diǎn)i與新社區(qū)C_j中節(jié)點(diǎn)連邊的權(quán)重之和；為節(jié)點(diǎn)i的度數(shù)；為新社區(qū)C_j中所有節(jié)點(diǎn)的度數(shù)之和；M是當(dāng)前連通圖中所有節(jié)點(diǎn)的度數(shù)之和；

當(dāng)C_i=C_j時(shí)：；（公式2）

在公式（2）中，是節(jié)點(diǎn)i與社區(qū)C_i中其他節(jié)點(diǎn)連邊的權(quán)重之和；為節(jié)點(diǎn)i的度數(shù)；為新社區(qū)C_j中所有節(jié)點(diǎn)的度數(shù)之和；M是當(dāng)前連通圖中所有節(jié)點(diǎn)的度數(shù)之和。

5.根據(jù)權(quán)利要求1所述的基于Louvain算法的社區(qū)發(fā)現(xiàn)方法，其特征在于，在步驟S6中，將被壓縮社區(qū)內(nèi)不同節(jié)點(diǎn)的連邊作為壓縮后節(jié)點(diǎn)的自連邊，將被壓縮社區(qū)內(nèi)同一節(jié)點(diǎn)的自連邊作為壓縮后節(jié)點(diǎn)的自連邊，將壓縮后節(jié)點(diǎn)的所有自連邊合并為一條邊，邊權(quán)重為該壓縮后節(jié)點(diǎn)的所有自連邊的權(quán)重之和。

6.根據(jù)權(quán)利要求1所述的基于Louvain算法的社區(qū)發(fā)現(xiàn)方法，其特征在于，所述第三閾值大于或等于第一閾值。

7.一種計(jì)算機(jī)設(shè)備，包括存儲(chǔ)器、處理器以及存儲(chǔ)在存儲(chǔ)器上并可在處理器上運(yùn)行的計(jì)算機(jī)程序，其特征在于，所述處理器執(zhí)行所述計(jì)算機(jī)程序時(shí)實(shí)現(xiàn)權(quán)利要求1至6任一項(xiàng)所述方法的步驟。

8.一種計(jì)算機(jī)設(shè)備可讀存儲(chǔ)介質(zhì)，其上存儲(chǔ)有計(jì)算機(jī)程序，其特征在于：所述計(jì)算機(jī)程序被處理器執(zhí)行時(shí)實(shí)現(xiàn)權(quán)利要求1至6任一項(xiàng)所述方法的步驟。