[發明專利]動態網絡的社團劃分方法及裝置

在審

• 申請號: 201611074435.6
• 申請日: 2016-11-29
• 公開（公告）號: CN106780058A
• 公開（公告）日: 2017-05-31
• 發明（設計）人: 時巖;趙靜文;陳濱;陳山枝
• 申請（專利權）人: 北京郵電大學
• 主分類號: G06Q50/00
• 分類號: G06Q50/00;H04L12/24
• 代理公司: 北京同立鈞成知識產權代理有限公司11205
• 代理人: 張洋,黃健

1.一種動態網絡的社團劃分方法，其特征在于，包括：

獲取動態網絡分別在至少兩個時刻的網絡拓撲結構，所述動態網絡包括多個節點，每個節點屬于一個社團；

分別以所述多個節點中的每一個節點作為目標節點，遍歷每個目標節點，執行以下步驟：

在每個網絡拓撲結構中，計算所述目標節點分別與其相鄰的每個節點的模塊度增量，所述目標節點與其相鄰的節點的模塊度增量為所述目標節點移動到所述相鄰的節點所屬的社團時產生的模塊度增量；

根據每個網絡拓撲結構的權重，以及每個網絡拓撲結構中，所述目標節點與同一個相鄰節點的模塊度增量，計算所述目標節點與同一個相鄰節點的平均模塊度增量；

比較所述目標節點與各個相鄰節點的平均模塊度增量；

若所述目標節點與所述相鄰節點的平均模塊度增量最大，且最大的所述平均模塊度增量為正值，則在每個網絡拓撲結構中，將所述目標節點移動到該所述相鄰節點所屬的社團中；

遍歷每個目標節點結束后，分別以每個網絡拓撲結構中的每個社團作為目標節點，重復遍歷每個目標節點，直到每個網絡拓撲結構中的任意兩個社團均無法繼續合并為止。

2.根據權利要求1所述的方法，其特征在于，所述獲取動態網絡分別在至少兩個時刻的網絡拓撲結構，包括：

獲取動態網絡在一時間段內至少兩個時刻的網絡拓撲結構；

所述每個網絡拓撲結構的權重為所述網絡拓撲結構對應的時刻在所述時間段內的時間順序，與所述時間段內獲取到的所述網絡拓撲結構的總數的比值。

3.根據權利要求2所述的方法，其特征在于，所述目標節點與同一個相鄰節點的平均模塊度增量，根據公式(1)確定：

${\mathrm{\ΔQ}}_{avg}=\frac{1}{{\mathrm{\Σ}}_{I\∈N}{w}_I}{\mathrm{\Σw}}_I\·{\mathrm{\ΔQ}}_I---\left(1\right)$

其中，ΔQ_avg表示所述平均模塊度增量，N表示所述時間段內的N個時刻，I表示所述N個時刻中的第I個時刻，w_I表示第I個時刻對應的所述網絡拓撲結構的權重，ΔQ_I表示在第I個時刻對應的所述網絡拓撲結構中，所述目標節點與所述同一個相鄰節點的模塊度增量。