[發明專利]一種基于密度峰值聚類的社團劃分方法及其用途

在審

• 申請號: 201910835339.6
• 申請日: 2019-09-05
• 公開（公告）號: CN110688533A
• 公開（公告）日: 2020-01-14
• 發明（設計）人: 王巍;韓運鵬;黃俊恒;辛國棟;王佰玲;劉揚
• 申請（專利權）人: 哈爾濱工業大學(威海);威海天之衛網絡空間安全科技有限公司
• 主分類號: G06F16/901
• 分類號: G06F16/901;G06K9/62;G06Q50/00
• 代理公司: 37247 青島華慧澤專利代理事務所(普通合伙)
• 代理人: 馬千會

本發明屬于數據處理技術領域，涉及一種網絡的社團劃分方法。該方法包括：輸入無權無向的原始圖；根據距離度量將原始圖轉化為有權圖；計算任意存在連邊的兩點之間的距離，得到距離矩陣；計算每個點的點密度和點距離；以點密度和點距離分別作為坐標系的橫軸和縱軸，得到二維聚類中心決策圖；確定聚類中心；采用迭代的方式將所有的點劃分到相應的聚類中心范圍內，得到最終的社團劃分結果。本發明的基于密度峰值聚類的社團劃分方法，使用密度峰值聚類思想直接作用于網絡結構數據，通過計算網絡結構數據的“點密度”和“點距離”的方法建立決策圖并確定聚類中心，在此基礎上進行組織的迭代劃分。

技術領域

本發明屬于數據處理技術領域，涉及一種網絡的社團劃分方法。

背景技術

互聯網成千上萬個頁面構成了網頁鏈接的網絡；國家城市間的運輸交通構成了物流網絡。因此對網絡的分析和結構劃分可以在很多具有現實意義的應用中發揮關鍵作用，應用場景也較為廣泛。

社團劃分是社交網絡研究領域的一個較為重要的課題，該研究在其他各個學科領域都可以找到較為廣泛的應用，如生物學、物理學、計算機圖形學和社會學等。而且從這幾個應用領域中，又有很多相應的方法被提出。其中具有代表性的有Grivan-Newman算法，KL算法等。這些算法一個共同特點是需要一個劃分標準來評價或是建立相應的目標函數，這方面應用最廣泛的是由Newman等人提出的模塊度函數Q，用來評價社團劃分結果的優劣度。社團劃分根據節點的歸屬唯一性可以分為重疊社團和非重疊社團。非重疊社團的劃分的研究開始的最早，應用也較為廣泛，最基本的方法有目標函數最優方法，譜聚類分析方法，信息論方法，標簽傳播算法等。其他大多數方法都是基于這些方法的變種或改進。在重疊社團的發現方面，成型的算法出現較晚，從2005年Palla等人提出CPM算法(Clique PercolationMethod，派系過濾算法)后，重疊社團越來越受到人們的關注。

現有的社團劃分方法中，有代表性的一類方法是基于聚類思想的，這類方法通過計算節點在向量空間的相似性或距離來劃分節點所屬社團，即首先將待聚類的網絡節點映射為向量空間的點，然后在向量空間應用聚類算法得到社團劃分結果。目前尚未發現有方法將聚類思想直接應用到原始的網絡結構進行社團劃分。

發明內容

本發明的目的是提供一種基于密度峰值聚類的組織劃分方法，該方法能夠直接作用于網絡結構數據進行節點的組織劃分，在保證準確性的前提下大大降低了算法復雜度，提高了執行效率。

為了實現上述目的，本發明采用的技術方案是：一種基于密度峰值聚類的社團劃分方法，包括：

輸入無權無向的原始圖；

根據距離度量將原始圖轉化為有權圖；

計算任意存在連邊的兩點之間的距離，得到距離矩陣；

計算每個點的點密度和點距離；

以點密度和點距離分別作為坐標系的橫軸和縱軸，得到二維聚類中心決策圖；

確定聚類中心；

采用迭代的方式將所有的點劃分到相應的聚類中心范圍內，得到最終的社團劃分結果。

作為本發明的進一步改進，所述的距離矩陣的計算過程為：計算任意存在連邊的兩點之間的依賴程度，得到相似度矩陣；使用指數函數將依賴程度映射為該兩點之間在進行密度峰值劃分時候使用的距離，得到距離矩陣。

作為本發明的進一步改進，計算兩點之間的依賴程度的相似度計算函數為：

其中，k_c為節點i和節點j的共同鄰居數，k_i和k_j分別表示節點i和節點j的度。