[發明專利]基于密度峰值與社區歸屬度的重疊社區發現方法

在審

• 申請號: 201810880920.5
• 申請日: 2018-08-04
• 公開（公告）號: CN108959652A
• 公開（公告）日: 2018-12-07
• 發明（設計）人: 郭昆;彭勝波;郭文忠;陳羽中
• 申請（專利權）人: 福州大學
• 主分類號: G06F17/30
• 分類號: G06F17/30;G06Q50/00
• 代理公司: 福州元創專利商標代理有限公司 35100
• 代理人: 蔡學俊

1.基于密度峰值與社區歸屬度的重疊社區發現方法，其特征在于：包括以下步驟：

步驟S1:讀取網絡數據集，生成網絡圖G；

步驟S2：根據網絡圖G節點間的路徑長度來計算網絡中節點間距離、距離最大值d_max、距離最小值d_min，得到節點間距離字典Pd；

步驟S3：根據節點間距離字典Pd計算節點間的距離閾值d_c、節點的局部密度Rho；

步驟S4：根據節點間距離字典Pd、節點的局部密度Rho求取節點的跟隨節點Nnb和跟隨距離Del；

步驟S5：根據密度峰值聚類算法的原理生成非重疊社區集C；

步驟S6：對非重疊社區集C的邊界點進行社區歸屬判斷，得到重疊社區集C'；

步驟S7：輸出最終的社區劃分結果。

2.根據權利要求1所述的基于密度峰值與社區歸屬度的重疊社區發現方法，其特征在于：所述步驟S1具體為：讀取網絡數據集，生成用于劃分社區結構的網絡圖G＝(V,E)，其中V表示節點集，E表示邊集。

3.根據權利要求2所述的基于密度峰值與社區歸屬度的重疊社區發現方法，其特征在于：所述步驟S2具體為：

步驟S21:初始化節點間距離字典Pd為空；

步驟S22：遍歷V中每個節點v，再遍歷節點v的每個鄰居u，按公式(1)求出節點u，v間的距離d(u,v)，并把d(u,v)添加到距離字典Pd中；

其中，DNB(v)表示節點v的直接鄰居，；w表示節點v的直接鄰居節點；當u∈DNB(v)時，節點u，v間距離由長度為1的路徑所表示的距離和長度為2的路徑所表示的距離相加計算得到；而當時，節點u，v間距離只需考慮由長度為2的路徑所表示的距離；

步驟S23：遍歷節點u的每個鄰居r，按公式(2)求出節點r，v間的距離d(r,v)，并把d(r,v)添加到節點間距離字典Pd中；

步驟S24：求出節點間距離的最大值d_max、最小值d_min；

步驟S25：輸出節點間距離字典Pd、最大值d_max、最小值d_min。

4.根據權利要求3所述的基于密度峰值與社區歸屬度的重疊社區發現方法，其特征在于：所述步驟S3具體為：

步驟S31:初始化節點的局部密度字典Rho為空，網絡所有節點的d_c-鄰域內節點數nb及nb與網絡節點總數的比例np為0；

步驟S32：根據密度峰值聚類算法中距離閾值的選取規則計算閾值d_c；

步驟S33：根據d_c和公式(3)計算網絡中每個節點的局部密度；

其中，rho(u)表示節點u的局部密度，INB(u)表示節點u鄰居的鄰居。

步驟S34：輸出局部密度字典Rho，距離閾值d_c。

5.根據權利要求4所述的基于密度峰值與社區歸屬度的重疊社區發現方法，其特征在于：所述步驟S4具體為：

步驟S41：初始化局部密度列表Rl、節點跟隨鄰居字典Nnb，跟隨距離字典Del和鄰居節點集合NB為空；

步驟S42：將Rho中的元素逐個添加到Rl中，并對Rl按局部密度值大小降序排序，得到排序后的局部密度列表Rl；

步驟S43：根據密度峰值聚類算法的原理求取每個節點的跟隨鄰居和跟隨距離，得到跟隨鄰居字典Nnb，跟隨距離字典Del；

步驟S44：輸出節點跟隨鄰居字典Nnb，跟隨距離字典Del和排序后的局部密度列表Rl。