[發明專利]基于隨機游走邊界域處理的三支決策社團劃分方法及裝置

在審

• 申請號: 201811045237.6
• 申請日: 2018-09-07
• 公開（公告）號: CN109242713A
• 公開（公告）日: 2019-01-18
• 發明（設計）人: 陳潔;李洋;趙姝;段震;張燕平
• 申請（專利權）人: 安徽大學
• 主分類號: G06Q50/00
• 分類號: G06Q50/00;G06K9/62
• 代理公司: 合肥市浩智運專利代理事務所(普通合伙) 34124
• 代理人: 丁瑞瑞

1.一種基于隨機游走邊界域處理的三支決策社團劃分方法，其特征在于，所述方法包括：

1)、將獲取的待進行社團劃分的網絡抽象成由節點連接成的抽象網絡；

2)、針對所述抽象網絡中的每一個節點，根據所述節點的連接屬性，對所述抽象網絡初始?；筮M行聚類粒化，并將聚類?；蟪橄缶W絡的結構關系作為第一劃分結果，其中，所述連接屬性，包括：所述節點與其它節點的連接關系；

3)、計算每一粒層分別對應的重疊社團模塊度，并獲取重疊社團模塊度最大值對應的抽象網絡的第一劃分結果，其中，所述重疊社團為，具有相同節點的社團，且粒層為對應不同的預設?；禂档牡谝粍澐纸Y果；

4)、將所述第一劃分結果中各個劃分后社團的重疊部分作為邊界域；并利用隨機游走算法對所述邊界域中的所有節點進行劃分，更新所述第一劃分結果以及所述邊界域，直至所述第一劃分結果以及所述邊界域的更新次數達到預設次數；

5)、針對更新后的所述邊界域中的每一個節點，使用三支決策法進行處理，獲得第二劃分結果，并將所述第二劃分結果作為目標劃分結果。

2.根據權利要求1所述的一種基于隨機游走邊界域處理的三支決策社團劃分方法，其特征在于，所述1)步驟，包括：

將獲取的待進行社團劃分的網絡中的每一個通過網絡相互連接的個體抽象成一個節點，然后將各個節點之間的連接鏈路抽象成節點之間的連接線。

3.根據權利要求1所述的一種基于隨機游走邊界域處理的三支決策社團劃分方法，其特征在于，所述2)步驟，包括：

A：針對所述抽象網絡中的每一個節點，將所述節點作為中心節點，獲取所述中心節點的鄰居節點的集合，并判斷所述中心節點的以及所述鄰居節點構成的網絡中是否存在僅通過所述中心節點連接的由節點構成的社團；若是，獲取所述中心節點的以及所述鄰居節點構成的網絡中所包含的，除所述中心節點外社團之間無連接關系的各個社團，并將所述各個社團作為劃分后社團；若否，將所述中心節點的以及所述鄰居節點構成的網絡作為劃分后社團。

B：針對預設數量個預設?；禂抵械拿恳粋€預設粒化系數，針對所述劃分后社團構成的集合中的每一對存在連接關系的劃分后社團，獲取所述存在連接關系的劃分后社團分別對應的?；禂?，進而獲取所述粒化系數中的最大值，若所述?；禂抵械淖畲笾挡恍∮陬A設粒化系數，將所述存在連接關系的劃分后社團合并成為一個社團，直至所述劃分后社團構成的集合中任一對存在連接關系的劃分后社團的粒化系數均小于所述預設粒化系數；將獲得的社團的結構關系作為第一劃分結果。

4.根據權利要求1所述的一種基于隨機游走邊界域處理的三支決策社團劃分方法，其特征在于，所述3)步驟之前，所述方法還包括：

對所述第一劃分結果進行去重處理。

5.根據權利要求1所述的一種基于隨機游走邊界域處理的三支決策社團劃分方法，其特征在于，所述3)步驟，包括：

利用公式，獲取每一個預設粒化系數分別對應的重疊社團模塊度，其中，

EQ為每一個預設?；禂捣謩e對應的重疊社團模塊度；m為所述抽象網絡中包含的邊的數量；G_r為每一預設粒化系數對應的社團劃分結果中的各個劃分后社團；i為第i個節點的序號；j為第j個節點的序號；o_i為第i個節點所屬劃分后社團的數量；o_j為第j個節點所屬劃分后社團的數量；A_ij為所述抽象網絡對應的鄰接矩陣元素；d_i為第i個節點的度；d_j為第j個節點的度。