[發明專利]一種二分網絡中社團檢測方法及裝置

有效

• 申請號: 201010108846.9
• 申請日: 2010-02-04
• 公開（公告）號: CN102148717A
• 公開（公告）日: 2011-08-10
• 發明（設計）人: 明仲
• 申請（專利權）人: 明仲
• 主分類號: H04L12/26
• 分類號: H04L12/26
• 代理公司: 深圳市君勝知識產權代理事務所 44268
• 代理人: 王永文

1.一種二分網絡中社團檢測方法，其特征在于，所述方法包括以下步驟：

獲取二分網絡的節點集，所述節點集由多個社團構成，所述社團包括同一類型的多個節點；

獲取所述節點集的模塊度值，其中，所述模塊度值為對屬于同一類型的所有節點對之間的所有路徑長度之和的差異值取和；

對二分網絡中的每個社團的任一節點，計算該節點從當前其所屬的社團移動到所述節點集的其它社團時，所述二分網絡的節點集的模塊度值的增加量；

選取使得所述二分網絡的節點集的模塊度值的增加量最大的社團作為該節點的新的劃分社團；

根據新的劃分出的社團重新構造二分網絡。

2.如權利要求1所述的二分網絡中社團檢測方法，其特征在于，所述獲取所述節點集的模塊度值時，使用以下計算公式：

Q=Σi=1pΣj=1p(Σa=1qwiawja-Σa=1qma2·titjm2)δ(gi,gj)]]>

其中，Q為模塊度，所述二分網絡中存在兩種類型的節點A和B，屬于類型A的節點的數目為p，屬于類型B的節點的數目為q；節點i屬于類型A，節點j屬于類型B；與i連接的所有邊的權重之和表示為t_i，與j連接的所有邊的權重之和表示為t_j；網絡中所有邊的權重之和為m；節點i和j屬于同一個社團，δ(g_i，g_j)的值為1；w_iaw_ja表示從節點i出發經過鄰居節點a，再到節點j的一條路徑的長度；表示從節點i到節點j的所有路徑的長度之和；從節點i到節點a的邊的權重；從節點a到節點j的邊的權重；從節點i出發經過節點a再到節點j的一條路徑的長度；從節點i到節點j的所有路徑的長度之和；表示一個節點對(i，j)之間的所有路徑長度之和的差異值。

3.如權利要求1所述的二分網絡中社團檢測方法，其特征在于，在所述獲取二分網絡中的每個類型的節點集的步驟之前，所述方法還包括：

獲取二分網絡中的各個節點；

將獲取的節點按照類型組成相應的社團，其中，每個類型的節點組成一個社團；所述多個社團構成二分網絡中的節點集。

4.如權利要求1所述的二分網絡中社團檢測方法，其特征在于，所述方法還包括：

判斷是否有節點移動，若是，則繼續進行以下步驟：計算該節點從當前其所屬的社團移動到所述節點集的其它社團時，所述二分網絡的各個社團模塊度值的增加量；

若沒有節點移動，則進行如下步驟：根據新的劃分出的社團重新構造二分網絡。