[發明專利]一種基于平均互信息的快速社區發現方法及系統

在審

• 申請號: 201910117812.7
• 申請日: 2019-02-15
• 公開（公告）號: CN109902728A
• 公開（公告）日: 2019-06-18
• 發明（設計）人: 李東;葉文彬;程鳴權
• 申請（專利權）人: 華南理工大學
• 主分類號: G06K9/62
• 分類號: G06K9/62;G06Q50/00
• 代理公司: 廣州粵高專利商標代理有限公司 44102
• 代理人: 何淑珍;黃海波

1.一種基于平均互信息的快速社區發現方法，其特征在于，包括以下步驟：

S1、服務器接收社區劃分請求；

S2、初始化節點所屬社區，為每個節點分配唯一的社區；

S3、獲取當前網絡結構中所有存在連接的社區組合；

S4、從社區組合選出起始社區組合開始進行遍歷；

S5、計算兩個社區合并時的平均互信息值I_p和模塊度增量值ΔQ，計算加權修正后的平均互信息值CI_p并進行記錄；

S6、若當前網絡結構中存在連接的社區組合遍歷完畢時，則進行步驟S7，否則選擇下一個社區組合并返回步驟S5；

S7、選擇步驟S6中計算的修正后的平均互信息值CI_p最大的社區組合進行合并；

S8、計算并記錄本次社區劃分過程中的平均互信息值；

S9、若當前網絡中所有節點屬于同一社區時，則進行步驟S10，否則返回步驟S3；

S10、選擇步驟S8中記錄的平均互信息的最大值所對應社區劃分結果作為最終社區劃分結果并輸出。

2.根據權利要求1所述的一種基于平均互信息的快速社區發現方法，其特征在于，步驟S2中所述初始化節點所屬社區的具體操作為：將每個節點都設置為一個社區，即初始化后社區個數等于節點個數。

3.根據權利要求1所述的一種基于平均互信息的快速社區發現方法，其特征在于，所述步驟S3的具體過程為：找出所有符合社區合并條件的社區組合，即只有當前網絡中有連接的兩個社區才有可能進行社區合并，若兩個社區之前沒有連接，則無法進行社區合并。

4.根據權利要求1所述的一種基于平均互信息的快速社區發現方法，其特征在于，步驟S5中，所述平均互信息值I_P的計算公式為：

其中，X_i表示社區結構X中的第i個社區，Y_j表示社區結構Y中的第j個社區，I(X_i；Y_j)表示社區X_i與社區Y_j的平均互信息值，ω_ij表示X_i社區和Y_j社區的關聯性；

所述模塊度增量值ΔQ的計算公式為：

ΔQ＝(e_ji+e_ij-2a_i*a_j)＝2(e_ij-2a_i*a_j)，

其中a_i＝∑_je_ij表示與社區i中節點相連的邊占所有邊的比例；a_j＝∑_ie_ji表示與社區j中節點相連的邊占所有邊的比例；e_ij表示一個節點在社區i內，另一個節點在社區j內的邊的數量；e_ji表示一個節點在社區j內，另一個節點在社區i內的邊的數量，即等于e_ij；

所述修正后的平均互信息值CI_p計算公式為：

CI_p＝β·I_p+(1-β)·ΔQ，

其中，C為標識符號，表示該平均互信息值為修正后的值；β為預設參數，表示社區合并時考慮節點信息的多少，β越大，則表示考慮社區的節點信息越多，考慮社區的連接信息越少；β的預設值取值范圍為0～1，實際使用時需根據對具體社區節點信息和連接信息的考慮權重進行設定。

5.根據權利要求1所述的一種基于平均互信息的快速社區發現方法，其特征在于，步驟S7中，選擇修正后平均互信息值CI_p最大的社區組合進行合并時，由于修正后平均互信息值考慮了復雜網絡中的節點信息與連接信息，因此此時可以選出最優社區組合進行合并。