[發明專利]基于多標簽傳播的網絡社區檢測方法

有效

• 申請號: 201811247488.2
• 申請日: 2018-10-25
• 公開（公告）號: CN109379282B
• 公開（公告）日: 2020-11-13
• 發明（設計）人: 湯穎;王斌
• 申請（專利權）人: 浙江工業大學
• 主分類號: H04L12/723
• 分類號: H04L12/723;H04L12/26
• 代理公司: 杭州天正專利事務所有限公司 33201
• 代理人: 王兵;黃美娟

基于多標簽傳播的網絡社區檢測方法，包括：步驟1：數據預處理階段，計算各個節點的密度值與距離值；步驟2：社區中心點選擇；利用各個節點的密度值與距離值，通過DPC決策圖選取社區中心點；步驟3：根據社區中心點進行多標簽傳播，傳播結果即為社區檢測結果；步驟4：將社區檢測結果與數據集中各節點的真實標簽進行比較，證明方法的有效性。

技術領域

本發明涉及一種社交網絡的社區檢測方法。

背景技術

隨著信息科技和社交網絡的快速發展，人與人之間的聯系越方便，社交網絡的規模越來越大。如何對龐大的社交網絡進行有效的分析以發現有價值的信息是一個很有意義的問題。其中，社區檢測方法是一種很重要的網絡分析方法。該類方法通過社交網絡中各用戶之間的聯系，將網絡劃分為多個不同的社區。通常來說，同一個社區內的用戶之間具有緊密的聯系，而不同社區的用戶之間聯系較弱?；谏鐓^劃分，可以分析不同社區用戶的特點，并根據用戶所在的社區提供符合該社區用戶特點的服務，因此具有很大商業價值。

社區檢測方法可分為基于圖的劃分、基于層次聚類以及標簽傳播方式。圖劃分方法需要預先知道網絡中的社區數目；層次聚類方法通常時間復雜度高，而且最終檢測到的社區數目取決于方法中設定的距離閾值；標簽傳播方法時間復雜度較低，適用于復雜網絡，但是也存在標簽更新不穩定、社區數目取決于方法中的特定參數的問題。

發明內容

為了克服現有技術無法準確識別網絡中社區數量以及基于標簽傳播的方法中標簽更新不穩定的問題，本發明提供一種新的基于多標簽傳播的網絡社區檢測方法來實現社區檢測；

本發明利用網絡拓撲結構，通過DPC(密度峰值檢測算法)識別網絡中社區中心點，并基于社區中心點進行多標簽傳播，從而實現網絡社區檢測；

基于多標簽傳播的網絡社區檢測方法，整體流程圖如圖1所示，主要分為中心點檢測階段和多標簽傳播階段；具體步驟如下：

步驟1：數據預處理階段，計算各個節點的密度值與距離值；密度值ρ，距離值δ以及密度-距離值γ的計算公式如公式(1)(2)(3)(4)所示：

ξ_i＝∑_jη_j (1)

ρ_i＝ξ_i+η_i (2)

γ_i＝ρ_i×δ_i (4)

其中η_j表示節點j的度數，ξ_i表示節點i的所有鄰居節點的度數之和，ρ_i表示節點i的密度值；d_ij表示節點i和節點j的圖最短路徑長度，其中節點j為密度值大于節點i的節點，δ_i表示節點i的密度值；

步驟2：社區中心點選擇；利用各個節點的密度值與距離值，通過DPC決策圖選取社區中心點；

2.1對節點的密度值和距離值分別進行Z-score標準化，標準化后的密度值ρ^*，距離值ξ^*以及標準化后的密度-距離值γ^*的計算公式如公式(5)(6)(7)所示：