[發明專利]一種社交網絡中的動態社區檢測方法

有效

• 申請號: 201310725401.9
• 申請日: 2013-12-25
• 公開（公告）號: CN103678671A
• 公開（公告）日: 2014-03-26
• 發明（設計）人: 陳羽中;陳國龍;郭文忠;邱曉輝
• 申請（專利權）人: 福州大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 福州元創專利商標代理有限公司 35100
• 代理人: 蔡學俊

1.一種社交網絡中的動態社區檢測方法，其特征在于，所述方法包括以下步驟：

步驟A：獲取社交網絡一時刻t_i-1的快照數據，作為初始的社交網絡快照，并構造以社交網絡用戶為節點、用戶關系為邊的社交網絡圖G_i-1=(V_i-1,?E_i-1)，V_i-1表示時刻t_i-1的社交網絡圖G_i-1的節點集合，E_i-1表示時刻t_i-1的社交網絡圖G_i-1的邊集合；

步驟B：對于時刻t_i-1的社交網絡圖G_i-1，進行社區劃分，獲得社交網絡在時刻t_i-1的社區結構；

步驟C：順序獲取社交網絡下一時刻t_i的快照數據，構造社交網絡圖G_i=(V_i,?E_i)，V_i表示時刻t_i的社交網絡圖G_i的節點集合，E_i表示時刻t_i的社交網絡圖G_i的邊集合，然后獲得時刻t_i的社交網絡圖G_i與上一時刻t_i-1的社交網絡圖G_i-1相比發生變化的節點集合，即增量節點集合VC_i；

步驟D：根據所述增量節點集合VC_i，計算增量節點占節點總數的比例，即增量節點比例；

步驟E：根據所述增量節點比例，若增量節點比例大于設定閾值，則對社交網絡圖G_i中所有的節點重新進行社區劃分，若增量節點比例小于設定閾值，則社交網絡圖G_i中不屬于增量節點集合的節點維持原有的標簽不變，保持原來的社區歸屬，僅對屬于增量節點集合的節點進行社區劃分，更新增量節點集合中節點的社區標簽；社區劃分結束后，根據每個節點所擁有的社區標簽，將擁有相同標簽的節點歸屬到同一社區，獲得社交網絡在時刻t_i的社區結構。

2.根據權利要求1所述的一種社交網絡中的動態社區檢測方法，其特征在于，所述步驟B中，使用靜態標簽傳播方法進行社區劃分，具體包括以下步驟：

步驟B1：根據社交網絡圖，通過密度聚類方法進行節點標簽初始化，為社交網絡圖中的每個節點分配一個標簽；

步驟B2：根據標簽更新規則，對社交網絡圖中的每個節點進行標簽更新，反復迭代，直到滿足迭代終止條件；

步驟B3：根據迭代終止時節點所分配的標簽，將具有相同標簽的節點歸屬到同一社區，輸出社區結構。