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

在審

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

本發明涉及基于密度峰值與社區歸屬度的重疊社區發現方法，包括以下步驟：步驟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：輸出最終的社區劃分結果。

技術領域

本發明涉及復雜網絡上的重疊社區發現技術領域，具體涉及一種基于密度聚類的重疊社區發現方法。

背景技術

在現實世界中存在大量復雜網絡，如社交網絡、生物網絡、文獻引用網絡。研究表明，這些復雜網絡普遍存在著一定的社區結構，各社區內部節點連接較為緊密，社區間連接較為稀疏。社區發現研究的就是如何準確的識別出復雜網絡中的社區結構。

傳統的社區發現算法是將網絡劃分成若干個互不相連的社區，網絡中每個節點和邊只能隸屬一個固定社區。包括模塊度優化方法，層次聚類算法，標簽傳播算法和信息論算法。.然而，真實網絡中，社區之間通常是互相交叉，彼此聯系的，這種情形下，網絡中的節點不再僅隸屬于單個社區，而是同時被包含到多個相關聯的社區中。因而，研究重疊社區結構具有更重要意義。

目前，重疊社區發現算法主要包括基于派系過濾的算法、基于局部社區的算法、基于多標簽傳播的算法和基于鏈接聚類的算法等。這些算法在社區結構明顯且大小均勻時可以較好的發現網絡社區結構，但對于社區大小不均以及形狀各異的網絡，上述算法的效果較差。所以就有研究員提出了基于密度峰值聚類的重疊社區發現算法。

目前已有一些學者對基于密度峰值聚類的重疊社區發現算法進行了研究，也取得了一定的成果，但仍然存在以下兩個問題：首先算法的時間復雜度相對較高，無法處理較大規模網絡；其次，在選取社區中心點時，需要人為指定社區中心點的局部密度閾值和跟隨距離閾值，這種方法無法很好的應用于較為復雜網絡結構。這兩個問題導致了社區發現的精度不高。

發明內容

有鑒于此，本發明的目的在于提供一種基于密度聚類的重疊社區發現方法，能夠準確的識別重疊社區結構，且具近似線性的時間復雜度，適用于大規模復雜網絡。

為實現上述目的，本發明采用如下技術方案：

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

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

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

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

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