[發明專利]動態網絡社區結構的更新方法及裝置

有效

• 申請號: 201210185451.8
• 申請日: 2012-06-06
• 公開（公告）號: CN102722750A
• 公開（公告）日: 2012-10-10
• 發明（設計）人: 尚家興;劉連臣;謝峰;陳安燕;徐磊
• 申請（專利權）人: 清華大學
• 主分類號: G06N3/00
• 分類號: G06N3/00
• 代理公司: 北京清亦華知識產權代理事務所(普通合伙) 11201
• 代理人: 張大威

1.一種動態網絡社區結構的更新方法，其特征在于，包括以下步驟：

對由多個節點組成的初始網絡進行計算，以生成網絡初始社區結構；

根據節點之間的交互判斷新加入的邊的類型，其中，所述新加入的邊的類型包括社區內部邊、跨社區的邊、半新邊和全新邊；以及

根據所述新加入的邊的類型選擇對應的增量更新策略對所述網絡初始社區結構進行更新以得到網絡更新社區結構。

2.根據權利要求1所述的動態網絡社區結構的更新方法，其特征在于，所述增量更新策略的選擇依據為：

選擇使得網絡初始社區結構的Modularity值的增量最大的增量更新策略。

3.根據權利要求2所述的動態網絡社區結構的更新方法，其特征在于，所述增量更新策略的選擇依據進一步包括：

如果不存在對所述網絡初始社區結構的Modularity值帶來增量的增量更新策略，則選擇使得網絡初始社區結構的Modularity值的減少量最小的增量更新策略。

4.根據權利要求1所述的動態網絡社區結構的更新方法，其特征在于，所述網絡初始社區結構是通過LOUVAIN算法得到的。

5.根據權利要求1所述的動態網絡社區結構的更新方法，其特征在于，所述增量更新策略包括保持社區結構不變的更新策略、將兩個社區合并為一個社區的更新策略、將新加入的節點加入到已存在的社區的更新策略以及創建新社區的更新策略。

6.根據權利要求5所述的動態網絡社區結構的更新方法，其特征在于，根據所述新加入的邊的類型選擇對應的增量更新策略對所述網絡初始社區結構進行更新的步驟進一步包括：

如果所述新加入的邊為社區內部邊，則選擇保持社區結構不變的更新策略；

如果所述新加入的邊為跨社區的邊，則選擇保持社區結構不變的更新策略或者選擇將兩個社區合并為一個社區的更新策略；

如果所述新加入的邊為半新邊，則選擇將新加入的節點加入到已存在的社區的更新策略；以及

如果所述新加入的邊為全新邊，則選擇創建新社區的更新策略對所述網絡初始社區結構進行更新。

7.根據權利要求6所述的動態網絡社區結構的更新方法，其特征在于，如果所述新加入的邊為跨社區的邊，則選擇保持社區結構不變的更新策略或者選擇將兩個社區合并為一個社區的更新策略的步驟進一步包括：

在所述保持社區結構不變的更新策略和將兩個社區合并為一個社區的更新策略中選擇使得網絡初始社區結構的Modularity值的增量較大的增量更新策略。

8.一種動態網絡社區結構的更新裝置，其特征在于，包括：

網絡初始社區結構生成模塊，用于對由多個節點組成的初始網絡進行計算以生成網絡初始社區結構；

判斷模塊，用于根據節點之間的交互判斷新加入的邊的類型，其中，所述新加入的邊的類型包括社區內部邊、跨社區的邊、半新邊和全新邊；以及

更新模塊，用于根據所述新加入的邊的類型選擇對應的增量更新策略對所述網絡初始社區結構進行更新以得到網絡更新社區結構。

9.根據權利要求8所述的動態網絡社區結構的更新裝置，其特征在于，所述更新模塊的增量更新策略的選擇依據為：

選擇使得網絡初始社區結構的Modularity值的增量最大的增量更新策略。

10.根據權利要求9所述的動態網絡社區結構的更新裝置，其特征在于，所述增量更新策略的選擇依據進一步包括：

如果不存在對所述網絡初始社區結構的Modularity值帶來增量的增量更新策略，則選擇使得網絡初始社區結構的Modularity值的減少量最小的增量更新策略。

11.根據權利要求8所述的動態網絡社區結構的更新裝置，其特征在于，所述網絡初始社區結構是通過LOUVAIN算法得到的。

12.根據權利要求8所述的動態網絡社區結構的更新裝置，其特征在于，所述增量更新策略包括保持社區結構不變的更新策略、將兩個社區合并為一個社區的更新策略、將新加入的節點加入到已存在的社區的更新策略以及創建新社區的更新策略。