[發明專利]一種基于邊不穩定度的社區發現系統及方法

有效

• 申請號: 201611150384.0
• 申請日: 2016-12-14
• 公開（公告）號: CN106599187B
• 公開（公告）日: 2020-06-16
• 發明（設計）人: 王雷;王新晨;李涵
• 申請（專利權）人: 北京航空航天大學
• 主分類號: G06F16/28
• 分類號: G06F16/28;G06Q50/00
• 代理公司: 北京科迪生專利代理有限責任公司 11251
• 代理人: 楊學明;顧煒

1.一種基于邊不穩定度的社區發現系統，其特征在于包括：邊不穩定度計算模塊、基于邊不穩定度的Fast Unfolding社區發現模塊、基于邊不穩定度的GN社區發現模塊和結果整合模塊；其中：

邊不穩定度計算模塊：接收函數調用圖的結構數據，計算函數調用圖的節點穩定度和邊不穩定度，并將計算結果保存入文件中，供后續社區發現模塊使用；所述邊不穩定度由節點的穩定度決定；節點的穩定度定義為節點的入度與節點度的比值，有向邊的不穩定度定義為源點的穩定度與終點的穩定度之差；節點的穩定度表現為，穩定度高的節點具有入度較出度相對更大的特點，函數調用圖中這樣的節點將更不易把改變擴散到其他節點處，因此稱節點穩定性較大，由穩定性大的節點指向穩定性小的節點的邊就具有較大的不穩定度，因為它容易把改變擴散出去；

基于邊不穩定度的Fast Unfolding社區發現模塊：根據邊不穩定度計算模塊的計算結果，采用改進的Fast Unfolding的算法，即在Fast Unfolding的算法中加入邊不穩定度決定性，使得社區的劃分根據參數大小而受邊不穩定度的影響，得到社區劃分結果E1并保存入文件中，為后續操作提供數據；

基于邊不穩定度的GN社區發現模塊：根據邊不穩定度的計算結果，采用改進的基于邊不穩定度的GN算法，即在GN算法的算法中計算邊介數改為計算邊不穩定度，在社區發現的過程中使用邊不穩定度尋找合適的劃分，得到社區劃分結果E2并保存入文件中，為后續操作提供數據；

結果整合模塊：將社區劃分結果E1和E2，合并成一個待處理結果E，掃描該結果，綜合考量各個節點的社區信息和節點信息，對于兩次劃分結果不一致的節點，進行社區的微調，最后得到函數調用圖基于邊不穩定度的社區發現結果；

所述邊不穩定度計算模塊中，

節點的穩定度計算公式如下：

其中和是節點n_i的入度和出度，S_i的值介于0到1之間，當S_i越大時，意味著節點n_i的出度越??；

邊的不穩定度計算公式如下：

I_ij＝S_i-S_j

其中S_i和S_j分別是節點n_i和n_j的節點穩定度，當I_ij越大時，對應的邊會將改變更快的擴展出去；

所述基于邊不穩定度的Fast Unfolding社區發現模塊具體步驟如下：

(1)計算網絡中每條邊的不穩定度，從邊不穩定度計算模塊的結果中提取邊不穩定度結果，加入到函數調用圖中相應邊的屬性中；

(2)初始化網絡節點，每個節點均為一個社區，所以初始狀態下函數調用圖中社區數目與節點數相同；對于每個節點，隨機將其歸入其任一鄰居節點中，計算模塊度增量ΔQ和邊不穩定度增量ΔI，對于某歸一化參數α，取使得α×ΔQ+(1-α)×ΔI獲得最大值的劃分方案，作為本次劃分的最后結果，所有節點均獲得新的社區劃分或者維持原有劃分不變，根據節點的劃分結果，得到新的社區信息，即所有屬于同一劃分的節點都屬于同一社區；

(3)將步驟(2)得到的所有社區抽象為新的節點，重復步驟(2)的操作，直到沒有新的劃分可以得到正的綜合增量α×ΔQ+(1-α)×ΔI時，此時網絡中所有節點的劃分便結束，且所有節點均有確定的社區信息，將社區信息相同的節點并入同一社區，便得到社區劃分結果E1，最后保存到文件中；

所述基于邊不穩定度的GN社區發現模塊具體步驟如下：

(1)計算函數調用圖中每條邊的不穩定度，從邊不穩定度計算模塊的結果中提取邊不穩定度結果，加入到網絡中相應邊的屬性中；

(2)對網絡中的節點按照邊不穩定度降序排列；

(3)對于排列好的邊，每次移除一定數量的邊，直到函數調用圖中的弱聯通子圖數目增加，并計算網絡模塊度增量，記錄當前的狀態；

(4)重復步驟(3)，直至網絡中所有邊都被移除，回溯尋找每一次執行步驟(3)后，網絡的模塊度以及相應的弱聯通子圖信息，選出模塊度最大的一次劃分，則此次劃分得到所有弱聯通子圖便是網絡的最佳社區劃分結果，即每一個弱聯通子圖都是一個社區，至此得到函數調用圖的社區劃分結果E2，保存到文件中；

所述結果整合模塊中，進行社區的微調，最后得到函數調用圖基于邊不穩定度的社區發現結果如下：在劃分結果E1中，節點n_i和n_j屬于不同社區，而劃分結果E2中此二節點屬于同一社區，則根據它們各自帶有的額外信息進行判斷，以決定采用E1還是E2的方案。